钉接龙
使用Python3.4和numpy 1.9.2编写
搜索策略分析
在所有搜索策略中,深度优先搜索(DFS)到目前为止是最好的。 我已经预料到它的性能将比广度优先搜索(BFS)好得多:所有可用的解决方案都出现在深度13处,而且数量很多。 我没想到的是A *和IDA *的表现如何。 在我看来,我们正在测试的启发式方法并不理想,但我认为它们至少能够像DFS一样快地找到解决方案。 但是实际上,情况恰恰相反:A *发现的解决方案仅比BFS快一点,并且比不了解情况的DFS慢了几个数量级。 经过更仔细的检查,这是由于以下事实:正在使用的试探法对性能的预测非常差。
将DFS应用于钉式拼图之所以特别有效,是因为拼图的性质解决了处理DFS时通常会出现的大多数“问题”:即完整性和最优性。 关于完整性,大多数搜索空间中的朴素DFS可能很容易陷入陷入相同状态的循环中。 在挂钩难题中,情况并非如此:尽管存在
评论0
最新资源