[幾何] 城市與小鎮間的公路路徑最佳化

看板Math作者 (BOB)時間6年前 (2019/02/28 18:48), 編輯推噓8(8推 0噓 31→)
留言39則, 3人參與, 6年前最新討論串1/2 (看更多)
請教一個問題: 有一個城市A在地圖的中心位置 而若干其他的小鎮散佈在它的四周 現在市政府要蓋公路由城市通往所有小鎮 但為了整齊 道路只能蓋東西南北四向 不能斜蓋 那麼有沒有什麼方法 可以求得公路總長最短的蓋法? 謝謝! -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.227.20.43 ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1551350934.A.EDC.html
→
03/03 02:08, 6年前 , 1F
好難喔瞎猜一下 四個象限 第一象限 Max(X)+sigmaY
03/03 02:08, 1F
→
03/03 02:20, 6年前 , 2F
想法錯了 自打臉
03/03 02:20, 2F
→
03/03 02:24, 6年前 , 3F
先求幾何中心 然後蓋x軸 y軸 再連連看?
03/03 02:24, 3F
推
03/03 02:25, 6年前 , 4F
投影到x軸y軸分開算 這兩個是獨立的
03/03 02:25, 4F
→
03/03 02:26, 6年前 , 5F
單軸的情況就是高中的絕對值題 答案是中位數點
03/03 02:26, 5F
→
03/03 02:26, 6年前 , 6F
所以 (Me_x, Me_y) 就是中心點 總長只能暴力加
03/03 02:26, 6F
→
03/03 02:27, 6年前 , 7F
嗯 這樣不太對 因為路可以共用
03/03 02:27, 7F
→
03/03 02:28, 6年前 , 8F
還有一個方法 各點距離算一算 然後開圖論演算法炸
03/03 02:28, 8F
→
03/03 02:29, 6年前 , 9F
單純求幾何中心 蓋x 跟 y 再連起來有什麼錯???
03/03 02:29, 9F
→
03/03 02:30, 6年前 , 10F
就是 x1+x2+x3...xn/n y1+...yn/n 然後蓋在這大十字
03/03 02:30, 10F
推
03/03 02:33, 6年前 , 11F
那(2,3) (2,-1) (-2,3) (-2,-1)就掛了
03/03 02:33, 11F
→
03/03 02:34, 6年前 , 12F
嗯 每個點都選一點距離它最近的城鎮
03/03 02:34, 12F
→
03/03 02:34, 6年前 , 13F
把這些點連起來之後 會形成好幾團
03/03 02:34, 13F
→
03/03 02:34, 6年前 , 14F
然後再考慮每一團到另一團最短距離
03/03 02:34, 14F
→
03/03 02:34, 6年前 , 15F
這樣接起來之後應該就很短了 不過是不是最短很難說
03/03 02:34, 15F
推
03/03 02:38, 6年前 , 16F
中心(0,1)總長南北4 東西8 還有更短的嗎?
03/03 02:38, 16F
→
03/03 02:40, 6年前 , 17F
題目不是從中心到各城最短 而是公路總長最短
03/03 02:40, 17F
→
03/03 02:40, 6年前 , 18F
總覺得幾何中心 拉一個十字 再蓋 沒矛盾?
03/03 02:40, 18F
推
03/03 03:19, 6年前 , 19F
有吧 題目有規定要從中心城鎮連線
03/03 03:19, 19F
→
03/03 03:20, 6年前 , 20F
也就是(0,0)是必帶的
03/03 03:20, 20F
→
03/03 03:20, 6年前 , 21F
算中心(0,1)的bug就是沒接到(0,0)
03/03 03:20, 21F
→
03/03 03:21, 6年前 , 22F
事實上就算把(0,0)丟進去算五點中心
03/03 03:21, 22F
→
03/03 03:21, 6年前 , 23F
先蓋x再蓋y 和 先蓋y再蓋x 答案還是不一樣
03/03 03:21, 23F
推
03/03 03:24, 6年前 , 24F
上面那個好像是直接連直線的最短 但不是縱橫的最短
03/03 03:24, 24F
→
03/03 03:25, 6年前 , 25F
畫縱橫最麻煩的情況是會共用路線
03/03 03:25, 25F
→
03/03 03:26, 6年前 , 26F
再舉一個反例 (1,1), (2,1), ..., (9,1)
03/03 03:26, 26F
→
03/03 03:26, 6年前 , 27F
以及這9個點轉90, 180, 270度 總共36個點
03/03 03:26, 27F
→
03/03 03:27, 6年前 , 28F
很明顯 照直觀隨便連 會比你說的平均十字短很多
03/03 03:27, 28F
推
03/03 03:41, 6年前 , 29F
嗯 (1,1), (2,1), ..., (9,1) 和其上下對稱
03/03 03:41, 29F
→
03/03 03:42, 6年前 , 30F
和 (1,9), (2,9), ..., (9,9) 及其上下對稱
03/03 03:42, 30F
→
03/03 03:42, 6年前 , 31F
這兩個圖的畫法差很多 明明只是拉遠而已
03/03 03:42, 31F
→
03/03 03:44, 6年前 , 32F
啊要再更近 (1,0.1), ..., (9,0.1) 和上下對稱
03/03 03:44, 32F
→
03/03 03:45, 6年前 , 33F
一個走中間路比較好 一個各自連線比較好
03/03 03:45, 33F
→
03/03 14:52, 6年前 , 34F
(1,1)到(9,1) 蓋(1,1)到(9,1)然後 (0.0)到(1,1)就好
03/03 14:52, 34F
→
03/03 14:53, 6年前 , 35F
沒矛盾 2種蓋法都是最短的
03/03 14:53, 35F
→
03/03 14:57, 6年前 , 36F
阿 我知道錯哪了
03/03 14:57, 36F
推
03/05 03:14, 6年前 , 37F
不能蓋斜的很奇怪 我可以一直轉直角去趨近他....
03/05 03:14, 37F
→
03/05 03:14, 6年前 , 38F
這座標化是不是很像相關係數回歸線
03/05 03:14, 38F
推
03/05 04:25, 6年前 , 39F
一直轉直角長度又不會變XD
03/05 04:25, 39F
‣ 更多 BOB1105 的文章
文章代碼(AID): #1STxoMxS (Math)
‣ 更多 BOB1105 的文章
文章代碼(AID): #1STxoMxS (Math)