[Python知识库]回溯法解决八数码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('此过程无解')

运行结果：

已找到解！！！！,路径如下
(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)
->: