回溯法解决八数码问题python

101 阅读 0 评论 67 点赞

我是靠谱客的博主神勇老虎，这篇文章主要介绍回溯法解决八数码问题python，现在分享给大家，希望可以做个参考。

这次人工智能的作业就是用回溯法解决八数码问题，经过一天多的功夫，终于写出来了。下面是正题

回溯法是人工智能领域的一种重要的盲目搜索算法，何为盲目算法，即是基于规则，不断的尝试可能的路径，直到到达目的的解为止。
回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
回溯法一般需要三张表
ps表：用于保存当前路径的状态，如果找到目标状态，ps就是解题路径上的状态有序集。
nps表：新的路径状态表。它包含了等待搜索的状态，其后裔状态还未被搜索到即未生成扩展。
nss表：不可解状态集，列出了找不到解题路径的状态，如果在搜索中扩展出的状态是该表的元素，则将该状态排除。
此外，八数码还有一个书否有解的条件，即初始状态和目标状态的逆序数奇偶性相同。
逆序数：一个状态表示成一维的形式，求出除0之外所有数字的逆序数之和，也就是每个数字前面比它大的数字的个数的和，称为这个状态的逆序。
回溯法搜索过程示意图如下所示：
这里写图片描述
其搜索起点为A初始值：ps=[A], nps=[A],nss=[]，目标点为G

0	搜索点	ps	nps	nss
1	A	[A]	[A]	[ ]
2	B	[BA]	[BCDA]	[ ]
3	E	[EBA]	[EFBCDA]	[ ]
4	I	[IJEBA]	[IJEFBCD]	[ ]
5	J	[JEBA]	[JEFBCDA]	[I]
6	F	[FBA]	[FBCDA]	[EJI]
7	K	[KFBA]	[KFBCDA]	[EJI]
8	C	[CA]	[CDA]	[BFKEJI]
9	G	[GCA]	[GHCDA]	[BFKEJI]

在搜索过程中，先进行深度搜索，直到到达指点深度，或者不可解点返回，并将该状态置为不可解点，然后回到上一节点进行扩展。直到找到结果或者搜完所有深度为止。
回溯法实现八数码思路亦是如此
初始状态 :
2 8 3
1 6 4
7 0 5

目标状态:
1 2 3
8 0 4
7 6 5

下面是python代码,数码的状态用一维数组表示
节点状态类Node.py

复制代码

#encoding:utf-8
from Node import *
class back:
    def __init__(self,orignate,target,length):
        self.origate=orignate  #初始状态
        self.target=target  #目标状态
        self.ps=[]  #PS表，用于保存当前搜索路径的状态
        self.nps=[] #nps表，用于保存等待搜索的状态
        self.nss=[] #nss表，用于保存不可到达目的地的状态集
        self.spce=[-3,3,-1,1] #上下左右四个移动方向
        self.length=length
        self.MaxDegree=5  #深度限制，到达此深度回溯

def issolve(self): #判断到目标状态是否有解
        targetVer=self.getreVersNum(self.target.state)
        orinateVer=self.getreVersNum(self.origate.state)
        if(targetVer%2!=orinateVer%2):
            return False
        else:
            return True

def getreVersNum(self,state):  #获取逆序数
        sum=0
        for i in range(0,len(state)):
            if(state[i]==0):
                continue
            else:
                for j in range(0,i):
                    if(state[j]>state[i]):
                        sum+=1

return sum

# def getspaceIndex(self): #获得空格所在的位置
    #     for i in range(len(self.origate)-1):
    #         if(self.origate[i]==0):
    #             return i

def copyArray(self,state):
        arr=[]
        return arr+state

#判断状态数码是否存在
    def isexit(self,node,table):
        for i in table:
            if(i.state==node.state):
                return True
        return False

#主要算法，回溯过程
    def backMainProcess(self):
        self.ps.append(self.origate)
        self.nps.append(self.origate)
        while(len(self.nps)):
            originateState=self.ps[-1]

spacIndex=originateState.state.index(0)
            if(originateState.state==self.target.state):
                return True
            else:

#到达指定深度，回溯
                if(originateState.degree>=self.MaxDegree):

self.ps.pop()
                    self.nps.pop()
                    if(self.nps[-1]!=self.ps[-1]):

self.ps.append(self.nps[-1])
                    self.nss.insert(0,originateState)
                    continue
                flag=False
                for i in range(len(self.spce)):

if((i==0 and (spacIndex+self.spce[i])>=0) or
                    (i==1 and (spacIndex+self.spce[i])<len(self.target.state)-1)
                    or(i==2 and (spacIndex%self.length!=0 )) or
                    (i==3 and ((spacIndex+1)%self.length)!=0)):
                        state=self.copyArray(originateState.state)
                        #扩展状态
                        temp=state[spacIndex+self.spce[i]]
                        state[spacIndex+self.spce[i]]=0
                        state[spacIndex]=temp
                        #判断新的状态是否已经存在
                        nodeState=Node(state,originateState.degree+1)

if(self.isexit(nodeState,self.nps))or (self.isexit(nodeState,self.nss)):
                            continue
                        else:
                            flag=True

self.nps.append(nodeState)
                if(not flag):

