main.cpp

实现八数码算法

#include <iostream>
#include "eightdigit.h"
#include <ctime>  
#include"Priority_Queue.h"  
using namespace std;  

int main()
{
	int num[9];
	int node_num;//生成节点数
	clock_t start,finish;
	int step;//扩展次数
	
	while(1){
		EightDight *OPEN=NULL;//OPEN表
		EightDight *CLOSED=NULL;

		Priority_Queue q;

		bool hash[362880];
		for(int i=0;i<362880;i++)
			hash[i]=false;
		cout<<"please input the initial state(CTRL+Z to end):"<<endl;
		for(int i=0;i<9;i++)
			cin>>num[i];
		char Hn;
		cout<<"input W to select Wn,P to select Pn: "<<endl;
		cin>>Hn;
		EightDight first(num),final(targetNum);
		if(!first.canSolve(targetNum)){
			cout<<"no solution!"<<endl;
			continue;
		}
		hash[first.hashval()]=true;

		EightDight *minFNode=&first;

		start=clock();
		node_num=0;
		step=0;
		bool solve=false;

		EightDight *temp;
		while(minFNode!=NULL){
			step++;
			for(int i=0;i<4&&!solve;i++){
				bool succ;
				temp=new EightDight(minFNode->EDnum);
				switch(i){
				case 0:
					succ=temp->moveUp();
					break;
				case 1:
					succ=temp->moveDown();
					break;
				case 2:
					succ=temp->moveLeft();
					break;
				case 3:
					succ=temp->moveRight();
					break;
				}
				if(succ){
					temp->parent=minFNode;
					if(*temp==final){
						minFNode=temp;
						solve=true;
						break;
					}
					int hv=temp->hashval();
					if(hash[hv]==false){
						temp->getEvalue1();
						temp->next=OPEN;
						OPEN=temp;
						q.Push(temp);
						node_num++;
						hash[hv]=true;

					}
					else {
						delete temp;
						temp=NULL;
					}
				}
				else {
					delete temp;
					temp=NULL;
				}
			}
			if(solve) break;
			minFNode=q.Pop();
		}
		finish=clock();
		node_num++;
		minFNode->display();
		cout<<"number of nodes:"<<node_num<<endl;
		cout<<"count of steps:"<<step<<endl;
		cout<<"average node:"<<node_num/step<<endl;
		cout<<"time used:"<<1000*double(finish-start)/double(CLOCKS_PER_SEC)<<"ms"<<endl;
		/*delete minFNode;
		temp=OPEN;
		while(temp!=NULL){
			OPEN=OPEN->next;
			temp->next=NULL;
			delete temp;
			temp=OPEN;
		}
		temp=CLOSED;
		while(temp!=NULL){
			CLOSED=CLOSED->next;
			temp->next=NULL;
			delete temp;
			temp=CLOSED;
		}*/

	}

	return 0;
}