与蟒蛇计算模式路线

Question

我有这样定义的图表：

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实现感到好奇。

谢谢

Answer 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']