1110.txt

集合了SOJ（四川大学ACM在线评测系统）众多经典题目的详细解题报告

15 Puzzle
题意：
    Problem
这就是古老而又经典的15数码难题：
在4*4的棋盘上，摆有15个棋子，每个棋子分别标有1-15的某一个数字。棋盘中有一个空格，空格周围的棋子可以移到空格中。现给出初始状态和目标状态，要求找到一种移动步骤最少的方法。

解法：
    此题曾在babble的搜索专题中讨论过，当时没有理解到，所以又重新看了一遍。此题可用一般的通用方法即A*加广度搜索，但时间效率很低，且需要限制结点个数。我参考了bbb的深度搜索算法+A*，即所谓的IDA*，使得效率提高，其优点就是在限制的范围内来寻找最优值，若找到则结束，否则扩大搜索范围，这样扩大范围而不是单纯地全搜索使得搜索结点个数大幅度减少，具体讨论参见蓝色星空ACM_ICPC版！！