找到沒有信息的迷宮退出的最佳算法

Question

我必須確定一種讓機器人走出迷宮的方法。事情是，迷宮的佈局是未知的，並且出口的位置也是未知的。機器人也開始在迷宮中的未知位置。 我發現了3種解決方案，但我很難知道應該使用哪種解決方案，因爲最終似乎解決方案純粹是隨機的。 我有那些3個解決方法：
1）基本的「人性化」戰略（），在那裏你把你的手在牆上，如果需要通過所有迷宮？我還保留了一個變量「轉向計數器」以避免機器人環路的情況。
2）深度優先搜索
3）在使機器人選擇方向隨機

隨機一個似乎更糟，因爲他可能需要很久才能找到出口（但另一方面，他可能是最快的了。 ..）。但我不確定其他兩個。
另外，有沒有辦法有某種啓發式？缺乏信息讓我覺得這是不可能的，但也許我錯過了一些東西。

最後一件事：當機器人找到出口，他將不得不使用A *回到他的起始位置。這意味着在第一部分，他尋找出口時，他會畫出第二部分迷宮的地圖。也許這也可以爲第一部分選擇最好的算法，但是我不明白爲什麼會更好。

有人可以幫我嗎？謝謝（另外，對不起我的英文）。

Answer 1

這樣的問題被歸類爲實時搜索，也許是最著名的例子是學習實時*，在那裏你結合你以前見過什麼樣的信息（如果你已經原路返回或者知道更便宜的方式來達到一個國家），以及你可以採取的行動。與reinforcement learning等區域一樣，某種程度的隨機性有助於平衡勘探和開採。

假設您的圖是無向的，時間不變，初始和出口節點存在於同一個組件中，那麼在每個頂點隨機選擇一個方向相當於random walk on a graph。 不管該圖是最初被與否，這是一個很容易理解的數學領域，相當於一個absorbing Markov chain，在這種情況下到達出口狀態的時間有Discrete phase-type distribution - 往往是相當緩慢的，但它也是值得注意在病態的情況下，可以設計一個隨機遊走將超越DFS的迷宮。

Answer 2

@beaker是正確的，因爲你建議的前兩個應該導致相同的結果。但是，通過跟蹤找到的任何循環，您可能會稍微改進搜索。如果機器人發現自己已經到過一個地方，並且一旦到達死路一段時間就需要回溯，如果找到了它的快捷方式，則可能不需要返回到目前爲止。還可以使用已出圖的段，並應用Dijkstra算法或A *來找到最有效的方法。在未探索的道路上可能會有更快的途徑，但這將是獲得快速結果的最安全的方法。

顯然，這實現檢查循環，以防止不必要的後面跟蹤會使事情更復雜的實現。儘管使用Dijkstra算法的迴歸開始不應該那麼複雜。

如果你現在感覺雄心勃勃遇見你可以使用這個信息，給機器人的方向感雖然在隨機生成的迷宮，可能沒有太大的幫助出口。