我说之前project1运行总有问题,果然这个优先队列用法不了解出错了,可惜现在才看到,要不8puzzle应该能够正确完成。记下来
priority_queue只会在push的时候进行排序,因此,先push,再对元素进行修改,并不会改变priority_queue的排序。举一个例子
priority_queue<s*, vector<s*>, cmpLarge> openlist;s* s1 = new s;
s* s2 = new s;
s1->a = 1;
s1->b = 1;
s2->a = 2;
s2->b = 2;
openlist.push(s1);
openlist.push(s2);
cout << openlist.top()->a << " " << openlist.top()->b << endl;
s2->a = 0;
s2->a = 0;
cout << openlist.top()->a << " " << openlist.top()->b << endl;
openlist是针对s->a+s->b进行排序,程序得到的结果是
1 1
1 1
这说明我们在对openlist进行push了s1和s2之后,先调用一次openlist.top(),会返回s1,然后我们对s2进行修改,让它的a+b值为0,但是第二次调用openlist.top()时,得到的依然是s1。

在伪代码中,在openlist.push()之前,应该先计算好successors的g和h值,再对它进行push。否则openlist.top()可能返回的不是g+h最小的那个节点。