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

看板Math作者Desperato (Farewell)時間6年前 (2019/03/03 05:19)推噓3(3推 0噓 4→)

留言7則, 3人參與討論串2/2 (看更多)

※ 引述《BOB1105 (BOB)》之銘言： : 請教一個問題: : 有一個城市A在地圖的中心位置 : 而若干其他的小鎮散佈在它的四周 : 現在市政府要蓋公路由城市通往所有小鎮 : 但為了整齊道路只能蓋東西南北四向不能斜蓋 : 那麼有沒有什麼方法 : 可以求得公路總長最短的蓋法? : 謝謝! (尚未解決) 城市和小鎮的分別其實不重要，可一視同仁 (Def) 「點」為公路的轉折點、分岔點或終點「真點」是那些有小鎮在上面的點「假點」是那些沒有小鎮在上面的點 (Def) 「線」是兩端為點，中間沒有其他點的線段「直線」是兩端為點，中間可以有其他點的線段「長直線」是延伸最長的直線 (Def) 給定一組真點 V1, 一個蓋法 G = (V, E) 是指一個連接圖 (1) V 包含所有真點 V1 和一些假點 V0 (2) E 中任一條線 e 都是縱橫方向 (3) 如果 v0 是假點，則至少有一水平和一垂直線往外連接 (不然可以刪掉這個假點) (Lem) 對任意蓋法 G 存在一個 G', 總長不多於 G 且每一條長直線上至少有一點真點 (pf) 如果有一條長直線上都是假點，叫它假長直線設 G 有一條假長直線 E，此假長直線將平面分成兩半考慮所有和 E 相交且垂直的直線則兩半平面上必有一半，例如 A，含有的垂直線比較少(或一樣) 此時將 E 往那個半邊平行滑動，E 上的假點跟著移過去 (1) 位於 A 的垂直線跟著縮短 (2) 位於 B 的垂直線跟著伸長 (3) 橫跨 AB 的垂直線就不變由上可知，總長度會降低或不變 E 滑到以下兩個情形時會停下來，稱為新圖 G1 (1) 某條垂直線碰到假點，此時 E 會蓋住至少一條線段總長直線數 N 會減少(少了被蓋住的線段所在的長直線) (2) 某條垂直線碰到真點，此時總假長直線數 N0 會減少(少了E自己) G1 中如果有多餘的假點就刪掉，則 G1 也是一個蓋法。對 N, N0 作數學歸納法即可得證 (Def) 給定一組真點 V1, 考慮其各自的 x 座標 X, y 座標 Y 則網格 Z(V1) 為以下所有線段的聯集 (1) X 中任選 x，Y 中任選 y1, y2，形成線段 (x, y1) 到 (x, y2) (2) Y 中任選 y，X 中任選 x1, x2，形成線段 (x1, y) 到 (x2, y) 其實就是長的像下面樣子的東西　　　┌──┬┬─‧────‧ 　　　├──┼‧─┼────┤ 　　　│　　││　│　　　　│ 　　　│　　││　│　　　　│ 　　　‧──┼┼─┼────┤ 　　　│　　││　│　　　　│ 　　　│　　││　│　　　　│ 　　　│　　││　│　　　　│ 　　　└──‧┴─┴────┘ (Def) 一個蓋法 G 是網格蓋法就是所有線段 e 都在網格 Z(V1) 上的蓋法 (Lem) 如果 G 是總長最短的網格蓋法則 G 也是總長最短的(一般)蓋法 (pf) 明顯由上面的 Lem 得證這代表想要總長最短的蓋法，只要在網格 Z(V1) 上做就好暫時只到這而已，接下來也很難搞 -- 嗯嗯ow o -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 101.12.9.172 ※ 文章網址: https://www.ptt.cc/bbs/Math/M.1551561582.A.C8D.html

推

arthurduh1

03/03 11:00, 6年前 , 1^F

03/03 11:00, 1^F

推

XII

03/03 13:33, 6年前 , 2^F

03/03 13:33, 2^F

→

XII

03/03 13:33, 6年前 , 3^F

03/03 13:33, 3^F