與蟒蛇計算模式路線

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