尋找最短路徑訪問網格上的所有非封鎖廣場

比方說，你有一個這樣的網格（隨機發）：尋找最短路徑訪問網格上的所有非封鎖廣場

現在讓我們假設你有車從一個隨機開始的時候，什麼是最短路徑去通過每個白色的盒子？您可以隨意訪問每個白盒，並且無法跳過黑盒子。黑匣子就像牆壁。簡而言之，您只能從白框移到白框。

您可以沿任何方向移動，即使是對角線。

兩個子問題：

假設你知道的所有黑匣子移動之前的位置。
假設你只知道一個黑盒子的位置，當你在一個白盒子旁邊時。

來源

2010-05-20 Laz

「通過每個白色盒子的最短路徑是什麼？」？你在這裏問什麼？你的意思是「去每個白盒子」？ – naiad 2010-05-20 16:50:25

是的..你只需要遍歷所有的白色框。 – Laz 2010-05-20 16:52:12

要找到最短的路徑，你必須做一個蠻力搜索。如果你事先知道黑盒子，這並不重要。 – mdma 2010-05-20 16:57:54

-1

嘗試建立它作爲一個曲線圖（其中每個節點具有其它至多8個節點），並把它像所述http://en.wikipedia.org/wiki/Travelling_salesman_problem

來源

2010-05-20 16:57:42 corsiKa

-1事實上，它可以簡化爲NP完全問題（您甚至沒有顯示過）沒有比告訴他蠻橫的力量更有幫助了。 – 2010-05-20 17:20:52

@BlueRaja：只因爲你不喜歡答案，所以沒有錯。我會給glowcoder 1，因爲他的回答忽略了這樣一個事實，即TSP通常需要每個城市訪問一次，這在這裏不是合適的模型，因爲需要多次訪問一些白盒子。 – 2010-05-20 17:30:32

TSP並不要求每個人都只被訪問一次。它只關心兩個城市之間的最短路徑，而不管它是否經過它已經前往的一座城市。無論你如何分割它，這都是一個NP難題，我相信最好採用與TSP相同的方法。 – corsiKa 2010-05-20 17:34:23

這類似於騎士遊問題，其中一個典型的解決方案來評估所有可能的路由起源於起始廣場。當巡回賽無法完成時，回溯用於返回以前的決定。由於您可以多次訪問廣場，因此您的問題更加放鬆。騎士旅行和旅行Saleman問題通常需要訪問每個廣場一次。

參見http://en.wikipedia.org/wiki/Knight's_tour

來源

2010-05-20 16:59:43 mdma

如果您可以不止一次地訪問廣場，您如何確定巡迴賽何時無法完成（因此是時候開始回溯）？通常這是在所有附近的廣場已經被訪問時確定的 - 但是如果你可以訪問它們兩次，則不再適用:-) – psmears 2010-05-21 10:01:02

你可以做從sqaure到square的可達性分析。評估從源方塊到目標方塊的所有路徑。在這裏，你避免週期，我們只需要一個路徑，所以每個方塊只被訪問一次。作爲一個例子，考慮一個棋盤，黑色方塊在中央分成兩半。在你開始的一半的廣場是可達的，另一半的廣場不是。 – mdma 2010-05-21 10:12:03

你應該作爲一個完整的圖，其中兩個節點（白框）之間的距離是這些節點之間的最短路徑的長度的問題進行建模。這些路徑長度可以通過Floyd-Warshall算法來計算。然後，你可以把它當作"Traveling salesman"，就像glowcoder寫的那樣。

編輯：使其更加清晰：您可以通過一系列不同的白色框來描述迷宮中的每個「有趣」路徑。因爲如果你有一個訪問每個白盒子的任意路徑，你可以把它分成子路徑，每個子路徑到目前爲止還沒有訪問過的新白盒子。從白框A到B的這些子路徑中的每一個都可以用從A到B的最短子路徑代替，這就是爲什麼您需要所有節點矩陣之間的最短路徑。

來源

2010-05-20 17:10:34

這非常令人費解。 TSP直接適用。爲什麼要通過弗洛伊德 - 華沙？-1直到你進一步闡述。 – 2010-05-20 18:08:12

@Moron：從維基百科，第一句話：「任務是找到一個最短的巡迴訪問每個城市*一次*」。這就是我的建議所做的事情：即使您不止一次訪問每個廣場，也可以將此問題視爲此類TSP問題。 – 2010-05-20 19:23:24

@Doc：我明白你的意思了。我將刪除-1。儘管如此，仍然非常複雜。我刪除了一個空格以允許我撤消-1。 – 2010-05-20 19:32:12

這似乎是一個NP完全問題。

哈密頓圖網格圖中的哈密頓路徑爲NP-Complete已顯示在這裏：Hamilton Paths in Grid Graphs。

注意網格圖=完整網格的子圖。

當然，我還沒有讀過那篇論文，所以先確認一下，尤其是對角線運動允許的部分。

來源

2010-05-20 18:16:42

這如何減少找到哈密爾頓路徑？他明確地說，你可以隨心所欲地訪問每個白盒子，這在哈密頓路徑中並非如此。 – bnaul 2010-05-20 18:43:43

@bnaul：減少類似於http://stackoverflow.com/questions/2359345/non-cycle-path-to-all-nodes/2360303#2360303可能會工作。 – 2010-05-20 18:48:40

Doc已經知道了。我會補充說黑盒子只會改變所有白盒之間的距離。進一步的細節 - 如果任何兩個白色方框之間的對角線上有一個黑框（容易檢查），則需要計算最短路徑以獲得距離。一旦有了距離矩陣，就可以通過在創建一個長度爲零的虛擬節點到所有其他節點之後求解TSP來求解TSP或哈密頓路徑。

關鍵是，爲了制定和解決TSP（或任何問題的公式），你必須有一個距離矩陣開始。距離矩陣並未在開始時指定，因此必須從頭開始開發。

來源

2010-05-20 20:09:37 Grembo

雖然基於TSP的啓發式是一種合理的方法，但它並不清楚它給出了最佳答案。問題（正如Moron指出的那樣）是跨越軌跡問題，並且在評論中提供的鏈接中，有很多特殊的情況存在線性時間最優解。一個讓OP的問題不同於引用論文中使用的網格圖形公式的問題是能夠沿着對角線進行遍歷，這相當多地改變了遊戲。

來源

2010-06-30 20:56:42 Suresh

尋找最短路徑訪問網格上的所有非封鎖廣場

回答

相關問題