當只允許對角線移動時，A *的啓發式

我打算使用A *算法在具有隻允許對角線移動的障礙物的無限網格上進行路徑查找。但我不確定要使用哪種啓發式。我知道我不能使用曼哈頓距離。任何人都可以提出一些建議嗎？當只允許對角線移動時，A *的啓發式

2015-11-07 Arun

如果只允許對角線移動，則根據起始位置，網格的一半不可到達。這是對的嗎？（例如國際象棋主教） – Demplo

@Demplo是的，你說得對。 – Arun

然後我會說湯姆的答案很好。一旦你知道目標是否可達，你旋轉45度並在那裏使用曼哈頓。假設對角線移動成本1. – Demplo

想象棋。旋轉45度。如果僅允許對角線運動，則實際上它就像僅具有正交運動的網格，但原始網格上的一半點無法到達。

2015-11-07 16:31:26

是的，那麼我應該使用哪種啓發法，以便它可以被接受？ – Arun

@Arun：首先看看目標是否可以達到。然後將座標轉換爲一個普通的網格，並使用任何啓發將你用於這樣的網格。 –

回答