Heuristic A* algorithm for N
I implementing an algorithm to solve the N-Puzzle problem. This algorithm will use other algorithms like A* and an Heuristic Bidirectional Search. In general this both algorithms give to me good results: A* worked finding solution for some problems with more that 50 moves, and i use the other for the other larger solutions.
The problem is the follow: i am using Manhattan Distance as heuristic for both algorithms and seem to work perfectly if the board has no repeated tiles. For example for 3x3 a classic 8-puzzle start board could be 1,2,3|4,5,6|7,8,0, with repeat tiles could be: 1,1,1|2,3,2|1,1,0. But in this case (when the board has repeated tiles) these algorithm works, but is not the same, and take even more time and give larger solutions. I modified the heuristic function and now each tile take the shortest path to any original position, for example if are several 2 each one will calculate the Manhattan distance to its nearest start position that have a 2.
Questions: Any knows any better heuristic for these problems? Is this Manhattan Distance Heuristic still admissible for the problem with repeated elements? Is this another problem different from N-Puzzle?
Thanks...
链接地址: http://www.djcxy.com/p/65560.html下一篇: N的启发式A *算法