python - 使用 DFS 搜索图形时出现 KeyError

Question

我想做的是在图表上实现深度搜索算法以达到目标状态，但我一直收到 KeyError。它似乎适用于更小、更简单的图形，但这个不起作用。

    #The Graph to Search   
         graph = {
                    'state1' : set(['state2','state3','state4']),
                    'state2' : set(['state5']),
                    'state5' : set(['state10','state11']),
                    'state10' : set(['state20']),
                    'state20' : set(['state34','state35']),
                    'state11' : set(['state21','state22','state23']),
                    'state21' : set(['state36','state37']),
                    'state22' : set(['state38','state39']),
                    'state23' : set(['state40','state41']),
                    'state3' : set(['state6','state7','state8']),
                    'state6' : set(['state12','state13']),
                    'state12' : set(['state24']),
                    'state24' : set(['state42','state43']),
                    'state13' : set(['state25']),
                    'state25' : set(['state44','state45']),
                    'state7' : set(['state14','state15']),
                    'state14' : set(['state26']),
                    'state26' : set(['state46']), #GOALSTATE
                    'state15' : set(['state27']),
                    'state8' : set(['state16','state17']),
                    'state16' : set(['state28']),
                    'state17' : set(['state29']),
                    'state4' : set(['state9']),
                    'state9' : set(['state18','state19']),
                    'state18' : set(['state30','state31','state32']),
                    'state19' : set(['state33'])
                    }


            #Depth First Algorithm
            def dfs_paths(graph, start, goal):
                stack = [(start, [start])]
                while stack:
                    (vertex, path) = stack.pop()
                    for next in graph[vertex] - set(path) :
                        if next == goal:
                            yield path + [next]
                        else:[enter image description here][1]
                            stack.append((next, path + [next]))

            #Method Call
            list(dfs_paths(graph, 'state1', 'state46'))   

Answer 1

正如 timgeb 提到的，有更好的方法可以做到这一点。但是正如 pkpnd 提到的，您的代码有时会失败的原因是某些路径状态没有相应的键，因此需要跳过它们。

我做了一些其他的小改动，比如使用更现代的 set 语法，并且不使用 next 作为变量名，因为这是一个内置函数。我还使用 set.difference 方法而不是 - 操作数形式，因此我不需要将路径列表转换为集合。

graph = {
    'state1': {'state3', 'state2', 'state4'},
    'state2': {'state5'},
    'state5': {'state11', 'state10'},
    'state10': {'state20'},
    'state20': {'state34', 'state35'},
    'state11': {'state22', 'state21', 'state23'},
    'state21': {'state37', 'state36'},
    'state22': {'state39', 'state38'},
    'state23': {'state40', 'state41'},
    'state3': {'state8', 'state7', 'state6'},
    'state6': {'state13', 'state12'},
    'state12': {'state24'},
    'state24': {'state43', 'state42'},
    'state13': {'state25'},
    'state25': {'state45', 'state44'},
    'state7': {'state14', 'state15'},
    'state14': {'state26'},
    'state26': {'state46'},
    'state15': {'state27'},
    'state8': {'state17', 'state16'},
    'state16': {'state28'},
    'state17': {'state29'},
    'state4': {'state9'},
    'state9': {'state19', 'state18'},
    'state18': {'state30', 'state32', 'state31'},
    'state19': {'state33'},
}

#Depth First Algorithm
def dfs_paths(graph, start, goal):
    stack = [(start, [start])]
    while stack:
        vertex, path = stack.pop()
        if vertex not in graph:
            continue
        for nxt in graph[vertex].difference(path):
            if nxt == goal:
                yield path + [nxt]
            else:
                stack.append((nxt, path + [nxt]))

for a in dfs_paths(graph, 'state1', 'state46'):
    print(a)

输出

['state1', 'state3', 'state7', 'state14', 'state26', 'state46']