8 головоломка с использованием метода поиска в глубину - PullRequest
Новая
       51

8 головоломка с использованием метода поиска в глубину

1 голос
/ 21 января 2020

Вот мой код для 8 пазлов с использованием dfs. Может кто-нибудь сказать, как удалить дубликаты элементов из qList и visitList? Я хочу, чтобы только один элемент представлял одно состояние в очереди и visitList. Эта проблема решает проблему 8 головоломок с использованием поиска методом грубой силы. Во время выполнения он уходит в бесконечное число l oop, поскольку он снова и снова расширяет один и тот же узел. 

from copy import deepcopy
initState=[0,1,2,3,4,5,6,7,8]
goalState=[1,4,2,3,5,0,6,7,8]
q=[]
qList=[]
visited=[]
visitedList=[]
class state:
    def __init__(self,state=[],prev=None,tree=None):
        self.state=state
        self.children=[]
        self.parent=prev
        self.tree=[]
        if tree==None:
            self.tree.append(state)
        if tree is not None:
            self.tree.extend(deepcopy(tree)

    def sameState(self,state):
        return bool(state==self.state)

    def retState(self):
        return list(self.state)

    def isPrevState(self):
        if self.parent in self.children:
            self.children.remove(self.parent)

    def moveUp(self):
        child=deepcopy(self.state)
        if child.index(0)-3>=0:
            i=child.index(0)
            temp=child[i]
            child[i]=child[i-3]
            child[i-3]=temp
            children=state(child,self.state,self.tree)
            if children.state not in qList and children.state not in visitedList:
                self.children.append(children)
        else:
            del child

    def moveRight(self):
        child=deepcopy(self.state)
        if child.index(0)%3<2:
            i=child.index(0)
            temp=child[i]
            child[i]=child[i+1]
            child[i+1]=temp
            children=state(child,self.state,self.tree)
            if children.state not in qList and children.state not in visitedList:
                self.children.append(children)
        else:
            del child

    def moveLeft(self):
        child=deepcopy(self.state)
        if child.index(0)%3>0:
            i=child.index(0)
            temp=child[i]
            child[i]=child[i-1]
            child[i-1]=temp
            children=state(child,self.state,self.tree)
            if children.state not in qList and children.state not in visitedList:
                self.children.append(children)
        else:
            del child

    def moveDown(self):
        child=deepcopy(self.state)
        if child.index(0)+3<=8:
            i=child.index(0)
            temp=child[i]
            child[i]=child[i+3]
            child[i+3]=temp
            children=state(child,self.state,self.tree)
            if children.state not in qList and children.state not in visitedList:
                self.children.append(children)
        else:
            del child

    def expandNode(self):
        self.moveLeft()
        self.moveUp()
        self.moveRight()
        self.moveDown()
        self.isPrevState()
el=state(initState)
q.append(el)
while len(q)>0:
    if list(q[len(q)-1].retState())==goalState:
        print("goal state found")
        break
    else:
        if q[len(q)-1] not in visited:
            q[len(q)-1].expandNode()
            visited.append(deepcopy(q[len(q)-1]))
            visitedList.append((q[len(q)-1].retState()))
            List=q[len(q)-1].children
            for i in range(len(List)):
                q.append(List[i])
                if List[i].retState not in qList and List[i] not in visitedList :
                    qList.append(List[i].retState())
            nq=list(dict.fromkeys(q))
            q.clear()
            q=nq 
            q.pop()
        else:
            del q[len(q)-1]
...