贪心最好的搜索算法，如何计算其遍历的长度？

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