桥与火把问题变种状态空间图异常：生成完全图而非目标图

我正在编写一个函数，为桥与火把问题（Bridge and Torch Problem）的变种生成所有可能状态的状态空间图。为避免为重复状态创建新节点，我使用lookup表复用相同节点，但运行程序时生成的是完全图（每个节点包含21个子节点），而非预期的状态空间图——系统共有22个可能状态。

Graph类结构 #

class Node:
    def __init__(self, lstate: str, rstate: str, nextstates=[]):
        self.lstate = lstate
        self.rstate = rstate
        self.nextnodes = nextstates

    def addChild(self, child):
        if child not in self.nextnodes:
            self.nextnodes.append(child)

    def dumpStateInfo(self):
        print("left: " + self.lstate + " right: " + self.rstate)

    def dumpNodeInfo(self):
        self.dumpStateInfo()


class Graph:
    def __init__(self, start, end) -> None:
        self.root = Node(start, end)
        self.lookup = dict()

图构建函数 #

def createChildren(self, currnode):
        currlstate = currnode.lstate
        currrstate = currnode.rstate

        if currlstate == "" or currrstate == "abcdp":
            return
        
        newnodes = []
        if "p" in currlstate:
            for i in range(len(currlstate) - 2):
                for j in range(i + 1, len(currlstate) - 1):

                    travelers = currlstate[i] + currlstate[j]

                    lstate = (
                        currlstate.replace(currlstate[i], "")
                        .replace(currlstate[j], "")
                        .replace("p", "")
                    )
                    rstate = "".join(sorted(travelers + currrstate)) + "p"
                    state = lstate + " " + rstate
                    if state not in self.lookup.keys():
                          
                        node = Node(lstate, rstate)
                        self.lookup[state] = node
                        currnode.addChild(node)
                        newnodes.append(node)

                    else:
                        node = self.lookup[state]
                        currnode.addChild(node)

                    print("parent: " + currlstate + " " + currrstate + " : Current State: " + lstate + " " + rstate)
                    currnode.dumpStateInfo()
                    node.dumpStateInfo()
                    #print(len(self.root.nextnodes))
        else:
            for i in range(len(currrstate) - 1):

                traveler = currrstate[i]
                rstate = currrstate.replace(traveler, "").replace("p", "")
                lstate = "".join(sorted(traveler + currlstate)) + "p"
                state = lstate + " " + rstate

                if state not in self.lookup.keys():

                    node = Node(lstate, rstate)
                    self.lookup[state] = node
                    currnode.addChild(node)
                    newnodes.append(node)

                else:
                    node = self.lookup[state]
                    currnode.addChild(node)

                print("parent: " + currlstate + " " + currrstate + " : Current State: " + lstate + " " + rstate)
                currnode.dumpStateInfo()
                node.dumpStateInfo()
                #print(len(self.root.nextnodes))

        for i in newnodes:
            self.createChildren(i)

def buildTree(self):
    currnode = self.root
    self.lookup[currnode.lstate + " " + currnode.rstate] = currnode
    self.createChildren(currnode)

打印函数输出信息 #

parent: abcdp  : Current State: cd abp
left: abcdp right: 
left: cd right: abp
parent: abcdp  : Current State: bd acp
left: abcdp right: 
left: bd right: acp
parent: abcdp  : Current State: bc adp
left: abcdp right: 
left: bc right: adp
parent: abcdp  : Current State: ad bcp
left: abcdp right: 
left: ad right: bcp
parent: abcdp  : Current State: ac bdp
left: abcdp right: 
left: ac right: bdp
parent: abcdp  : Current State: ab cdp
left: abcdp right: 
left: ab right: cdp
parent: cd abp : Current State: acdp b
left: cd right: abp
left: acdp right: b
parent: cd abp : Current State: bcdp a
left: cd right: abp
left: bcdp right: a
parent: acdp b : Current State: d abcp
left: acdp right: b
left: d right: abcp
parent: acdp b : Current State: c abdp
left: acdp right: b
left: c right: abdp
parent: acdp b : Current State: a bcdp
left: acdp right: b
left: a right: bcdp
parent: d abcp : Current State: adp bc
left: d right: abcp
left: adp right: bc
parent: d abcp : Current State: bdp ac
left: d right: abcp
left: bdp right: ac
parent: d abcp : Current State: cdp ab
left: d right: abcp
left: cdp right: ab
parent: adp bc : Current State:  abcdp
left: adp right: bc
left:  right: abcdp
parent: bdp ac : Current State:  abcdp
left: bdp right: ac
left:  right: abcdp
parent: cdp ab : Current State:  abcdp
left: cdp right: ab
left:  right: abcdp
parent: c abdp : Current State: acp bd
left: c right: abdp
left: acp right: bd
parent: c abdp : Current State: bcp ad
left: c right: abdp
left: bcp right: ad
parent: c abdp : Current State: cdp ab
left: c right: abdp
left: cdp right: ab
parent: acp bd : Current State:  abcdp
left: acp right: bd
left:  right: abcdp
parent: bcp ad : Current State:  abcdp
left: bcp right: ad
left:  right: abcdp
parent: a bcdp : Current State: abp cd
left: a right: bcdp
left: abp right: cd
parent: a bcdp : Current State: acp bd
left: a right: bcdp
left: acp right: bd
parent: a bcdp : Current State: adp bc
left: a right: bcdp
left: adp right: bc
parent: abp cd : Current State:  abcdp
left: abp right: cd
left:  right: abcdp
parent: bcdp a : Current State: d abcp
left: bcdp right: a
left: d right: abcp
parent: bcdp a : Current State: c abdp
left: bcdp right: a
left: c right: abdp
parent: bcdp a : Current State: b acdp
left: bcdp right: a
left: b right: acdp
parent: b acdp : Current State: abp cd
left: b right: acdp
left: abp right: cd
parent: b acdp : Current State: bcp ad
left: b right: acdp
left: bcp right: ad
parent: b acdp : Current State: bdp ac
left: b right: acdp
left: bdp right: ac
parent: bd acp : Current State: abdp c
left: bd right: acp
left: abdp right: c
parent: bd acp : Current State: bcdp a
left: bd right: acp
left: bcdp right: a
parent: abdp c : Current State: d abcp
left: abdp right: c
left: d right: abcp
parent: abdp c : Current State: b acdp
left: abdp right: c
left: b right: acdp
parent: abdp c : Current State: a bcdp
left: abdp right: c
left: a right: bcdp
parent: bc adp : Current State: abcp d
left: bc right: adp
left: abcp right: d
parent: bc adp : Current State: bcdp a
left: bc right: adp
left: bcdp right: a
parent: abcp d : Current State: c abdp
left: abcp right: d
left: c right: abdp
parent: abcp d : Current State: b acdp
left: abcp right: d
left: b right: acdp
parent: abcp d : Current State: a bcdp
left: abcp right: d
left: a right: bcdp
parent: ad bcp : Current State: abdp c
left: ad right: bcp
left: abdp right: c
parent: ad bcp : Current State: acdp b
left: ad right: bcp
left: acdp right: b
parent: ac bdp : Current State: abcp d
left: ac right: bdp
left: abcp right: d
parent: ac bdp : Current State: acdp b
left: ac right: bdp
left: acdp right: b
parent: ab cdp : Current State: abcp d
left: ab right: cdp
left: abcp right: d
parent: ab cdp : Current State: abdp c
left: ab right: cdp
left: abdp right: c

内容的提问来源于stack exchange，提问作者Lord Cinders