………………这么说，贪婪是肯定过不了了……

改代码去……

我都说了不一定啦。。。。

啥是8数码问题，解释解释、

瘟38说的我怎么看不懂，难道有比A*还要高效的算法？
如果你的A*效率低，有太多的回溯，就是你估值函数没有设计好。

A General Graph-Searching Algorithm

1. Create search tree Tr consisting only of the start node (root) n0. Put n0 on an ordered list called OPEN.
2. Create empty list called CLOSED.
3. If OPEN is empty, exit with failure.
4. Move the first node from OPEN, called n, to CLOSED.
5. If n is a goal node, exit with success; the solution is the path from n to n0 along the edges in Tr.
6. Expand node n by generating a set M of successors and connect them to n. Also put the members of M on OPEN.
7. Reorder the list OPEN according to a specific rule.
8. Go to step 3.

这是通用搜索模式，在第七步中：
1 如果把新open的节点放在open表前面就是DFS
2 如果把新open的节点放在open表后面就是BFS
3 如果把新open的节点按其h(n)+g(n)值大小按递增序插入open表就是best-first search,也叫A*。

8数码问题的A*算法应该这样设置估值函数：
f’(n) = depth of n in the tree + number of digits in the puzzle in incorrect position.

蓝色，087654321这组数据你要花多长时间？

A*是很快，快的原因是智能化的搜索，所以A*和A*本身都是不同的，差别在于估价函数。选择的估价函数的好坏，直接影响到了算法本身的效率。有些题目，选择了巧妙而良好的估价函数甚至可以使算法简化为贪婪或者DP，但A*难也就难在估价函数的选择……

看来书上给出的这个函数并不好，087654321应该有解，但是我算了几分钟还是没有出解……

0.4秒

晕……《计算机算法》给出的16数码解法是面向决策的，《算法艺术》给出的解法是面向状态的……我综合一下再说……

我知道原因了，我没有判断重复到达统一状态的不同路线的f值，所以重复了，算这个解的时候出现了环……

继续Coding……

这是两种不同的估值函数选择，区别很明显

For the Eight-puzzle, it seems like a good idea to expand those nodes first that lead to configurations similar to the goal state.
In our first attempt, we will simply define f’ as the number of digits in the puzzle that are not in the correct (goal) position yet.
第一次不大聪明的尝试：

You see that with this simple function f’ the algorithm is still likely to perform unnecessarily many steps.
We should increase the “cost” of searches in greater depth to make the algorithm avoid them.
To achieve this, we simply add the current depth of a node to its f’-value.
Now f’(n) = depth of n in the tree + number of digits in the puzzle in incorrect position.
Let us try again!
明智的选择：