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

[Desperato (Farewell)]

※ 引述《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  : cf. rectilinear minimum spanning tree
推 XII         : to 1F 這應該是類似 Steiner tree problem
→ XII         : 而不單只是 spanning tree
→ XII         : 這是NP-hard,見Rectilinear Steiner tree(wiki)
推 arthurduh1  : 那要改 rectilinear Steiner tree, 變 NP-hard 了XD
→ Desperato   : NOOOOOO qw q
→ Desperato   : 看到wiki上有Hanan grid覺得蠻感動的XD