请教《智能拼图游戏》搜索算法引起内存不足的问题。

问题描述：
本人现研究《智能拼图游戏》，就是我们常玩的那种给出一个打乱的图，让你排列成完整的格式，本程序已完成输入n*m格局的数据后，自动给出最快的移动步骤；但是当n,m数字达到4*4，并且移动步数教多时，会产生内存不足问题。以下为具体程序说明。
（以数字代表图片）
数字目标格式（以3*3格局为例）：
1 2 3
4 5 6
7 8 0
譬如某初始格式为：
1 2 3
4 5 6
0 7 8，
则经过两步移动即可找到结果：
------------
1 2 3
4 5 6
7 0 8
------------
1 2 3
4 5 6
7 8 0
-----------本程序采用如下流程：
1：录入初始结构结点h，p=h;
2：判断p是否为目标结点，是则结束，否则执行步骤3
3：p插入到已访问结点二叉搜索树stree
4：生成p结点的4个子结点(上下左右移动)pu,pd,pl,pd
5：分别判断pu,pd,pl,pd是否已经存在于在stree中，若无则将p(?)插入到stree中，并插入到待扩展结点队列queue，若已经存在则放弃该点。
6：读取queue队头结点front，p=front，执行步骤2该程序执行后的某些效率和结果如下：
运行环境：intel Pentium M 1.5GHZ    256M DDR   WIN XP
布局
1  2   3  4
5  6  7  8
9 10  11 12
13 14 15  0
0 1 0 (移动次数产生结点数运行时间（毫秒）)
--------------------------------------------
1  2   3  4
5  6  7  8
9 10  11 0
13 14 15 12
1 4 0 (移动次数产生结点数运行时间（毫秒）)
-----------------------------------
1  2   3  4
5  6  7  0
9 10  11 8
13 14 15 12
2 10 0(移动次数产生结点数运行时间（毫秒）)
-----------------------------------
1  2   3  0
5  6  7 4
9 10  11 8
13 14 15 12
3 17 0(移动次数产生结点数运行时间（毫秒）)
--------------------------------------------
1  2   0  3
5  6  7 4
9 10  11 8
13 14 15 12
4 88 0(移动次数产生结点数运行时间（毫秒）)
---------------------------------------------
1  2   7  3
5  6  0 4
9 10  11 8
13 14 15 12
5 208 0(移动次数产生结点数运行时间（毫秒）)
------------------------------------
1  2   7  3
5  6  11 4
9 10  0 8
13 14 15 12
6 396 10(移动次数产生结点数运行时间（毫秒）)
-----------------------------------------------
1  2   7  3
5  6  11 4
9 0  10 8
13 14 15 12
7 1155 10(移动次数产生结点数运行时间（毫秒）)
--------------------------------------
1  2   7  3
5  6  11 4
0 9  10 8
13 14 15 12
8 2164 20(移动次数产生结点数运行时间（毫秒）)
-------------------------------------------
1  2   7  3
0  6  11 4
5 9  10 8
13 14 15 12
9 2983 30(移动次数产生结点数运行时间（毫秒）)
-------------------------------------------------
1  2   7  3
6  0  11 4
5 9  10 8
13 14 15 12
10 11716 240(移动次数产生结点数运行时间（毫秒）)
---------------------------------------------------
1  2   7  3
6 9  11 4
5 0  10 8
13 14 15 12
11 18208 301(移动次数产生结点数运行时间（毫秒）)
---------------------------------------
1  2   7  3
6 9  11 4
5 10  0 8
13 14 15 12
12 46830 742(移动次数产生结点数运行时间（毫秒）)
--------------------------------------------------
1  2   7  3
6 9  11 4
5 10  8 0
13 14 15 12
13 75738 1242(移动次数产生结点数运行时间（毫秒）)
----------------------------------------------------
1  2   7  3
6 9  11 4
5 10  8 12
13 14 15 0
14 90774 1603(移动次数产生结点数运行时间（毫秒）)
----------------------------------------------------
1  2   7  3
6 9  11 4
5 10  8 12
13 14 0 15
15 254378 4646(移动次数产生结点数运行时间（毫秒）)
--------------------------------------------
1  2   7  3
6 9  11 4
5 10  8 12
13 0 14 15
16 350476 6209(移动次数产生结点数运行时间（毫秒）)
--------------------------------------------
1  2   7  3
6 9  11 4
5 10  8 12
0 13 14 15
17 748696 31515(移动次数产生结点数运行时间（毫秒）)
-------------------------------------------
1  2   7  3
6 9  11 40
10  8 12
5 13 14 15
18 1190478 810656(移动次数产生结点数运行时间（毫秒）)
-------------------------------------------
1  2   7  3
0 9  11 4
6 10  8 12
5 13 14 15
19 内存不足内存不足(移动次数产生结点数运行时间（毫秒）)
-----------------------------------------------------内存不足时的提示：“虚拟内存不足，请重新分配.....”
问题：如何有效解决数据量大和移动步数多时内存不足的问题？附完整源代码如下：

