迷宮求解優化不左轉算法

Question

我正在一個項目中，我需要使用最少的右轉數和左轉來解迷宮。

只要右轉最小化，行駛距離就無關緊要。我們被要求使用回溯算法和最優（時間）算法來實現我們的程序。

對於回溯算法，我打算使用堆棧。我的算法可能類似於：

• 將所有四個可能的起始方向推入堆棧。
• 遵循一條路徑，儘可能直行。
• 如果我們到達迷宮的盡頭，返回當前路徑長度爲最佳。
• 如果我們達到死衚衕回溯到最後一個可能的右轉並採取它。
• 如果當前路徑長度大於當前最佳路徑，則回溯到最後一次可能的右轉並採取它。

我想知道是否有人可以指出我爲這個最佳算法的方向。

我有一段艱難的時間想着比回溯的更好的東西。

Answer 1

我認爲你可以這樣做，首先找到所有可用0向右轉動的點。然後右轉一圈，依此類推。你可以使用一個隊列來做到這一點。請注意，在第n階段，您可以針對n個右轉可達到的所有點獲得最佳解決方案。更重要的是，任何尚未到達的點都可以達到n點或根本不可達。爲了達到最佳的時間複雜度，您必須使用這樣一個事實，即您只需要從那些到達的點開始搜索新的可到達點，這些點在適當的方向上有一個未到達的鄰居。由於每個點只有4個鄰居，你只能從中搜索4次。您可以通過爲每個方向維護一個單獨的列表來實現它，該列表包含所有到達的點，並且在該方向上有一個未到達的鄰居。這給你一個與迷宮面積成正比的時間複雜度，它與輸入數據的大小成正比。

下面我提出一個圖形化的例子：

. . . . . . (0) . . . . . 0 1 1 1 1 (1) 0 1 1 1 1 1 
. ####### . . 0 ########## . 0 ########## . 0 ########## 2 
. # . # . . 0 # . # . . 0 # . # . . 0 # . # . (2) 
. # . . . . 0 # . . . . 0 # . . . . 0 # . . . (2) 
. #### . # . 0 #### . # . 0 #### . # . 0 #### . # 2 
(.) . . . . . (0) . . . . . 0 1 1 1 1 1 0 1 1 1 1 1 

0 1 1 1 1 1 0 1 1 1 1 1 
0 ########## 2 0 ########## 2 
0 # . # 3 2 0 # 4 # 3 2 
0 # (3) 3 3 2 0 # 3 3 3 2 
0 #### . # 2 0 #### 4 # 2 
0 1 1 (1) 1 1 0 1 1 1 1 1 

()分別表示已與相應的鄰居未得點

Answer 2

通過構建迷宮中每個位置的四個節點來構建一個圖。每個節點都將對應一個特定的方向：N，S，E，W。

每個節點和至多三個相鄰鄰居之間將存在邊：「前」，「後」和「正確「（如果存在）。通向「前」和「後」中節點的邊將具有權重0（因爲路徑長度無關緊要），而「右」中的節點的邊將具有權重1（這是表示右轉的成本）。

一旦圖形設置完成（並且可能最好的方法是重新使用迷宮的原始表示），修改後的breadth-first search算法將解決該問題。

處理0/1邊權重的技巧是使用deque而不是標準隊列實現。具體來說，通過0重量邊緣到達的節點將被推到雙耳前方，通過重量1邊緣到達的那些將被推到後面。