Graytom 2011-04-04 02:02
浏览 421
已采纳

AI八数码问题 Stack Overflow

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,我是想知道是否有更好的方法可以优化代码

  • 写回答

1条回答 默认 最新

  • turing-complete 2011-04-04 10:46
    关注

    你这里面使用了递归没有 ?

    看你这种情况,引起堆栈溢出的可能性,有两种。一种是递归,一种就是内存没有往堆上分配,即没有使用malloc等内存分配函数。

    我认为递归引起的可能性更大。

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 求差集那个函数有问题,有无佬可以解决
  • ¥15 【提问】基于Invest的水源涵养
  • ¥20 微信网友居然可以通过vx号找到我绑的手机号
  • ¥15 寻一个支付宝扫码远程授权登录的软件助手app
  • ¥15 解riccati方程组
  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题