解决方案 »

免费领取超大流量手机卡，每月29元包185G流量+100分钟通话, 中国电信官方发货

#include<malloc.h>
#include<iostream.h>
#include<windows.h>
#define rows 4 //总行数
#define cols 4 //总列数
typedef struct node
{
int a[rows][cols];
node *u; //上分支
node *d; //下分支
node *l; //左分支
node *r; //右分支
node *p; //父结点
};
typedef struct queue
{
node *data;
queue *next;
};
typedef struct stree //二叉搜索树
{
node *data;
stree *left;
stree *right;
};int Tcnt=1; //产生结点数
void search(node * &h); //广度优先搜索
void tcopy(node * &h,node * &t); //将h中的数组a复制到t中
void move_up(node * &t,int i,int j); //上移
void move_down(node * &t,int i,int j); //下移
void move_left(node * &t,int i,int j); //左移
void move_right(node * &t,int i,int j); //右移
void print(node * h); //打印h中的数组
bool succ(node *np); //判断np中的数组是否已经符合要求
bool IsExist(stree * &shead,node *t); //判断二叉搜索树shead中是否已经存在结点t，不存在则插入该结点
int IsSame(node *p1,node *p2); //判断两个结点p1,p2中的数组排列是否相等p1<p2:-1  p1=p2:0  p1>p2: 1
void main()
{
DWORD Dstart,Dend;
node *h;
h=new node;
//******************注意**注意**注意**注意**注意**************
//在此输入原始格式
h->a[0][0]=1;h->a[0][1]=2 ;h->a[0][2]=3;h->a[0][3]=0;
h->a[1][0]=5;h->a[1][1]=6;h->a[1][2]=7;h->a[1][3]=4;
h->a[2][0]=9;h->a[2][1]=10;h->a[2][2]=11;h->a[2][3]=8;
h->a[3][0]=13;h->a[3][1]=14;h->a[3][2]=15;h->a[3][3]=12;
//******************注意**注意**注意**注意**注意************** h->u=NULL; h->d=NULL; h->l=NULL; h->r=NULL; h->p=NULL;

Dstart=GetTickCount(); //运行前的时间
cout<<"Start:"<<Dstart<<endl<<"正在搜索......"<<endl;
search(h);
Dend=GetTickCount(); //运行后的时间
cout<<"Start:"<<Dstart<<endl;
cout<<"End;"<<Dend<<endl;
cout<<"Elapsed:"<<Dend-Dstart<<endl;}void search(node * &h)
{
queue *front,*rear; //队头,队尾
queue *qq,*Qtemp,*Qfront; //Qtemp:删除队列中已访问结点时使用
stree *shead; //二叉搜索树根结点
node *tu,*td,*tl,*tr;
node *np;
int i,j,k1,k2,temp; front=new queue; //生成待访问结点队列
front->data=h; front->next=NULL;
rear=front; np=front->data; shead=new stree; //生成二叉搜索树
shead->data=np;
shead->left=NULL; shead->right=NULL; while(succ(np)==false) //尚未找到结果
{

for(i=0;i<rows;i++) //找到0所在位置
for(j=0;j<cols;j++)
{
if(np->a[i][j]==0)
{
k1=i;k2=j;
}
}
i=k1; j=k2; if(i!=rows-1) //0不在最后一行，可以上移
{
tu=new node;
tcopy(np,tu);
move_up(tu,i,j);
if(IsExist(shead,tu)==false) //tu在二叉搜索树中不存在
{
np->u=tu;
tu->p=np;
qq=new queue;
qq->data=tu; qq->next=NULL;
rear->next=qq; rear=qq; //新结点插入待访问队列
Tcnt++;
}
else
{
delete tu;
} } if(i!=0) //0不在第一行，可下移
{
td=new node;
tcopy(np,td);
move_down(td,i,j);
if(IsExist(shead,td)==false) //tu在二叉搜索树中不存在
{
np->d=td;
td->p=np;
qq=new queue;
qq->data=td; qq->next=NULL;
rear->next=qq; rear=qq; //新结点插入待访问队列
Tcnt++;
}
else
{
delete td;
} }
if(j!=cols-1) //0不在最后一列，可以左移
{
tl=new node;
tcopy(np,tl);
move_left(tl,i,j);
if(IsExist(shead,tl)==false) //tu在二叉搜索树中不存在
{
np->l=tl;
tl->p=np;
qq=new queue;
qq->data=tl; qq->next=NULL;
rear->next=qq; rear=qq; //新结点插入待访问队列
Tcnt++;
}
else
{
delete tl;
} } if(j!=0) //0不在第一列，可右移
{
tr=new node;
tcopy(np,tr);
move_right(tr,i,j);
if(IsExist(shead,tr)==false) //tu在二叉搜索树中不存在
{
np->r=tr;
tr->p=np;
qq=new queue;
qq->data=tr; qq->next=NULL;
rear->next=qq; rear=qq; //新结点插入待访问队列
Tcnt++;
}
else
{
delete tr;
} }

qq=front;
front=front->next; if(front==NULL)
{
cout<<"该格式无解！"<<endl;
np=NULL;
break;
} np=front->data;
delete qq; //删除无用的队列结点
} int cnt=0; //移动步数记数器
while(np)
{
cout<<cnt++<<":"<<endl;
print(np);
np=np->p;
}
cout<<"产生结点数："<<Tcnt<<endl;}bool succ(node *np) //当前结果匹配成功
{
int i,j,k=1;
for(i=0;i<rows-1;i++) //1~n-1行
for(j=0;j<cols;j++)
{
if(np->a[i][j]!=k) return false;
k++;
}

i=rows-1; for(j=0;j<cols-1;j++) //n行
{
if(np->a[i][j]!=k) return false;
k++;
} return true;
}void tcopy(node * &h,node * &t)
{
for(int i=0;i<rows;i++)
for(int j=0;j<cols;j++)
t->a[i][j]=h->a[i][j];
}void move_up(node * &t,int i,int j)
{
int temp=t->a[i][j];
t->a[i][j]=t->a[i+1][j];
t->a[i+1][j]=temp;
}
void move_down(node * &t,int i,int j)
{
int temp=t->a[i][j];
t->a[i][j]=t->a[i-1][j];
t->a[i-1][j]=temp;
}
void move_left(node * &t,int i,int j)
{
int temp=t->a[i][j];
t->a[i][j]=t->a[i][j+1];
t->a[i][j+1]=temp;
}
void move_right(node * &t,int i,int j)
{
int temp=t->a[i][j];
t->a[i][j]=t->a[i][j-1];
t->a[i][j-1]=temp;
}void print(node * h)
{
for(int i=0;i<rows;i++)
{
for(int j=0;j<cols;j++)
{
cout<<h->a[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
}bool IsExist(stree * &shead,node *t) //存在返回true,不存在则在二叉搜索树中加入该点，并返回false
{
stree *ss,*sp;
ss=shead;
sp=ss;
while(ss)
{
if(IsSame(ss->data,t)==0) return true;
sp=ss;
if(IsSame(ss->data,t)<0) ss=ss->left;
else ss=ss->right;
}

ss=new stree;
ss->data=t;
ss->left=NULL; ss->right=NULL; if(IsSame(sp->data,t)<0) sp->left=ss;
else sp->right=ss;
return false;
}int IsSame(node *p1,node *p2)
{
int i,j;
for(i=0;i<rows;i++)
for(j=0;j<cols;j++)
{
if(p1->a[i][j]<p2->a[i][j]) return -1;
if(p1->a[i][j]>p2->a[i][j]) return 1;
}
return 0;
}
lz的穷举法太耗资源了，换个算法吧.
http://www.shes.hcc.edu.tw/~oddest/math162.htm
echohere(疯狂学习C++) ( ) 信誉：100  2006-04-23 18:12:00  得分: 0
   lz的穷举法太耗资源了，换个算法吧.
http://www.shes.hcc.edu.tw/~oddest/math162.htm
-------------------------------------------------------------
首先谢谢你给我提供了这么好的资源。关于算法我这个程序确实有很多地方可以改进，譬如可改用深度搜索等。
但是我写这个程序的目的是为了测试如何在有限的资源下，让程序搜索的更多更快，如果你有这方面的资料，希望你能指点一下。
谢谢
syy64(太平洋) ( ) 信誉：145  2006-04-23 14:20:00  得分: 0
分块,动态调度.
----------------------------------------------------------------
太平洋，你好；
首先感谢你的指点。
我写这个程序的目的是为了测试如何在有限的资源下，让程序搜索的更多更快。
我觉得你所说的可能会是一种提高搜索效率的有效方法，但我对你所说的分块调度的内容不很了解，希望你能指点一些资源和书籍，我能去查阅一下。
谢谢！