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

问题描述

我已经实现了一个 A* 算法来解决 15 拼图.我进行了一项研究，以寻找一些可行的或可接受的启发式方法，寻找快速解决方案，我发现使用 4*曼哈顿距离作为启发式方法总是可以在不到一秒的时间内解决任何 15 难题.我试过这个并且有效地工作.我试图找到答案，但我找不到.

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.

谁能解释一下?

推荐答案

4* manhattan distance 是不可接受的启发式算法，这使得算法首先表现得更接近"贪婪(算法选择开发哪个节点完全基于启发式函数).这使得算法有时更喜欢解决方案的深度和探索，而不是广度和最优性.

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.

这个想法类似于 A*-Epsilon 中发生的事情，其中你允许 A* 开发非最优节点达到某个界限以加速你的算法，实际上 - 我怀疑如果你使用曼哈顿距离和 运行 A*-Epsilon，你会得到相同(或相似的结果)epsilon = 3.(如果我是对的，这使得您在以 4*OPTIMAL 为界的修改启发式中找到的解决方案，其中 OPTIMAL 是最佳路径的长度)

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)

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