題目說明：
（九宮問題）在一個３×３的九宮中有１－８這８個數(shù)及一個空格隨機(jī)的擺放在其中的格子里，現(xiàn)在要求實(shí)現(xiàn)這個問題：將該九宮格調(diào)整為某種有序的形式。調(diào)整的規(guī)則是：每次只能將與空格（上、下、或左、右）相鄰的一個數(shù)字平移到空格中。試編程實(shí)現(xiàn)這一問題的求解。
問題所在：
我實(shí)現(xiàn)了一下，但是結(jié)果不甚理想，當(dāng)搜索深度比較深的時候，盡管能找到解，但卻不一定是最優(yōu)解。
評估函數(shù)的選擇至關(guān)重要，我覺得如果是變權(quán)值的評估函數(shù)應(yīng)該比較好，像我這種最普通的計(jì)算累計(jì)步距之和的方法太直觀，效果肯定不好，不知道諸位能否討論一下一些值得思考和實(shí)現(xiàn)的思路呢？
源碼如下：
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//表示該結(jié)點(diǎn)已廢棄
9
10using namespace std;
11
12typedef struct Graph
13
{
14
int grids[10];//九宮狀態(tài)
15 int flag;//權(quán)值
16 int layer;//樹中所屬層次
17 Graph * father;//父結(jié)點(diǎn)指針
18
}GraphNode;//狀態(tài)結(jié)點(diǎn)
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;//目標(biāo)結(jié)點(diǎn)
34 OpenList pop;//表頭結(jié)點(diǎn),即當(dāng)前結(jié)點(diǎn)
35 public:
36 bool IsSuccess();//判斷是否查找成功
37 bool IsSuccess(GraphNode N);//若h^為0,表示找到了目標(biāo)結(jié)點(diǎn){}
38 void Extend_Realign_Open(GraphNode Nchild[4]);//擴(kuò)展并重新排列OPEN集
39 void CreateChild(GraphNode Nchild[4]);//
40 bool PopOpen();//從OPEN集中取出表頭
41 void GetPath();//從目標(biāo)結(jié)點(diǎn)沿著father指針往上打印路徑
42 bool Discriminance();//判別起始結(jié)點(diǎn)和目標(biāo)結(jié)點(diǎn)之間是否有解
43
44 private:
45 bool Compare(const GraphNode child,OpenList& same);//比較兩結(jié)點(diǎn)是否相同
46 int h_hat(GraphNode N);//計(jì)算后繼結(jié)點(diǎn)的h^函數(shù)
47 int g_hat(GraphNode N);//計(jì)算后繼結(jié)點(diǎn)的g^函數(shù)
48 int f_hat(GraphNode N);//計(jì)算后繼結(jié)點(diǎn)的f^函數(shù)
49 void GoalIndex(int index[]);//將目標(biāo)狀態(tài)轉(zhuǎn)化為位置信息
50 int pedometer(int start,int end);//計(jì)算兩格之間步數(shù)
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個數(shù)，首個為空格位置(1~9),接下來依次為格中數(shù)字(0~8)."<<endl;
7 cout<<"如：4 2 7 4 0 8 1 3 5 6"<<endl;
8 cout<<"請輸入初始狀態(tài)："<<endl;
9 for(int i=0;i<=9;i++)
10 {
11 cin>>begin.grids[i];
12 }
13 begin.father=&begin;//只有起始結(jié)點(diǎn)(根結(jié)點(diǎn))指向父指針指向本身
14 begin.flag=-1;//設(shè)起始結(jié)點(diǎn)無窮小,防止回溯至根
15 begin.layer=1;
16
17 cout<<"請輸入目標(biāo)狀態(tài)："<<endl;
18 for(i=0;i<=9;i++)
19 {
20 cin>>end.grids[i];
21 }
22 end.father=&end;//目標(biāo)結(jié)點(diǎn)實(shí)際上只有g(shù)rids部分有用,其它的隨便初始化
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++)//先復(fù)制父結(jié)點(diǎn)，然后在父結(jié)點(diǎn)基礎(chǔ)上實(shí)施4種算子得到至多4個兒子,
50 //除根結(jié)點(diǎn)外,其它結(jié)點(diǎn)至多有三個兒子(去掉祖先)
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)//正常兒子結(jié)點(diǎn)
99 {
100 if(child.grids[0]==pop->data.father->grids[0])
101 child.flag=DISCARD;//與父結(jié)點(diǎn)的父結(jié)點(diǎn)相同的兒子廢棄掉
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,表示找到了目標(biāo)結(jié)點(diǎn){}
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,表示找到了目標(biāo)結(jié)點(diǎn){}
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表中已存在的相同結(jié)點(diǎn)的OpenList指針
138{
139 OpenList p;
140 bool findthesame=false;//是否在OPEN表中找到與child相同的結(jié)點(diǎn)
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;//有不同的格子就跳出內(nèi)循環(huán)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相同的結(jié)點(diǎn)
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;//有不同的格子就跳出內(nèi)循環(huán)for
166 }
167 else findthesame=true;
168 }
169 if (findthesame)
170 {
171 pSame=p;
172 return true;
173 }
174 }
175 return false;//for循環(huán)結(jié)束,仍然沒有找到相同結(jié)點(diǎn)
176}
177
178void CNineGrid::Extend_Realign_Open(GraphNode Nchild[4])//擴(kuò)展并重新排列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：擴(kuò)展結(jié)點(diǎn)已在OPEN∪CLOSED表中
189 {
190 if(Nchild[i].flag<pSame->data.flag) //并且新結(jié)點(diǎn)的層次更淺
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結(jié)點(diǎn)稍候移到表尾，便于降序搜索重排
198 pSame->prior->next=pSame->next;//剪切pSame結(jié)點(diǎn)，稍候移到表尾
199 pSame->next->prior=pSame->prior;
200 }
201 }
202 else available=false;//雖找到相同結(jié)點(diǎn),但評估值太大,此結(jié)點(diǎn)廢棄
203 }
204 else//情形2：擴(kuò)展結(jié)點(diǎn)不在OPEN表中,pSame另作他用,作為插入結(jié)點(diǎn)指針
205 {
206 pSame=new DuLNode;
207 pSame->data=Nchild[i];
208 }
209
210 //當(dāng)新結(jié)點(diǎn)可用(available),插入新結(jié)點(diǎn)到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表空，任務(wù)失敗"<<endl;
248 return false;
249 }//OPEN表空，任務(wù)失敗
250 pop=p;
251 /**//*發(fā)現(xiàn)很奇怪的現(xiàn)象,我原來設(shè)置pop為一個GraphNode結(jié)點(diǎn),賦值語句pop=p->data;*/
252 /**//*執(zhí)行以后,pop的father指針指向自身,更奇怪的是,p->data的father指針變得和pop.father一樣,*/
253 /**//*也改為指向它自己*/
254
255 if(p->next!=p)//OPEN表中還剩有結(jié)點(diǎn)
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[])//目標(biāo)結(jié)點(diǎn)下標(biāo)重排信息
281{
282 for(int i=0;i<9;i++)//和grids數(shù)組相反,goalindex數(shù)組記錄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);//行距和列距之和即對應(yīng)格子的步距
291}
292int CNineGrid::h_hat(GraphNode N)
293{
294 int h=0;
295 int goalindex[9];//目標(biāo)結(jié)點(diǎn)下標(biāo)重排信息
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()//從目標(biāo)結(jié)點(diǎn)沿著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//判別起始結(jié)點(diǎn)和目標(biāo)結(jié)點(diǎn)之間是否有解,判別方法是：
344//設(shè)函數(shù)p(x)定義為：x數(shù)所在位置前面的數(shù)比x小的數(shù)的個數(shù)，其中0空格不算在之內(nèi),
345//對目標(biāo)狀態(tài)r=sigma(p(x)) sigma()表示取所有的x:1-8并求和，
346//對于初始狀態(tài)t=sigma(p(x))，如果r和t同為奇數(shù)或者同為偶數(shù)，那么該狀態(tài)有解，否則無解。
347bool CNineGrid::Discriminance()
348{
349 int i,j;
350 int sigma_start=0,sigma_goal=0;
351 for(i=2;i<=9;i++)//第一個不用計(jì)算
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函數(shù)部分：
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
哈哈 閱讀(2088)
評論(4) 編輯 收藏 引用