題目說明：
（九宮問題）在一個３×３的九宮中有１－８這８個數及一個空格隨機的擺放在其中的格子里，現在要求實現這個問題：將該九宮格調整為某種有序的形式。調整的規則是：每次只能將與空格（上、下、或左、右）相鄰的一個數字平移到空格中。試編程實現這一問題的求解。
問題所在：
我實現了一下，但是結果不甚理想，當搜索深度比較深的時候，盡管能找到解，但卻不一定是最優解。
評估函數的選擇至關重要，我覺得如果是變權值的評估函數應該比較好，像我這種最普通的計算累計步距之和的方法太直觀，效果肯定不好，不知道諸位能否討論一下一些值得思考和實現的思路呢？
源碼如下：
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
哈哈 閱讀(2078)
評論(4) 編輯 收藏 引用