通路/鋪路問題

今天我們得到了一個任務，在實驗室完成（兩個小時）。問題是：通路/鋪路問題

給出一個m * n矩陣。
矩陣有'h'住宅大廳和'b'主要大廈入口。
這些'h'大廳和'b'入口的位置是已知的（根據（x，y）座標）。
您需要鋪設通道，讓每個住宅大廳至少有一條通往「b」入口之一的道路。
最多可以有'b'這種不連通的路徑。
通路長度必須最小。
您只能向上，向下，向左或向右移動。
解決方案不得是蠻力嘗試。

任務結束。但我仍在思考如何解決這個問題。有這樣的問題的標準術語嗎？我應該讀什麼？

人們是否也使用這種算法在城市鋪設道路？

來源

2010-11-25 Utkarsh Sinha

這是我想出的解決方案。它不會生成'b'斷開的路徑。它產生了一條通過所有住宅大廳和入口的路徑。

計算每對節點之間的距離（X座標差異+ Y座標差異）。現在你有一個完整的圖表。
查找此完整圖的MST
MST的每個傾斜邊緣（不是垂直或水平的）都可以分爲兩部分 - 水平和垂直。
每個分割都可以通過兩種方式進行 - 先水平後再垂直，反之亦然。
通過每個這樣的排列並計算最短長度的路徑。這是答案。

來源

2010-11-29 07:08:19

無法告訴你解決方案是什麼（某種形式的成本最低的路徑分析，猜測），但我有一些道路建模軟件的經驗。

在規模的一端，您擁有使用類似（廣義而言）方法的戰略建模系統。它們可以被認爲是一種重力模型 - 它將使用交通生成和需求的估計來對例如城鎮和工業區之間的交通流量進行高水平預測，這對於尋找在主要計劃發展的宏觀效應，人口分佈或土地使用區的變化等等。

另一方面，您有城市，城鎮，交匯處等特定區域的模擬模型。這些數字模型將每輛汽車視爲具有侵略性，道路知識等因素的自主代理。這是一種非常暴力的風格方法，但它是唯一能夠提供有用的統計數據的實際流量行爲的複雜網絡，具有交通燈，公交車等功能。例如，交通建模者可以將其插入實際的交通控制數據，針對特定的設計解決方案運行特定時期的模型，並將其設置爲運行6或7次。由此產生的數據可以很好地評估特定解決方案相對於另一個解決方案（或現狀）的性能。

希望這提供了一些有用的上下文。

來源

2010-11-25 21:00:37 Hamish

有趣！你用什麼軟件？我想嘗試一下 – 2010-11-26 07:04:46

有問題描述的一個方面是，我不清楚：「只是一個連接路徑」

當你說：「你需要鋪設途徑」，意味着什麼或者可以有多個斷開的路徑？（例如，從大廳H1到建築入口B1和大廳H2建設入口B2獨立路徑的路徑）

但是無論你回答我的問題，這是一個非常棘手的問題：這是NP-很難，因爲它包括作爲特殊情況的rectilinear Steiner tree問題（當只有一個主樓入口時）。

所以沒有人知道如何在一般情況下有效地解決它！

來源

2010-11-25 21:34:50

我剛剛解決了這個問題。你可以有多個路徑。感謝您的術語 - 直線斯坦納樹...我會讀它！ – 2010-11-26 07:02:13

我認爲這個問題比較簡單，而不是斯坦納樹甚至不是最小生成樹。

將矩陣M表示爲圖G，其中V = {Mij | i < = m，j < = n}，E = {（Mi1j1，Mi2j2）：i1，i2 < = m，j1，j2 < = n，| i1-i2 | = 1-exclusive OR | j1-j2 | = 2}入口
採取組B，設置大廳h的
H '= H/B，B'= B/H（標記是入口大廳，它們在深度0達到，除去所有這些入口，因爲那些是大廳）
進行寬度優先遍歷。在每個深度標記可從B到達的大廳，直到所有大廳都被標記。選擇相應的路徑。

來源

2010-11-26 02:25:08 mho

這是通路的最小可能長度嗎？例如：H1 =（5,5）H2 =（6,9）B1 =（12,5）B2 =（10,10）。 H2非常接近B2，但那裏沒有路徑。 H1直接連接到B1。 H2連接到此路徑。 – 2010-11-26 07:08:56

我明白你的觀點，我回答考慮最低限度的含義 - 一組來自門的最小長度路徑。但看看你的評論 - 看起來你正在試圖找到一組路徑，使得它們的長度總和最小。在那種情況下，我將不得不重新嘗試 – mho 2010-11-26 10:20:38

這是一個搜索問題。你有望在2小時內完成，對吧？我會DFS和修剪。您可以使用啓發式更快地獲得更好的解決方案。但請記住啓發法不能保證最佳解決方案，因此您必須嘗試的所有可能性。似乎是NP難。

來源

2010-11-29 02:59:50

通路/鋪路問題

回答

相關問題