用VS2012做A*算法解决8数字推盘问题，运行完后跳出Debug Assertion Failed这是哪出问题了？
代码如下：
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <fstream>
using namespace std;
class Node {
public:
int a[9]; //position of the 8-puzzle
Node *from; //pointer to parent node
int f, g, h; //cost evaluation
Node (int* at, Node* fromt, int gt);
void printNode ();
void cal (); //calculate the value of h and f
bool operator < (Node &other) { return f < other.f; } //operator overloading for the use of "sort" function
};
Node::Node (int* at, Node* fromt, int gt)
{
for (int i=0; i<9; i++) a[i] = at[i];
from = fromt;
g = gt;
cal();
}
void Node::printNode()
{
for (int i = 0; i < 9; i++) {
if ( a[i] == 0 ) cout << ' ' << ' ';
else cout << a[i] << ' ';
if ( (i+1)%3 == 0 ) cout << endl;
}
cout << endl;
}
void Node::cal()
{
h = 0;
if( a[0]!=1 ) h++; if( a[1]!=2 ) h++; if( a[2]!=3 ) h++;
if( a[3]!=8 ) h++; if( a[5]!=4 ) h++;
if( a[6]!=7 ) h++; if( a[7]!=6 ) h++; if( a[8]!=5 ) h++;
f = g + h;
}
// check if the node is in the list or not, if the node is in the list, let poiter c point to it
bool checkNode (int* a, vector<Node*> b, Node* &c)
{
for (int i = 0; i < b.size(); i++) {
bool temp = true;
for (int j = 0; j < 8; j++) {
if (a[j] != b[i]->a[j]) {
temp = false;
break;
}
}
if (temp) {
c = b[i];
return true;
}
}
return false;
}
//one move
void operation (int foo, int bar, vector<Node*> &open, vector<Node*> &closed, int &new_g)
{
int temp[9]; Node *temp3 = NULL;
for ( int i=0; i<9; i++ ) { temp[i] = open.front()->a[i]; }
swap(temp[foo], temp[bar]);
if ( !checkNode(temp, closed, temp3) ) { //if new node is not in the closed list do the following
if ( !checkNode(temp, open, temp3) ) { //if new node is not in the open list do the following
Node* temp2 = new Node(temp, open.front(), new_g); //add the new node into the open list
//cout << "add new node into open list" << endl;
//if( temp2->h == 0 ) temp2->f = 0; //check if the new node is the destination node
open.push_back(temp2);
} else { //if new node is in the open list do the following
if (new_g < temp3->g) { //if old g is greater than new g, update f, change parent node to current
temp3->g = new_g;
temp3->cal();
temp3->from = open.front();
//cout << "update node already in open list" << endl;
}
}
} //else cout << "node is already in closed list, do nothing" << endl;
//cout << "operation done" << endl;
}
// implementation of a* pathfinding algorithm
Node* aStar (Node* start, vector<Node*> &open, vector<Node*> &closed)
{
open.push_back( start );
while ( !open.empty() ) {
//put the node which has minimum f into closed list, check if it is the destination node
closed.push_back( open.front() );
if ( open.front()->h == 0 ) return open.front();
int new_g;
new_g = open.front()->g + 1;
//determine the position of 0
int positionZero;
for (int i=0; i<9; i++) {
if (open.front()->a[i] == 0) {
positionZero = i;
break;
}
}
//extend current node according to the position of 0
switch ( positionZero ) {
case 0:
operation(0, 1, open, closed, new_g);
operation(0, 3, open, closed, new_g);
break;
case 1:
operation(1, 0, open, closed, new_g);
operation(1, 2, open, closed, new_g);
operation(1, 4, open, closed, new_g);
break;
case 2:
operation(2, 1, open, closed, new_g);
operation(2, 5, open, closed, new_g);
break;
case 3:
operation(3, 0, open, closed, new_g);
operation(3, 4, open, closed, new_g);
operation(3, 6, open, closed, new_g);
break;
case 4:
operation(4, 1, open, closed, new_g);
operation(4, 3, open, closed, new_g);
operation(4, 5, open, closed, new_g);
operation(4, 7, open, closed, new_g);
break;
case 5:
operation(5, 2, open, closed, new_g);
operation(5, 4, open, closed, new_g);
operation(5, 8, open, closed, new_g);
break;
case 6:
operation(6, 3, open, closed, new_g);
operation(6, 7, open, closed, new_g);
break;
case 7:
operation(7, 4, open, closed, new_g);
operation(7, 6, open, closed, new_g);
operation(7, 8, open, closed, new_g);
break;
case 8:
operation(8, 5, open, closed, new_g);
operation(8, 7, open, closed, new_g);
break;
default:
break;
}
open.erase( open.begin() ); //cout << "erase successfully" << endl;
sort( open.begin(), open.begin()+open.size() ); //cout << "sort successfully" << endl << endl;
}
return NULL;
}
int main ()
{
cout << "This application will find a solution to the \n8-puzzle with the starting node below " << endl << endl;
//build up an OPEN list and a CLOSED list
vector<Node*> open;
vector<Node*> closed;
//initialize the starting node
int temp[9];
ifstream sample_file;
sample_file.open ("sample.txt");
if ( !sample_file ) {
cout << "Can not open file!" << endl;
return 1;
}
for (int i=0; i<9; i++) sample_file >> temp[i];
sample_file.close();
/*for (int i=0; i<9; i++) temp[i] = i;
srand( time(NULL) );
for (int i=0; i<15; i++) {
int j = rand() % 5;
int k = rand() % 4 + 5;
swap( temp[j], temp[k] );
}*/
Node* start = new Node( temp, NULL, 0 );
cout << "Starting node: \n" << endl;
start->printNode();
//search and print a solution
cout << "Searching for solution, please wait... ";
Node* dest = aStar (start, open, closed);
if( dest != NULL ) {
stack<Node*> solution;
while (dest != NULL) {
solution.push(dest);
dest = dest->from;
}
cout << "\n\nSolution found!\n\n";
while (!solution.empty()) {
solution.top()->printNode();
solution.pop();
}
} else cout << "\n\nCan not find solution to the 8-puzzle with the above starting node!\n";
//delete all generated nodes
for (int i=0; i<open.size(); i++) delete open[i];
for (int i=0; i<closed.size(); i++) delete closed[i];
int foo; while ( (foo = getchar()) != EOF ) putchar (foo);
system("pause");
return 0;
}