时间戳

首页 > 解决方案 > 递归在块世界问题中不起作用......不回溯到父节点

python - 递归在块世界问题中不起作用......不回溯到父节点

问题描述

import copy
class node:
    def __init__(self,state):
        self.state=state
        self.children=[]
    def action(self):
        for i in range(3):
                for j in range(3):
                    if i!=j:
                        temp=copy.deepcopy(self.state)
                        if len(temp[i])>0:
                            m=temp[i].pop()
                            temp[j].append(m)
                            if temp not in self.children:
                                self.children.append(node(temp))
    def display(self):
        print("different node \n")
        print(self.state)
        for i in range(len(self.children)):
            print(self.children[i].state)
            
    def search(self , goal,queue):
        print('called')
        if self.state==goal:
            print("inspection state=",self.state)
            return True 
        else:
            for i in range(len(self.children)):
                if self.children[i].state not in queue:
                    print(self.children[i].state)
                    self.children[i].action()
                    print(self.children[i].children[0].state)
                    temp=copy.deepcopy(self.children[i].state)
                    queue.append(temp)
                    return self.children[i].search(goal,queue)
                    return self.search(goal,queue)
            else:
                print("queue full error")
                
i_state=[['a'],['b','c'],[]]
root=node(i_state)
root.action()
goal=[[],['a','b','c'],[]]
queue=[]
root.search(goal,queue)

这里的代码不是回溯到父节点并搜索其他分支。return self.children[i].search(goal,queue) return self.search(goal,queue) 当子节点填满特定分支的队列时，将父节点发送到函数

标签： pythonclassrecursionsearchbacktracking

解决方案

我怀疑这个双重return是你问题的根源：

return self.children[i].search(goal,queue)
return self.search(goal,queue)

第二条语句永远不会被执行。一种典型的处理方式可能是：

result = self.children[i].search(goal, queue)

if result:
     return result

return self.search(goal,queue)

或者任何适合你的算法的东西。以下是带有此修复和一些样式更改的代码：

import copy

class node:
    def __init__(self, state):
        self.state = state
        self.children = []

    def action(self):
        for i in range(3):
            for j in range(3):
                if i != j:
                    if self.state[i]:
                        temp = copy.deepcopy(self.state)
                        m = temp[i].pop()
                        temp[j].append(m)

                        if temp not in self.children:
                            self.children.append(node(temp))

    def display(self):
        print("different node \n")
        print(self.state)

        for child in self.children:
            print(child.state)

    def search(self, goal, queue):
        print('called')

        if self.state == goal:
            print("inspection state =", self.state)
            return True

        for child in self.children:
            if child.state not in queue:
                print(child.state)
                child.action()
                print(child.children[0].state)
                temp = copy.deepcopy(child.state)
                queue.append(temp)
                result = child.search(goal, queue)

                if result:
                    return result

                return self.search(goal, queue)

        print("queue full error")
        return False

i_state = [['a'], ['b', 'c'], []]
root = node(i_state)
root.action()
goal = [[], ['a', 'b', 'c'], []]
queue = []
root.search(goal, queue)

推荐阅读