eightdata.txt

8数码问题

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