时间戳

首页 > 解决方案 > 最佳优先搜索和贪婪的最佳优先搜索之间的区别？

algorithm - 最佳优先搜索和贪婪的最佳优先搜索之间的区别？

问题描述

有什么区别吗？我被告知贪婪选择具有最高启发式函数值的孩子，即本地最佳后继者。我的困惑是在一个贪婪的最佳优先算法中会发生什么，它不跟踪它的访问节点，在不同的路径中遇到相同的节点？我会画出问题来清楚地描述它；在此处输入图像描述

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

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

标签： algorithmsearchartificial-intelligence

解决方案

这样一来，这是否意味着 ABCG 是最先提供的贪婪路径？因为它将只考虑节点 B 的子节点进行下一次选择？

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

相比之下，诸如A*Dijkstra 或 Dijkstra 之类的“最佳优先”算法会注意到最便宜的总路径。它从状态 (A, 0) 开始——到达A. 然后它产生移动（AB，2），（AC，3）和（AD，手）；它采取最便宜的移动，（AB，2），但保留列表中的其他移动。现在它产生总成本的移动B： ( ABE , 7) 和 (ABC, 5)。在这一点上，它下降 (ABC, 5) 因为有一条已知的更便宜的路径到C.

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

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

推荐阅读