问题描述
AI课本八数码问题，我是用广度优先搜索，用Ismatch来记录状态是否已经遍历，个人感觉算法基本没错吧！可是编译程序的时候只要步数长一点（5步可以输出）就没有输出，用Debug调试显示是：Stack Overflow。我看了很久的代码，也没有搞懂需要在哪里做优化。希望大家看下给点意见。谢谢#include <stdio.h>#include <string.h>#define M 362881bool IsAnswer = false;bool Ismatch[M];//标记是否已经遍历过int tos,len;//队列指针tos,长度lenint 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];elseprintf("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 answerIsAnswer = true;printf("Find the path!n");return;}else if(len>=M){//flowprintf("Above Flow!");return ;}else{//downif( _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);}}//rightif( _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);}}//upif(_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);}}//leftif( _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[]){//displayint ii;for(ii=0;ii<9;++ii){if(0==ii%3)printf("n");if(_map[ii] == '0')printf(" ");elseprintf("%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;}ps:用“在link option中增加/stack”这种方法可以实现步长到27，我是想知道是否有更好的方法可以优化代码
解决方案
你这里面使用了递归没有 ？ 看你这种情况，引起堆栈溢出的可能性，有两种。一种是递归，一种就是内存没有往堆上分配，即没有使用malloc等内存分配函数。我认为递归引起的可能性更大。