Kir*_*rov 7 c++ algorithm artificial-intelligence solver
我想知道这两种算法的优点和缺点是什么.我想写AddEmUp C++解决了,但我不确定应该使用哪种(IDA或DFID)算法.
我找到的最好的文章就是这篇文章,但看起来太旧了 - '93.有没有新的？
我认为IDA*会更好,但是......？还有其他想法吗？
任何想法和信息都会有所帮助.
谢谢 !(:
编辑:关于IDA*的一些好文章和算法的良好解释？
EDIT2:或者那个游戏有一些很好的启发式功能？我不知道如何想到一些:/
Aph*_*hex 10
Russel和Norvig的书是对这些算法的极好参考,我会给larsmans一个虚拟的高五来表示它; 但是我不同意IDA*比A*更难以编程.我已经完成了一个项目,我必须编写一个AI来解决滑块拼图 - 熟悉的问题是有一个N×N网格的编号拼贴,并使用单个自由空间来滑动拼贴直到它们是按升序排列.
召回:
F(n) = g(n) + h(n).
TotalCost = PathCost + Heuristic.
g(n)=路径成本,从初始状态到当前状态的距离
h(n)=启发式,从当前状态到结束状态的成本估计.要成为一个可接受的启发式(从而确保A*的最优性),您无论如何都不能高估成本.有关过高估计/低估启发式对A*的影响的更多信息,请参阅此问题.
请记住,Iterative Deepening A*只是A*,对允许遍历的节点的F值有限制.这FLimit随着每次外部迭代而增加; 每次迭代都会加深搜索.
这是我的C++代码,它实现了A*和IDA*来解决前面提到的滑块拼图.您可以看到我使用std::priority_queue自定义Comparator将Puzzle状态存储在按F值优先排序的队列中.您还会注意到A*和IDA*之间的唯一区别是添加了一个FLimit检查和一个增加此值的外部循环FLimit.我希望这有助于阐明这个问题.