探索網格並找到標誌的最快方法

Question

我有一個n×n網格，以障礙物的形式出現。我需要從隨機點開始在這個網格的某處找到一個標誌。您可以左轉，右轉或向前/向後移動 。

在網格中的每個點都有關於您的四個塊（上，下，左，右）的信息。 BFS似乎是一個很好的解決方案。但它讓我懷疑是否有更快或更好的探索算法？

任何想法將不勝感激。

Answer 1

BFS確實是您需要的算法。作爲額外的好處，你會發現細胞穿越國旗的最短路徑。另外請注意，您不需要以任何「傳統方式」存儲整個圖形，在這種情況下，網格足以代表圖形本身。我的很多學生都不明白這一點。

Answer 2

這似乎是一個正常的網格勘探問題。如果您使用BFS，則可以找到距離爲<的所有點=開始和標誌之間的距離。

但是，我會建議使用一些優化。

如果您知道標誌的座標（您的問題不清楚），您可以使用A *。

如果你沒有標誌座標，你可以嘗試利用你的信息塊。在一個正方形網格上，BFS創建圓形搜索前沿，這意味着您可以獲得圍繞您開始的圓形區域內的點上的所有信息。這意味着您將評估該地區的所有點。您可以嘗試通過優先評估點數來最大化您的探索，這些點數可以爲您提供更多有關您的圖形點的信息，這些點有許多未知的鄰居。

這將重定向您的搜索以儘快評估新分數。一旦你找到了標誌，你就有了距離的上限，你可以探索圖中未知的部分，可以改善邊界。您還可以考慮優先級功能從開始到結束的距離，以避免搜索過度。優先功能的平衡將取決於您的電網和障礙物的數量。