-1

我有一个这样定义的图表：

graph = {
    'A': ['H', 'B'],
    'B': ['H'. 'A', 'C', 'D', 'F'],
    'C': ['B', 'D'],
    'D': ['H', 'B', 'C', 'F', 'E'],
    'E': ['F', 'D'],
    'F': ['E', 'D', 'B', 'H', 'G'],
    'G': ['F', 'H'],
    'H': ['A', 'B', 'D', 'F', 'G'],
}

我想知道使用所有边但不通过同一边来计算从 A 到自身的路线的最佳方法是什么。

上面解释的问题可能没有解决方案，但我对这种类型的问题的 Python 实现很好奇。

谢谢

4

1 回答 1

1

这是完全有可能的，如果不是有点困难的话。以下是我将如何解决这个问题。 

graph = {
    'A': ['H', 'B'],
    'B': ['H', 'A', 'C', 'D', 'F'],
    'C': ['B', 'D'],
    'D': ['H', 'B', 'C', 'F', 'E'],
    'E': ['F', 'D'],
    'F': ['E', 'D', 'B', 'H', 'G'],
    'G': ['F', 'H'],
    'H': ['A', 'B', 'D', 'F', 'G'],
}

def is_goal(path): 
    states_visited = set(path);
    for state in graph.keys():
        if state not in states_visited:
            return False
    return path[-1] == 'A'

def successors(state):
    return graph[state]

def sps(start, is_goal, successors):
    explored_paths = set((start,))
    explored_edges = {}
    explored_edges[(start,)] = set()
    frontier = [[start]]
    while frontier:
        #breadth first search
        path = frontier.pop(0)
        s = path[-1]
        for state in successors(s):
            new_path = path + [state]
            #cast to tuple for hashing
            hashable_path = tuple(path)
            hashable_new_path = tuple(new_path)
            if hashable_new_path not in explored_paths:
                edge = tuple(sorted(new_path[-2:]))
                new_set = set()
                new_set.add(edge);
                if edge not in explored_edges[hashable_path]:
                    explored_paths.add(hashable_new_path)
                    explored_edges[hashable_new_path] = explored_edges[hashable_path].union(new_set)
                    if is_goal(new_path):
                        return new_path
                    else: 
                        frontier.append(new_path)

    return "No path found"

if __name__ == '__main__':
    print(sps('A', is_goal, successors))

在终端执行

$ python3 sps.py 
['A', 'H', 'B', 'C', 'D', 'H', 'F', 'B', 'A']
于 2013-08-19T15:53:41.967 回答