人工智能搜索問題：飛機上有障礙物的兩點之間的最短路徑

Question

我試圖解決人工智能中使用不知情搜索策略的問題。這是問題，將不勝感激您的建議。

目標是找到具有凸多邊形障礙物的平面上2點之間的最短路徑。假設狀態空間由（x，y）平面中的所有位置組成，那裏有多少個狀態？目標有多少條路徑？

我相信有x * y個州，但我不確定這個目標有多少條路徑？

此外，我需要定義一個良好的狀態空間，我也不知道如何思考解決方案，因此也會對此提出建議。

更新1：關於'良好狀態空間'我必須解釋爲什麼在場景中從一個多邊形頂點到其他任何其他頂點的最短路徑必須由連接多邊形的某些頂點的直線段組成，然後定義一個好的狀態空間，告知這個狀態空間有多大。

謝謝！

Answer 1

假設在平面上的離散位置 - 即整數 - 那麼在你所說的這個平面上存在x * y個位置。假設沒有周期，不同路徑的數量指數地增加，但它不是無限的。例如，在最壞的情況下，如果開始狀態爲0,0，結束狀態爲w，h，並且表面上沒有障礙物，那麼可以想象從開始到結束構建最小生成樹將包含所有路徑。對於2x2飛機，會有2條路徑;對於2x3飛機，會有4條路徑，依此類推。如果你允許循環，那麼你可能有無數的路徑。

請注意，「障礙」對於搜索算法並不是真正的問題。他們只是不能從鄰國到達。例如，A *不會生成一個「障礙物」作爲可達節點，因此它不會將其添加到打開的列表中。 （事實上​​，它也不會被添加到封閉列表中，它根本不是節點）。

我不確定你的意思是「定義一個好的狀態空間」。你能澄清嗎？

編輯：如何獲得2x2平面最多2條路徑？簡單。首先，把你想要的開始和結束位置。他們要麼彼此相鄰，要麼相反。在它們彼此相鄰的情況下，第一路徑是微不足道的。第二條路徑是首先遍歷所有其他方塊。在對角的情況下，通過使用其他方格之一作爲第一步獲得一條路徑，另一條路徑使用剩餘的空方格作爲第一步。在任何一種情況下，如果你不允許循環，這些是唯一的路徑。