题目说明：
（九宫问题）在一个３×３的九宫中有１－８这８个数及一个空格随机的摆放在其中的格子里，现在要求实现这个问题：将该九宫格调整为某种有序的形式。调整的规则是：每次只能将与空格（上、下、或左、右）相邻的一个数字平移到空格中。试编程实现这一问题的求解。
问题所在：
我实现了一下，但是结果不甚理想，当搜索深度比较深的时候，尽管能找到解，但却不一定是最优解。
评估函数的选择至关重要，我觉得如果是变权值的评估函数应该比较好，像我这种最普通的计算累计步距之和的方法太直观，效果肯定不好，不知道诸位能否讨论一下一些值得思考和实现的思路呢？
源码如下：
CNineGrid.h
1
#ifndef CNINEGRID_H
2#define CNINEGRID_H
3#include<iostream>
4#include<cstdlib>
5#include<cctype>
6#include<cmath>
7
8#define DISCARD -8//表示该结点已废弃
9
10using namespace std;
11
12typedef struct Graph
13
{
14
int grids[10];//九宫状态
15 int flag;//权值
16 int layer;//树中所属层次
17 Graph * father;//父结点指针
18
}GraphNode;//状态结点
19
20class CNineGrid
21{
22public:
23 typedef struct DuLNode
24
{
25 GraphNode data;//0 ~ 8
26 struct DuLNode * prior;
27 struct DuLNode * next;
28
}DuLNode,*OpenList;//双链表OPEN集合
29
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
52 public:
53 CNineGrid(GraphNode& begin,GraphNode& end);
54 ~CNineGrid();
55};
56
57#endif //CNINEGRID_H
CNineGrid.cpp
1#include "CNineGrid.h"
2
3CNineGrid::CNineGrid(GraphNode& begin,GraphNode& end)
4{
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 {
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 {
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
38CNineGrid::~CNineGrid()
39{
40 delete pOpen;
41 delete pClosed;
42}
43
44void CNineGrid::CreateChild(GraphNode Nchild[4])
45{
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 {
52 child=pop->data;
53 switch(way)
54 {
55 case 0 : //up
56 if (blank<=6)
57 {
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 {
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 {
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 {
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 {
100 if(child.grids[0]==pop->data.father->grids[0])
101 child.flag=DISCARD;//与父结点的父结点相同的儿子废弃掉
102 else
103 {
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
114bool CNineGrid::IsSuccess(GraphNode N)//若h^为0,表示找到了目标结点{}
115{
116 for(int i=0;i<=9;i++)
117 {
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
125bool CNineGrid::IsSuccess()//若h^为0,表示找到了目标结点{}
126{
127 for(int i=0;i<=9;i++)
128 {
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
136bool CNineGrid::Compare(const GraphNode child,OpenList& pSame)//比较child是否已在OPEN表中
137//若在，返回true，否则返回false，pSame为指向OPEN表中已存在的相同结点的OpenList指针
138{
139 OpenList p;
140 bool findthesame=false;//是否在OPEN表中找到与child相同的结点
141 for(p=pOpen;(p!=NULL)&&(p->next!=pOpen);p=p->next)
142 {
143 for(int i=0;i<=9;i++)
144 {
145 if(child.grids[i]!=p->data.grids[i])
146 {
147 findthesame=false;
148 break;//有不同的格子就跳出内循环for
149 }
150 else findthesame=true;
151 }
152 if (findthesame)
153 {
154 pSame=p;
155 return true;
156 }
157 }
158 for(p=pClosed;(p!=NULL)&&(p->next!=pClosed);p=p->next)//是否在CLOSED表中找到与child相同的结点
159 {
160 for(int i=0;i<=9;i++)
161 {
162 if(child.grids[i]!=p->data.grids[i])
163 {
164 findthesame=false;
165 break;//有不同的格子就跳出内循环for
166 }
167 else findthesame=true;
168 }
169 if (findthesame)
170 {
171 pSame=p;
172 return true;
173 }
174 }
175 return false;//for循环结束,仍然没有找到相同结点
176}
177
178void CNineGrid::Extend_Realign_Open(GraphNode Nchild[4])//扩展并重新排列pOpen集合
179{
180 OpenList p,pSame=pOpen;
181 bool available;
182 for(int i=0;i<=3;i++)
183 {
184 available=true;
185 if (Nchild[i].flag!=DISCARD)
186 {
187 if (Compare(Nchild[i],pSame))
188 //情形1：扩展结点已在OPEN∪CLOSED表中
189 {
190 if(Nchild[i].flag<pSame->data.flag) //并且新结点的层次更浅
191 {
192 {
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 {
206 pSame=new DuLNode;
207 pSame->data=Nchild[i];
208 }
209
210 //当新结点可用(available),插入新结点到OPEN表尾
211 if(available)
212 {
213 if (pOpen)
214 {
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 {
221 if(p->data.flag<p->prior->data.flag)
222 {
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 {
233 pOpen=pSame;
234 pOpen->next=pOpen;
235 pOpen->prior=pOpen;
236 }
237 }
238 }//end of if
239 }//end of for
240}
241
242bool CNineGrid::PopOpen()
243{
244 OpenList p=pOpen;
245 if (!p)
246 {
247 cout<<"OPEN表空，任务失败"<<endl;
248 return false;
249 }//OPEN表空，任务失败
250 pop=p;
251 /**//*发现很奇怪的现象,我原来设置pop为一个GraphNode结点,赋值语句pop=p->data;*/
252 /**//*执行以后,pop的father指针指向自身,更奇怪的是,p->data的father指针变得和pop.father一样,*/
253 /**//*也改为指向它自己*/
254
255 if(p->next!=p)//OPEN表中还剩有结点
256 {
257 p->prior->next=p->next;
258 p->next->prior=p->prior;
259 pOpen=p->next;
260 }
261 else
262 pOpen=NULL;
263
264/**//*往CLOSED表中加入pop*/
265 if(pClosed)
266 {
267 p->prior=pClosed->prior;pClosed->prior->next=p;
268 p->next=pClosed;pClosed->prior=p;
269 }
270 else
271 {
272 pClosed=p;
273 pClosed->next=pClosed;
274 pClosed->prior=pClosed;
275 }
276 return true;
277}
278
279
280void CNineGrid::GoalIndex(int index[])//目标结点下标重排信息
281{
282 for(int i=0;i<9;i++)//和grids数组相反,goalindex数组记录0~8每个元素在哪个位置
283 index[m_goal.grids[i]]=i;
284}
285
286int CNineGrid::pedometer(int start,int end)//start,end均为格子位置
287{
288 int disrow=abs((start-1)/3-(end-1)/3);//行距
289 int discol=abs(start%3-end%3);//列距
290 return (disrow+discol);//行距和列距之和即对应格子的步距
291}
292int CNineGrid::h_hat(GraphNode N)
293{
294 int h=0;
295 int goalindex[9];//目标结点下标重排信息
296 GoalIndex(goalindex);
297
298 for(int i=1;i<=9;i++)
299 {
300 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
316int CNineGrid::g_hat(GraphNode N)
317{
318 return N.layer;
319}
320
321int CNineGrid::f_hat(GraphNode N)
322{
323 return h_hat(N)+g_hat(N);
324}
325
326
327
328void CNineGrid::GetPath()//从目标结点沿着father指针往上打印路径
329{
330 GraphNode * p;
331 int i;
332 for(p=&m_goal;p->father!=p;p=p->father)
333 {
334 for(i=0;i<=9;i++)
335 {
336 cout<<p->grids[i];
337 }
338 cout<<endl;
339 }
340}
341
342
343//判别起始结点和目标结点之间是否有解,判别方法是：
344//设函数p(x)定义为：x数所在位置前面的数比x小的数的个数，其中0空格不算在之内,
345//对目标状态r=sigma(p(x)) sigma()表示取所有的x:1-8并求和，
346//对于初始状态t=sigma(p(x))，如果r和t同为奇数或者同为偶数，那么该状态有解，否则无解。
347bool CNineGrid::Discriminance()
348{
349 int i,j;
350 int sigma_start=0,sigma_goal=0;
351 for(i=2;i<=9;i++)//第一个不用计算
352 {
353 for(j=1;j<i;j++)
354 {
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
4using namespace std;
5
6int main()
7{
8
9 GraphNode start,goal;
10
11 int i;
12
13 CNineGrid jiugong(start,goal);
14
15 if(!jiugong.Discriminance())
16 {
17 cout<<"题无解,请重新输入!"<<endl;
18 exit(0);
19 }
20
21 GraphNode Nchild[4];
22
23 while(jiugong.PopOpen())
24 {
25 if (jiugong.IsSuccess())
26 {
27 cout<<"Find the goal!!!"<<endl;
28 jiugong.GetPath();
29 break;
30 }
31 jiugong.CreateChild(Nchild);
32 for(i=0;i<=3;i++)
33 {
34 if (jiugong.IsSuccess(Nchild[i]))
35 {
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
47
48 return 1;
49}
50
posted on 2006-11-04 11:30
哈哈 阅读(2090)
评论(4) 编辑 收藏 引用