self.ps.pop()
                    self.nps.pop()
                    if(self.nps[-1]!=self.ps[-1]):
                      self.ps.append(self.nps[-1])
                    self.nss.append(originateState)
                if(flag):#展开有子节点
                    self.ps.append(self.nps[-1])
    #输出结果路径
    def showLine(self):
        for node in self.ps:
            i=0
            print(node.state[i],node.state[i+1],node.state[i+2])
            print(node.state[i+3],node.state[i+4],node.state[i+5])
            print(node.state[i+6],node.state[i+7],node.state[i+8])
            print('->:')

if __name__ == '__main__':

originate=[2,8,3,1,6,4,7,0,5]
    target=[1,2,3,8,0,4,7,6,5]
    node1=Node(originate,0)
    node2=Node(target,0)
    c=back(node1,node2,3)
    if(c.issolve()):
        if(c.backMainProcess()):
            print('已找到解！！！！,路径如下')
            c.showLine()
    else:
        print('此过程无解')

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
#encoding:utf-8
from Node import *
class back:
    def __init__(self,orignate,target,length):
        self.origate=orignate  #初始状态
        self.target=target  #目标状态
        self.ps=[]  #PS表，用于保存当前搜索路径的状态
        self.nps=[] #nps表，用于保存等待搜索的状态
        self.nss=[] #nss表，用于保存不可到达目的地的状态集
        self.spce=[-3,3,-1,1] #上下左右四个移动方向
        self.length=length
        self.MaxDegree=5  #深度限制，到达此深度回溯

    def issolve(self): #判断到目标状态是否有解
        targetVer=self.getreVersNum(self.target.state)
        orinateVer=self.getreVersNum(self.origate.state)
        if(targetVer%2!=orinateVer%2):
            return False
        else:
            return True



    def getreVersNum(self,state):  #获取逆序数
        sum=0
        for i in range(0,len(state)):
            if(state[i]==0):
                continue
            else:
                for j in range(0,i):
                    if(state[j]>state[i]):
                        sum+=1

        return sum

    # def getspaceIndex(self): #获得空格所在的位置
    #     for i in range(len(self.origate)-1):
    #         if(self.origate[i]==0):
    #             return i

    def copyArray(self,state):
        arr=[]
        return arr+state


    #判断状态数码是否存在
    def isexit(self,node,table):
        for i in table:
            if(i.state==node.state):
                return True
        return False




    #主要算法，回溯过程
    def backMainProcess(self):
        self.ps.append(self.origate)
        self.nps.append(self.origate)
        while(len(self.nps)):
            originateState=self.ps[-1]

            spacIndex=originateState.state.index(0)
            if(originateState.state==self.target.state):
                return True
            else:

                #到达指定深度，回溯
                if(originateState.degree>=self.MaxDegree):


                    self.ps.pop()
                    self.nps.pop()
                    if(self.nps[-1]!=self.ps[-1]):

                      self.ps.append(self.nps[-1])
                    self.nss.insert(0,originateState)
                    continue
                flag=False
                for i in range(len(self.spce)):

                    if((i==0 and (spacIndex+self.spce[i])>=0) or
                    (i==1 and (spacIndex+self.spce[i])<len(self.target.state)-1)
                    or(i==2 and (spacIndex%self.length!=0 )) or
                    (i==3 and ((spacIndex+1)%self.length)!=0)):
                        state=self.copyArray(originateState.state)
                        #扩展状态
                        temp=state[spacIndex+self.spce[i]]
                        state[spacIndex+self.spce[i]]=0
                        state[spacIndex]=temp
                        #判断新的状态是否已经存在
                        nodeState=Node(state,originateState.degree+1)

                        if(self.isexit(nodeState,self.nps))or (self.isexit(nodeState,self.nss)):
                            continue
                        else:
                            flag=True

                            self.nps.append(nodeState)
                if(not flag):

                    self.ps.pop()
                    self.nps.pop()
                    if(self.nps[-1]!=self.ps[-1]):
                      self.ps.append(self.nps[-1])
                    self.nss.append(originateState)
                if(flag):#展开有子节点
                    self.ps.append(self.nps[-1])
    #输出结果路径
    def showLine(self):
        for node in self.ps:
            i=0
            print(node.state[i],node.state[i+1],node.state[i+2])
            print(node.state[i+3],node.state[i+4],node.state[i+5])
            print(node.state[i+6],node.state[i+7],node.state[i+8])
            print('->:')








if __name__ == '__main__':


    originate=[2,8,3,1,6,4,7,0,5]
    target=[1,2,3,8,0,4,7,6,5]
    node1=Node(originate,0)
    node2=Node(target,0)
    c=back(node1,node2,3)
    if(c.issolve()):
        if(c.backMainProcess()):
            print('已找到解！！！！,路径如下')
            c.showLine()
    else:
        print('此过程无解')

运行结果：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
已找到解！！！！,路径如下
(2, 8, 3)
(1, 6, 4)
(7, 0, 5)
->:
(2, 8, 3)
(1, 0, 4)
(7, 6, 5)
->:
(2, 0, 3)
(1, 8, 4)
(7, 6, 5)
->:
(0, 2, 3)
(1, 8, 4)
(7, 6, 5)
->:
(1, 2, 3)
(0, 8, 4)
(7, 6, 5)
->:
(1, 2, 3)
(8, 0, 4)
(7, 6, 5)
->: