貪心最好的搜索算法，如何計算其遍歷的長度？

Question

我有這個問題，我正在與貪婪的最好的第一搜索算法有關。然而，當談到點（x，y）時，我有點卡在計算遍歷的長度。例如讓我說我有這些點： （0,1），（0,2），（1,2），（1,3）。所以我所做的就是畫了一個圖上的X，Y平面：

現在知道GBF算法，它會檢查在這種情況下，橫向看起來像這樣的衣櫃節點等：（0， 1）→（0,2）→（1,2）→（1,3）。所以現在爲了計算GBF完成的點連接的長度，我是否需要基本加上路徑，在這種情況下，路徑是三？任何澄清都會有所幫助。

Answer 1

第一部分是找到使用適當的數據結構來存儲圖形的最佳方法。

現在說圖表看起來像這樣。

  (1,3)P4 
      | 
P2(0,2)--(1,2)P3 
    | 
(0,1)P1 
    | 
(0,0)P0 

表示此圖表的一種方法是使用Adjacency List。這樣

P0 => P1 
P1 => P2 
P2 => P3 
P3 => P4 

現在使用Breath first Search兩個點之間的距離可以在線性時間來計算。兩個節點（點）之間的距離與路徑長度爲數字邊緣。

對BFS解釋可以發現here