题目说明:
(九宫问题)在一个3×3的九宫中有1-8这8个数及一个空格随机的摆放在其中的格子里,现在要求实现这个问题:将该九宫格调整为某种有序的形式。调整的规则是:每次只能将与空格(上、下、或左、右)相邻的一个数字平移到空格中。试编程实现这一问题的求解。
问题所在:
我实现了一下,但是结果不甚理想,当搜索深度比较深的时候,尽管能找到解,但却不一定是最优解。
评估函数的选择至关重要,我觉得如果是变权值的评估函数应该比较好,像我这种最普通的计算累计步距之和的方法太直观,效果肯定不好,不知道诸位能否讨论一下一些值得思考和实现的思路呢?
源码如下:
CNineGrid.h
1
#ifndef CNINEGRID_H
2
#define CNINEGRID_H
3
#include<iostream>
4
#include<cstdlib>
5
#include<cctype>
6
#include<cmath>
7![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
8
#define DISCARD -8//表示该结点已废弃
9![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
10
using namespace std;
11![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
12
typedef struct Graph
13![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
14
int grids[10];//九宫状态
15
int flag;//权值
16
int layer;//树中所属层次
17
Graph * father;//父结点指针
18
}GraphNode;//状态结点
19![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
20
class CNineGrid
21![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
22
public:
23
typedef struct DuLNode
24![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
25
GraphNode data;//0 ~ 8
26
struct DuLNode * prior;
27
struct DuLNode * next;
28
}DuLNode,*OpenList;//双链表OPEN集合
29![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
30
private:
31
OpenList pOpen;//OPEN表
32
OpenList pClosed;//CLOSED表
33
GraphNode m_start,m_goal;//目标结点
34
OpenList pop;//表头结点,即当前结点
35
public:
36
bool IsSuccess();//判断是否查找成功
37
bool IsSuccess(GraphNode N);//若h^为0,表示找到了目标结点{}
38
void Extend_Realign_Open(GraphNode Nchild[4]);//扩展并重新排列OPEN集
39
void CreateChild(GraphNode Nchild[4]);//
40
bool PopOpen();//从OPEN集中取出表头
41
void GetPath();//从目标结点沿着father指针往上打印路径
42
bool Discriminance();//判别起始结点和目标结点之间是否有解
43
44
private:
45
bool Compare(const GraphNode child,OpenList& same);//比较两结点是否相同
46
int h_hat(GraphNode N);//计算后继结点的h^函数
47
int g_hat(GraphNode N);//计算后继结点的g^函数
48
int f_hat(GraphNode N);//计算后继结点的f^函数
49
void GoalIndex(int index[]);//将目标状态转化为位置信息
50
int pedometer(int start,int end);//计算两格之间步数
51![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
52
public:
53
CNineGrid(GraphNode& begin,GraphNode& end);
54
~CNineGrid();
55
};
56![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
57
#endif //CNINEGRID_H
CNineGrid.cpp
1
#include "CNineGrid.h"
2![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
3
CNineGrid::CNineGrid(GraphNode& begin,GraphNode& end)
4![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
5
6
cout<<endl<<"输入格式:输入10个数,首个为空格位置(1~9),接下来依次为格中数字(0~8)."<<endl;
7
cout<<"如:4 2 7 4 0 8 1 3 5 6"<<endl;
8
cout<<"请输入初始状态:"<<endl;
9
for(int i=0;i<=9;i++)
10![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
11
cin>>begin.grids[i];
12
}
13
begin.father=&begin;//只有起始结点(根结点)指向父指针指向本身
14
begin.flag=-1;//设起始结点无穷小,防止回溯至根
15
begin.layer=1;
16
17
cout<<"请输入目标状态:"<<endl;
18
for(i=0;i<=9;i++)
19![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
20
cin>>end.grids[i];
21
}
22
end.father=&end;//目标结点实际上只有grids部分有用,其它的随便初始化
23
end.flag=1;
24
end.layer=1;
25
26
pOpen=new DuLNode;
27
pOpen->data=begin;
28
pOpen->next=pOpen;
29
pOpen->prior=pOpen;
30
31
pClosed=new DuLNode;
32
pClosed=NULL;
33
34
m_start=begin;
35
m_goal=end;
36
}
37![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
38
CNineGrid::~CNineGrid()
39![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
40
delete pOpen;
41
delete pClosed;
42
}
43![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
44
void CNineGrid::CreateChild(GraphNode Nchild[4])
45![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
46
GraphNode child;
47
int blank=pop->data.grids[0];
48
int way=0;
49
for(int i=0;i<=3;i++)//先复制父结点,然后在父结点基础上实施4种算子得到至多4个儿子,
50
//除根结点外,其它结点至多有三个儿子(去掉祖先)
51![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
52
child=pop->data;
53
switch(way)
54![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
55
case 0 : //up
56
if (blank<=6)
57![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
58
child.grids[blank]=child.grids[blank+3];
59
child.grids[blank+3]=0;
60
child.grids[0]=blank+3;
61
}
62
else
63
child.flag=DISCARD;
64
break;
65
case 1 : //down
66
if (blank>3)
67![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
68
child.grids[blank]=child.grids[blank-3];
69
child.grids[blank-3]=0;
70
child.grids[0]=blank-3;
71
}
72
else
73
child.flag=DISCARD;
74
break;
75
case 2 : //left
76
if (blank%3==1||blank%3==2)//空格位于前2列
77![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
78
child.grids[blank]=child.grids[blank+1];
79
child.grids[blank+1]=0;
80
child.grids[0]=blank+1;
81
}
82
else
83
child.flag=DISCARD;
84
break;
85
case 3 : //right
86
if (blank%3==2||blank%3==0)//空格位于后2列
87![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
88
child.grids[blank]=child.grids[blank-1];
89
child.grids[blank-1]=0;
90
child.grids[0]=blank-1;
91
}
92
else
93
child.flag=DISCARD;
94
break;
95
default:
96
break;
97
}
98
if (child.flag!=DISCARD)//正常儿子结点
99![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
100
if(child.grids[0]==pop->data.father->grids[0])
101
child.flag=DISCARD;//与父结点的父结点相同的儿子废弃掉
102
else
103![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
104
child.layer=pop->data.layer+1;
105
child.flag=f_hat(child);
106
child.father=&pop->data ;
107
}
108
}
109
Nchild[i]=child;
110
way++;
111
}
112
}
113![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
114
bool CNineGrid::IsSuccess(GraphNode N)//若h^为0,表示找到了目标结点{}
115![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
116
for(int i=0;i<=9;i++)
117![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
118
if(N.grids[i]!=m_goal.grids[i])
119
return false;
120
}
121
m_goal.father=pop->data.father;
122
return true;
123
}
124![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
125
bool CNineGrid::IsSuccess()//若h^为0,表示找到了目标结点{}
126![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
127
for(int i=0;i<=9;i++)
128![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
129
if(pop->data.grids[i]!=m_goal.grids[i])
130
return false;
131
}
132
m_goal.father=pop->data.father;
133
return true;
134
}
135![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
136
bool CNineGrid::Compare(const GraphNode child,OpenList& pSame)//比较child是否已在OPEN表中
137
//若在,返回true,否则返回false,pSame为指向OPEN表中已存在的相同结点的OpenList指针
138![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
139
OpenList p;
140
bool findthesame=false;//是否在OPEN表中找到与child相同的结点
141
for(p=pOpen;(p!=NULL)&&(p->next!=pOpen);p=p->next)
142![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
143
for(int i=0;i<=9;i++)
144![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
145
if(child.grids[i]!=p->data.grids[i])
146![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
147
findthesame=false;
148
break;//有不同的格子就跳出内循环for
149
}
150
else findthesame=true;
151
}
152
if (findthesame)
153![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
154
pSame=p;
155
return true;
156
}
157
}
158
for(p=pClosed;(p!=NULL)&&(p->next!=pClosed);p=p->next)//是否在CLOSED表中找到与child相同的结点
159![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
160
for(int i=0;i<=9;i++)
161![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
162
if(child.grids[i]!=p->data.grids[i])
163![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
164
findthesame=false;
165
break;//有不同的格子就跳出内循环for
166
}
167
else findthesame=true;
168
}
169
if (findthesame)
170![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
171
pSame=p;
172
return true;
173
}
174
}
175
return false;//for循环结束,仍然没有找到相同结点
176
}
177![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
178
void CNineGrid::Extend_Realign_Open(GraphNode Nchild[4])//扩展并重新排列pOpen集合
179![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
180
OpenList p,pSame=pOpen;
181
bool available;
182
for(int i=0;i<=3;i++)
183![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
184
available=true;
185
if (Nchild[i].flag!=DISCARD)
186![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
187
if (Compare(Nchild[i],pSame))
188
//情形1:扩展结点已在OPEN∪CLOSED表中
189![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
190
if(Nchild[i].flag<pSame->data.flag) //并且新结点的层次更浅
191![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
192![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
193
pSame->data.flag=Nchild[i].flag;
194
pSame->data.layer=Nchild[i].layer;
195
pSame->data.father=Nchild[i].father;
196
197
//将pSame结点稍候移到表尾,便于降序搜索重排
198
pSame->prior->next=pSame->next;//剪切pSame结点,稍候移到表尾
199
pSame->next->prior=pSame->prior;
200
}
201
}
202
else available=false;//虽找到相同结点,但评估值太大,此结点废弃
203
}
204
else//情形2:扩展结点不在OPEN表中,pSame另作他用,作为插入结点指针
205![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
206
pSame=new DuLNode;
207
pSame->data=Nchild[i];
208
}
209
210
//当新结点可用(available),插入新结点到OPEN表尾
211
if(available)
212![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
213
if (pOpen)
214![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
215
pSame->prior=pOpen->prior;pOpen->prior->next=pSame;
216
pSame->next=pOpen;pOpen->prior=pSame;
217
218
219
for(p=pSame;p!=pOpen;p=p->prior)//由后往前降序搜索,
220![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
221
if(p->data.flag<p->prior->data.flag)
222![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
223
GraphNode temp;//这一步交换是否成功呢?father指针是否交换成功?
224
temp=p->data;
225
p->data=p->prior->data;
226
p->prior->data=temp;
227
}
228
}
229
}
230
231
else
232![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
233
pOpen=pSame;
234
pOpen->next=pOpen;
235
pOpen->prior=pOpen;
236
}
237
}
238
}//end of if
239
}//end of for
240
}
241![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
242
bool CNineGrid::PopOpen()
243![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
244
OpenList p=pOpen;
245
if (!p)
246![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
247
cout<<"OPEN表空,任务失败"<<endl;
248
return false;
249
}//OPEN表空,任务失败
250
pop=p;
251![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
/**//*发现很奇怪的现象,我原来设置pop为一个GraphNode结点,赋值语句pop=p->data;*/
252![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
/**//*执行以后,pop的father指针指向自身,更奇怪的是,p->data的father指针变得和pop.father一样,*/
253![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
/**//*也改为指向它自己*/
254
255
if(p->next!=p)//OPEN表中还剩有结点
256![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
257
p->prior->next=p->next;
258
p->next->prior=p->prior;
259
pOpen=p->next;
260
}
261
else
262
pOpen=NULL;
263
264![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
/**//*往CLOSED表中加入pop*/
265
if(pClosed)
266![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
267
p->prior=pClosed->prior;pClosed->prior->next=p;
268
p->next=pClosed;pClosed->prior=p;
269
}
270
else
271![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
272
pClosed=p;
273
pClosed->next=pClosed;
274
pClosed->prior=pClosed;
275
}
276
return true;
277
}
278![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
279![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
280
void CNineGrid::GoalIndex(int index[])//目标结点下标重排信息
281![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
282
for(int i=0;i<9;i++)//和grids数组相反,goalindex数组记录0~8每个元素在哪个位置
283
index[m_goal.grids[i]]=i;
284
}
285![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
286
int CNineGrid::pedometer(int start,int end)//start,end均为格子位置
287![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
288
int disrow=abs((start-1)/3-(end-1)/3);//行距
289
int discol=abs(start%3-end%3);//列距
290
return (disrow+discol);//行距和列距之和即对应格子的步距
291
}
292
int CNineGrid::h_hat(GraphNode N)
293![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
294
int h=0;
295
int goalindex[9];//目标结点下标重排信息
296
GoalIndex(goalindex);
297
298
for(int i=1;i<=9;i++)
299![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
300![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
switch(N.grids[i])
{
301
case 0:h=h+pedometer(goalindex[0],i);break;
302
case 1:h=h+pedometer(goalindex[1],i);break;
303
case 2:h=h+pedometer(goalindex[2],i);break;
304
case 3:h=h+pedometer(goalindex[3],i);break;
305
case 4:h=h+pedometer(goalindex[4],i);break;
306
case 5:h=h+pedometer(goalindex[5],i);break;
307
case 6:h=h+pedometer(goalindex[6],i);break;
308
case 7:h=h+pedometer(goalindex[7],i);break;
309
case 8:h=h+pedometer(goalindex[8],i);break;
310
default:break;
311
}
312
}
313
return h;
314
}
315![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
316
int CNineGrid::g_hat(GraphNode N)
317![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
318
return N.layer;
319
}
320![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
321
int CNineGrid::f_hat(GraphNode N)
322![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
323
return h_hat(N)+g_hat(N);
324
}
325![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
326![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
327![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
328
void CNineGrid::GetPath()//从目标结点沿着father指针往上打印路径
329![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
330
GraphNode * p;
331
int i;
332
for(p=&m_goal;p->father!=p;p=p->father)
333![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
334
for(i=0;i<=9;i++)
335![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
336
cout<<p->grids[i];
337
}
338
cout<<endl;
339
}
340
}
341![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
342![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
343
//判别起始结点和目标结点之间是否有解,判别方法是:
344
//设函数p(x)定义为:x数所在位置前面的数比x小的数的个数,其中0空格不算在之内,
345
//对目标状态r=sigma(p(x)) sigma()表示取所有的x:1-8并求和,
346
//对于初始状态t=sigma(p(x)),如果r和t同为奇数或者同为偶数,那么该状态有解,否则无解。
347
bool CNineGrid::Discriminance()
348![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
349
int i,j;
350
int sigma_start=0,sigma_goal=0;
351
for(i=2;i<=9;i++)//第一个不用计算
352![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
353
for(j=1;j<i;j++)
354![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
355
if ((j!=m_start.grids[0])&&(m_start.grids[j]<m_start.grids[i]))
356
sigma_start++;
357
if ((j!=m_goal.grids[0])&&(m_goal.grids[j]<m_goal.grids[i]))
358
sigma_goal++;
359
}
360
}
361
if ((sigma_start+sigma_goal)%2==0)
362
return true;
363
return false;
364
}
main函数部分:
1
#include "CNineGrid.h"
2
#include <iostream>
3![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
4
using namespace std;
5![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
6
int main()
7![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif)
![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif)
{
8
9
GraphNode start,goal;
10![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
11
int i;
12![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
13
CNineGrid jiugong(start,goal);
14
15
if(!jiugong.Discriminance())
16![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
17
cout<<"题无解,请重新输入!"<<endl;
18
exit(0);
19
}
20![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
21
GraphNode Nchild[4];
22![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
23
while(jiugong.PopOpen())
24![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
25
if (jiugong.IsSuccess())
26![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
27
cout<<"Find the goal!!!"<<endl;
28
jiugong.GetPath();
29
break;
30
}
31
jiugong.CreateChild(Nchild);
32
for(i=0;i<=3;i++)
33![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
34
if (jiugong.IsSuccess(Nchild[i]))
35![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif)
{
36
cout<<"Find the goal!"<<endl;
37
jiugong.GetPath();
38
break;
39
}
40
}
41
//cout<<"Target4"<<endl;
42
jiugong.Extend_Realign_Open(Nchild);
43
cout<<"Target5"<<endl;
44
45
}
46![](http://www.cppblog.com/Images/OutliningIndicators/InBlock.gif)
47
48
return 1;
49
}
50![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
posted on 2006-11-04 11:30
哈哈 阅读(2045)
评论(4) 编辑 收藏 引用