在图上从 A 点到 B 点进行贪婪搜索

Question

教科书中的一个问题要求我通过 1) 贪婪搜索和 2) 统一成本搜索计算并找到从 Mehadia 到布加勒斯特的路线。

*现在我可以通过统一成本搜索完全说明和解决路线，但我的贪婪搜索看起来非常相似。关于如何通过 "greedy" 搜索计算路线的任何想法？

更新 我应用了一个混乱的贪婪算法，并从我的统一成本中获得了一条与最短路线不同的路线。

这是我的贪心算法输出的路线。该算法只是不断检查并选择最小的局部值。我对任何人的新问题：这条路线作为我的贪婪算法的输出是否可以接受？ IE。我的解决方案甚至可以在法律上被视为贪婪吗？

基于我的新算法的路线：

梅哈迪亚 -> 卢戈伊 -> 蒂米什瓦拉 -> 阿拉德 -> 泽林德 -> 奥拉迪亚 -> 锡比乌 -> Rimnicu Vilcea -> 皮特什蒂 -> 布加勒斯特

Answer 1

当您使用 Uniform-cost 搜索 时，您正在计算从 Mehadia 到所有节点的最短路径，因此您可以确定 Mehadia-Bucharest 路径将是optimal one（这个算法是完整的和最优的）。 但是如果你使用贪心搜索算法，它会选择局部最好的 为每个节点丢弃其他选项的选项。该算法既不完整也不是最优的。 回答你的问题是，你的解决方案被认为是贪婪的。

希望对您有所帮助。