明星算法沒有采取視覺理想的路線

Question

我已經實現了A星算法來找到一個簡單的網格上的兩個節點之間的路線。我目前正在沒有任何障礙的網格上進行測試，似乎找到了最短路徑，但它不是一條「理想」的最短路徑，因此我的意思是不會隨機改變方向。理想情況下，我希望它繼續向一個方向發展，這意味着它只會改變方向一次。

我該如何執行此操作？我正在查看代碼的哪一部分，我考慮在打開的列表中展開哪個節點，並且如果下一個圖塊具有相同的方向，則我可以通過記錄先前的方向並選擇相同的方向來破解某些內容相同的f值，但它不是很優雅。

Answer 1

鑑於你的圖形G=(V,E)其中V每個v代表一個細胞，每一個邊緣(u,v)是可能的移動，你可以按如下創建一個新的（加權）圖G'=(V',E')：

V' = V_u U V_d U V_l U V_r - 各組代表的此舉的類型是否爲V_d,V_l,V_r

在E做最後和V_u = { v_u | for each v in V }，同樣現在，每個邊緣(u,v)：

• 如果（u，v）代表'左'移動，則添加(u_l,v_l,1)和(u_r,v_l,1+eps),(u_u,v_l,1+eps),(u_d,v_l,1+eps)。直覺上來說 - 你給「改變方向」的小懲罰（eps），如果保持相同的方向則不會受到懲罰。
• 如果（u，v）表示「向上」移動，請添加(u_u,v_u,1)和(u_r,v_u,1+eps),(u_l,v_u,1+eps),(u_d,v_u,1+eps)。 （類似地）
• 重複'右'和'下'移動。

確保eps足夠小，只能影響相同長度的路徑。 1/(|V|+1)應該這樣做。
還要確保你現在有4個目標（t_u,t_d,t_l,t_r，其中t是原始目標）。

這給你一個帶有4*|V|頂點的圖，它現在傾向於保持相同的方向來改變它。你可以堅持你以前的啓發 - 如果它是可以接受的，它會保持這種方式。

Answer 2

你不應該執行什麼。只要看看你的路徑，我可以告訴你算法有問題。雖然沒有你的代碼，我不能告訴你它在哪裏。由於（a^2 + b^2 = c^2），開放網格上的最短路徑始終是直線。 A *將永遠返回。如果你發佈你的代碼，我可以給你一些你需要做的指導。但是現在你的成本計算因爲某種原因而關閉，否則你會直接從頭開始到結束。還要記住，A *找到一條最短路徑時/如果有一條平行線。在你的情況下不會有，但是當你添加障礙物時，視覺評估圖並不總是一個好的指標。

長答案短。檢查您的成本函數以及您確定路徑節點的前一個節點的方式。如果你發現把它帶到當前節點是不利的，那麼你將不會使用前一個節點。如果你的成本函數是錯誤的（通常啓發式會以某種方式搞砸），它也會發生。