座標系統中兩點之間的最短路徑

Question

我有兩個點A和B.我想找到從A到B的最短路徑，但有N個（最多200個）矩形，路徑不能與任何這些矩形相交。路徑和矩形只能在矩形的頂點和矩形的兩邊相交。最短路徑的長度是多少？矩形不能相交。他們可以分享點或一邊。所以如果他們中有兩個人分享了一方，那麼你可以在他們之間傳遞。

Answer 1

通常這種問題的最佳算法是A*使用像Manhattan Distance這樣的簡單啓發式算法。但首先你應該找到非法點。非法點是你不能在這個問題中輸入的點，矩形內的點是非法的（位於矩形兩側的點是合法的，因爲你可以通過它們）。找到這些點後，只需執行A *算法，即可找到A和B之間的最短路徑。

請注意，由於此問題中沒有邊權重，因此您可以簡單地運行BFS以查找最短路徑，但不會像A *那樣快。

如果您的搜索空間非常大，並且您使用A *耗盡內存，則應考慮使用消耗較少內存但不止一次探查節點的IDA*。