…………还是不对……如果是真的估价函数c()可以这样，但是使用的是评估函数^c()，这个函数不一定具有离目标越近，函数值就越小的特点……所以这样很容易就无解了……
比如选择评估函数是“每个数码到最终位置需要走的步数”，则原始状态132458769评估为6+0
，它的两个子状态：
    l 1+6 132458796
    u 1+6 132459768

居然都大于6……
如果这里都不选，那么自然就无解了，如果任意选一个，因为是递归算法，那么在以后也是同样在相同层数的子状态里面选择，如果这样，那么加上去的层数就没有意义了：因为这个层数唯一的意义就是和参加比较的母状态进行比较……

郁闷……后天考试，我先复习再说，这个东西考试完了再说。

不好意思，rootkit~~

我对A*的理解就是通过启发函数（而不是估价函数）在搜索中智能选择最有可能的分支。
这么说我现在的算法还不是A*，只是智能化搜索而已，因为如果不使用层数，那么只是单纯的估价函数，而不是启发函数，但是怎么把层数应用进去，我还没想好。

24L我保存了，今天晚上再看。

在打开一个新节点时如果有两个估值相同的节点，随便选一个。
你对A*的误解在于没有被open的节点会停留在open表中，不会丢弃。如这里的：
l 1+6 132458796
u 1+6 132459768
如果选择打开节点l，将l的子节点加入open表，u节点在其父节点产生u时就把u加入open表了，现在任然在里头。新打开的l节点的子孙节点和以前的节点一起选择一个估值函数最小的节点作为下一个打开的节点。

你还是再看看这里的第4，6步，看一个节点何时加入open表，何时移出：

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.

启发函数和估价函数有什么区别？或许叫它“决策函数”更合适，因为这个函数决定了每一步的决策。
你不要陷入字眼里去了，名字各有各的叫法，还各有各的翻译方法。关键是算法思想。

我明白了，我的错误在于每个判断子过程定义的是一个单独的open表………………啊……傻了……

就问最后一个问题，你给的示例的估值函数是“不在正确位置的数字的数目”，给出的283164705估值是4，可是怎么会是4呢？？？
不在正确位置的数字用1表示，是110111011，我的程序算来是7……

恩，有完整的思路了，准备用priority_queue重新写整个代码…………

考试完再说……

楼上你试试把你的A*代码提交在第100题那里试试看

越看越看不懂了,看的如同天书一样啊

按照rootkit的说法，我的那个代码应该不算A*，而只是智能导向的深度优先——因为每次选择子状态的时候，是仅仅从当前的子节点中选择的。

我准备写个treap以后再完成真正的A*……

现在嘛……还是考试重要，嘿嘿~

说明一下为什么要写treap：
首先应该有一个优先队列，这样才能每次选择最优的子节点来扩展。其次在扩展的时候，需要去除掉重复的状态。
treap本身就是一个基于优先级的堆，因此是个优先队列，同时因为它也是一颗排序树，刚刚好可以用来查找去重，所以对待这道题，treap是最好的数据结构。

当然可以用priority_queue+set的形式，这样就用不着自己写treap了，不过会占用两倍的内存。

第二个办法是用map，map是用红黑树实现的，查找可以在对数时间内完成，而且其begin()就是最小元素，可以当作优先队列使用，但是因为其并没有规定begin一定指向最小元素，使用map可能会导致一些可移植的问题，而最重要的是——map只有一个key，但是现在的需求是需要两个key……

[[it] 本帖最后由 StarWing83 于 2008-10-24 10:27 编辑 [/it]]

不是A*也不要紧啦，你先试试提交一下嘛，可能结果会让你觉得意外的