AI课本八数码问题,我是用广度优先搜索,用Ismatch来记录状态是否已经遍历,个人感觉算法基本没错吧!可是编译程序的时候只要步数长一点(5步可以输出)就没有输出,用Debug调试显示是:Stack Overflow。我看了很久的代码,也没有搞懂需要在哪里做优化。希望大家看下给点意见。谢谢
[code="c"]#include
#include
#define M 362881
bool IsAnswer = false;
bool Ismatch[M];//标记是否已经遍历过
int tos,len;//队列指针tos,长度len
int tt[9]={1,1,2,6,24,120,720,5040,40320};
char dest[10];//目标状态
char tmap[10];
enum dir{up,down,left,right,none};
struct {
int dir;
int t;
}path[M];//记录路径
struct eightnum{
char map[10];
int x,y;
int father;
dir myDir;//父节点移动的方向
}num[M];
eightnum temp;
void back_push(eightnum _num)//push
{
strcpy(num[len].map, _num.map);
num[len].x = _num.x;
num[len].y = _num.y;
num[len].father = _num.father;
num[len].myDir = _num.myDir;
++len;
}
eightnum front_pop()//pop
{
tos++;
if(tos<len)
return num[tos];
else
printf("Wrong about the queue!\n");
}
int getHash(char _map[])//获取hash
{
int hash;
int k,l;
hash = 0;
int count = 0;
for(k=0;k<9;++k){
count = 0;
for(l = 0 ; l < k ;++ l){
if(_map[k]<_map[l])
count++;
}
hash += count*tt[k];
}
return hash;
}
int ReverseNum(char _map[])//逆序数
{
int k,l;
int count = 0;
for(k=0;k<9;++k){
for(l = 0 ; l < k ;++ l){
if(_map[k] == '0')
continue;
else if(_map[k]<_map[l])
count++;
}
}
return count;
}
void DFS(eightnum _tmp)//dfs
{
getHash(_tmp.map);
if(strcmp(_tmp.map,dest)==0){//find the answer
IsAnswer = true;
printf("Find the path!\n");
return;
}
else if(len>=M){//flow
printf("Above Flow!");
return ;
}
else{
//down
if( _tmp.x != 2){
strcpy(tmap,_tmp.map);
char m_tmp;
m_tmp = tmap[_tmp.x*3+_tmp.y];
tmap[_tmp.x*3+_tmp.y] = tmap[(_tmp.x+1)*3+_tmp.y];
tmap[(_tmp.x+1)*3+_tmp.y] = m_tmp;
int m_hash = getHash(tmap);
if(Ismatch[m_hash]==false){
Ismatch[m_hash] = true;
strcpy(temp.map,tmap);
temp.x = _tmp.x + 1;
temp.y = _tmp.y;
temp.father = tos;
temp.myDir = down;
back_push(temp);
}
}
//right
if( _tmp.y != 2 ){
strcpy(tmap,_tmp.map);
char m_tmp;
m_tmp = tmap[(_tmp.x)*3+_tmp.y];
tmap[(_tmp.x)*3+_tmp.y]= tmap[(_tmp.x)*3+_tmp.y+1];
tmap[(_tmp.x)*3+_tmp.y+1] = m_tmp;
int m_hash = getHash(tmap);
if(Ismatch[m_hash]==false){
Ismatch[m_hash] = true;
strcpy(temp.map,tmap);
temp.x = _tmp.x;
temp.y = _tmp.y+1;
temp.father = tos;
temp.myDir = right;
back_push(temp);
}
}
//up
if(_tmp.x != 0){
strcpy(tmap,_tmp.map);
char m_tmp;
m_tmp = tmap[_tmp.x*3+_tmp.y];
tmap[_tmp.x*3+_tmp.y] = tmap[(_tmp.x-1)*3+_tmp.y];
tmap[(_tmp.x-1)*3+_tmp.y] = m_tmp;
int m_hash = getHash(tmap);
if(Ismatch[m_hash]==false){
Ismatch[m_hash] = true;
strcpy(temp.map,tmap);
temp.x = _tmp.x - 1;
temp.y = _tmp.y;
temp.father = tos;
temp.myDir = up;
back_push(temp);
}
}
//left
if( _tmp.y != 0 ){
strcpy(tmap,_tmp.map);
char m_tmp;
m_tmp = tmap[_tmp.x*3+_tmp.y];
tmap[_tmp.x*3+_tmp.y]= tmap[(_tmp.x)*3+_tmp.y-1];
tmap[(_tmp.x)*3+_tmp.y-1] = m_tmp;
int m_hash = getHash(tmap);
if(Ismatch[m_hash]==false){
Ismatch[m_hash] = true;
strcpy(temp.map,tmap);
temp.x = _tmp.x;
temp.y = _tmp.y-1;
temp.father = tos;
temp.myDir = left;
back_push(temp);
}
}
}
eightnum m_tmp = front_pop();
DFS(m_tmp);
}
void myDisplay(char _map[]){//display
int ii;
for(ii=0;ii<9;++ii){
if(0==ii%3)
printf("\n");
if(_map[ii] == '0')
printf(" ");
else
printf("%c ",_map[ii]);
}
printf("\n-----------------------------\n");
}
int main()
{
char input[10] ;//输入
strcpy(input,"283164705");
strcpy(dest,"123804765");
int i;
tos = -1;
len = 0;
strcpy(temp.map,input);
printf("原始状态:\n");
myDisplay(input);
for(i=0;i<M;++i)
Ismatch[i] = false;
if( ReverseNum(input)%2 != ReverseNum(dest)%2){
printf("Not exist the answer!\n");
return 1;
}
for(i=0;i<10;++i){
if(temp.map[i] == '0'){
Ismatch[getHash(temp.map)] = true;
temp.x = i/3;
temp.y = i%3;
temp.father=-1;
temp.myDir = none;
back_push(temp);
break;
}
}
eightnum _tmp = front_pop();
DFS(_tmp);
int kk = 0;
if (IsAnswer){
int ff = tos ;
while( num[ff].father != -1){
path[kk].dir = num[ff].myDir;
path[kk].t = ff;
kk++;
//printf("%d",num[ff].myDir);
ff = num[ff].father;
}
}
for(i=kk-1;i>=0;--i)
{
if(path[i].dir==0){
printf("down-->");
myDisplay(num[path[i].t].map);
}
else if(path[i].dir==1){
printf("up-->");
myDisplay(num[path[i].t].map);
}
else if(path[i].dir==2){
printf("right-->");
myDisplay(num[path[i].t].map);
}
else if(path[i].dir==3){
printf("left-->");
myDisplay(num[path[i].t].map);
}
}
return 0;
}[/code]
ps:用“在link option中增加/stack”这种方法可以实现步长到27,我是想知道是否有更好的方法可以优化代码