为什么A *是更快，如果我使用4xManhattan的距离作为启发式的15拼图 [英] Why A* is faster if i use 4xManhattan Distances as Heuristic for 15-Puzzle

问题描述

我已经解决了15拼图实施的A *算法。我做了一个研究发现了一些可行或可采启发式，寻找一个快速的解决方案，我发现，使用4 *曼哈顿距离作为启发式总能解决所有的15拼图在不到一秒钟。我想这和有效地工作。我试图找到一个答案，但我不能找到它。

任何人能解释一下吗？

解决方案

4 *曼哈顿距离是不容许的启发，这使得算法表现得更加靠近贪婪最好先（这里的算法选择哪个节点仅仅基于开发启发式功能）。这使得算法有时是

解决方案

的对$ PFER深入和探索过的广度和最优性。

我们的想法是类似于发生在 A * -Epsilon ，其中你让A *开发没有最优节点达到一定的约束，以加速你的算法，其实 - 我怀疑你会得到相同（或相似的结果），如果你运行一个* -Epsilon曼哈顿距离和小量= 3 。 （如果我是正确的，这会让你找到由限定的改进的启发式解决方案4 *优化，其中最优的最优路径的长度）

I have implemented an A* algorithm for solving the 15-puzzle. I made a research for finding some viable or admissible heuristics, looking for a fast solution, and i find that using 4*Manhattan Distance as heuristic always solve any 15-puzzle in less than a second. I tried this and effectively works. I tried to find a answer for that but i cant find it.

Any one can explain this?

解决方案

4* manhattan distance is not admissible heuristic, this makes the algorithm behave "closer" to greedy best first (where the algorithm chooses which node to develop solely based on the heuristic function). This makes the algorithm sometimes prefer depth of solutions and exploration over breadth and optimality.

The idea is similar to what happens in A*-Epsilon, where you allow A* to develop none optimal nodes up to a certain bound in order to speed up your algorithm, Actually - I suspect you will get the same (or similar results) if you run A*-Epsilon with Manhattan distance and epsilon = 3. (If I am correct, this makes the solution you find in the modified heuristic bounded by 4*OPTIMAL, where OPTIMAL is the length of the optimal path)

这篇关于为什么A *是更快，如果我使用4xManhattan的距离作为启发式的15拼图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！