我的直觉和假设是，只要我们不能使用贪婪，那么 A* 将是要走的路，但我不是 100% 确定。我需要更多关于如何识别和发现 A* 算法的示例和模式。
有人可以给出一些特殊的极端情况，当你第一次看到它时，你就知道这不会是贪婪的，或者它必须是 A* 甚至不用费心去尝试。
问问题
994 次
3 回答
6
通常，术语贪婪用于描述不回溯的算法。这些算法通过最大化启发式（通常是相当“本地”的）做出选择，然后永远不会重新访问该选择。将贪心算法想象成一个人挑选一个蛋糕然后马上吃掉它，而不是把它放在一边并调查另一个蛋糕是否更好。
相比之下，A*是一种回溯算法：它探索选择，可能在一定深度，但随后能够放弃这些选择并尝试其他可能性。
因此，如果您的问题有“死胡同”（局部最大值），无法进一步解决问题，那么贪心算法很可能不适合。但这并不一定意味着 A* 及其变体是您唯一的选择。还有许多其他类型的搜索算法使用不同的技术来摆脱死胡同：模拟退火、蒙特卡洛树搜索、禁忌搜索、粒子群优化......
于 2012-09-14T17:25:41.133 回答
3
贪心算法失败的典型案例是在目标附近死胡同的走廊情况。如果您对到目标的距离有启发式算法，那么贪心算法将沿着走廊走下去，因为这些位置离目标更近。例如，
_ _ _ _ _ _ _ _ _ _
| . S . . . . | G |
| . _ _ _ _ _ | . |
| . . . . . . . . |
| _ _ _ _ _ _ _ _ |
请注意，代理必须“远离”目标 (G) 才能从起点 (S) 到达目标，这不是贪心算法所建议的。
于 2012-09-14T17:06:29.043 回答
0
A* 是单源单目的地最短路径算法。
当您可以将手头的问题作为最短距离问题提出时，您可以使用它，并且您可以找到不会高估的启发式方法（例如使用欧几里得距离）。
于 2012-09-14T22:27:47.627 回答