它们之间真的有区别吗？我听说贪婪算法会选择启发式函数值最高的子节点，即局部最优后继。我感到困惑的是，在一个不跟踪已访问节点的贪婪最佳优先算法中，如果通过不同的路径再次遇到同一个节点，会发生什么？我将通过图示来清楚地描述这个问题；

当贪婪最佳优先算法通过B到达C时，它会扩展哪个节点C，是C(x)还是C(y)？输出路径会是ABCG还是ACG？

注意，这棵树是网格中最短路径评估的图形表示，子节点是网格中父节点的有效邻居节点。

回答：

那么，这是否意味着A-B-C-G是贪婪最佳优先算法提供的路径？因为它只会考虑节点B的子节点进行下一步选择？

是的：严格的“贪婪”算法在每个节点处只考虑最佳的短期选择。在第一步，B比C便宜，所以它开始沿着这条路径走。从这里开始，它将B视为起始节点。从这里最便宜的移动是到C，然后到G。

相比之下，像A*或Dijkstra这样的“最佳优先”算法会注意到最便宜的总路径。它从状态(A, 0)开始——到达A不花费任何费用。然后它生成移动(AB, 2), (AC, 3), 和(AD, 很多)；它选择最便宜的移动，(AB, 2)，但保留其他移动在列表中。现在它从B生成移动，带有总成本：(ABE, 7) 和(ABC, 5)。在这一点上，它丢弃(ABC, 5)，因为已经知道有更便宜的路径到达C。

现在列表中最便宜的路径是(AC, 3)，算法将从这里生成移动：(ACG, 3+未知)。

这对你来说足够清楚了吗？