pet*_*ter -2 algorithm design-patterns greedy
我的直觉和假设是每当我们不能使用贪婪时,那么A*将成为可行的方式,但我并非100%肯定.我需要更多关于如何识别和发现A*算法的示例和模式.
有人可以给出一些特殊的极端情况,当你第一次看到它并且你知道这不会贪婪或它必须是A*甚至没有打扰尝试.
Gar*_*ees 5
通常,术语贪婪用于描述不回溯的算法.这些是通过最大化启发式(通常是相当"本地"的)来做出选择的算法,然后不再重新考虑该选择.把一个贪婪的算法想象成一个挑选蛋糕然后立即吃掉它的人,而不是把它放在一边并调查另一个蛋糕是否会更好.
相比之下,A*是一种回溯算法:它可能在某种程度上探索选择,但之后能够放弃这些选择并尝试其他可能性.
因此,如果您的问题具有"死胡同"(局部最大值),而无法在解决方案方面取得进一步进展,那么贪婪算法很可能不适用.但这并不一定意味着A*及其变体是您唯一的选择.还有许多其他类型的搜索算法使用不同的技术来逃避死胡同:模拟退火,蒙特卡罗树搜索,禁忌搜索,粒子群优化,......
归档时间：
13 年，4 月 前
查看次数：
884 次
最近记录：