某版主把原来我们用来讨论的帖子删除（不知何故），
我只好把最后几个帖子内容趁没有关闭浏览器的时候复制下来：
原帖子：https://bbs.bccn.net/viewthread.php?tid=239307&page=5

---------------------------------------------------------------------------

StarWing83

得啦，二星就够我麻烦的，说实在的是产生心理阴影了……哈哈~~打击一下liyanhong同学，希望他把133给做出来~~
其实我不提交的原因是，我没有写策略的失败回溯，首先如果我定义的策略失败了，是肯定TLE的，32层的DFS，一旦不是一条路线直通4^32的回溯会很吓人的，其次，如果策略成功了，直接单通的线性算法可以过的话，这也不是三星题了。这就是我不敢提交的原因。

PS 直接策略单通的话，就退化到贪婪而不是A*了……

---------------------------------------------------------------

rootkit:

瘟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.

---------------------------------------------------------------

StarWing83

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

---------------------------------------------------------------

StarWing83

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

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

---------------------------------------------------------------

蓝色线段树

0.4秒

---------------------------------------------------------------

各位继续吧
SW刚刚问087654321的解是不是ddrruullddrruullddrruullddrr
答案是正确的

[[it] 本帖最后由 蓝色线段树 于 2008-10-23 17:34 编辑 [/it]]