パーミッションセット（python）から不正なエッジを削除

Question

私は、起点ノードと宛先ノード（ODペア）の間の最短経路を見つけるためにbrute-forceメソッドを適用しようとしています。私はnetworkXを使用してネットワークを作成し、その後にブルートフォースを適用した順列を呼び出します。
ネットワーク内のすべてのノードが他のすべてのノードと接続されている場合、これは問題ありません。しかし、いくつかのまたは多くのエッジがそこにない場合、この方法はうまくいかないでしょう。 それを正しくするには、私は違法なエッジを含むすべてのパーミュテーションを削除する必要があります。例えば

2つの置換タプルが

[（1,2,3,4,5）、（1,2,4,3,5）]

とにある場合私のネットワークはノード2と3の間にエッジが存在しないので、上記のリストの最初のタプルは削除する必要があります。

最初の質問：最初に順列を作成してそこに入り、不正なエッジを含むものを削除するのは効率的な方法ですか？もし私が何をすればいいのですか？

2番目の質問：はい、私の戦略は、私が最初に「G.has_edge（U、V）」コマンドnetworkxからすべての違法なエッジを含むタプルのリストを作成し、順列に入るとあれば探​​しているということであればそのようなエッジが存在し、その順列などを削除する。それは良い戦略ですか？もしそうでなければ、他に何をお勧めしますか？

ありがとうございました。

Answer 1

一般的なTSPの正確な解は非多項式として認識されます。最も単純なアプローチであるすべての並べ替えを列挙することは、その複雑さがO(n!)であるにもかかわらず有効です。詳細は、wikipedia page of TSPを参照してください。

具体的な問題については、depth-first searchをグラフに使用して有効な順列を生成することができます。このアルゴリズムを示す

Pythonのような擬似コードは以下の通りである：

def dfs(vertex, visited): 
    if vertex == target_vertex: 
     visited.append(target_vertex) 
     if visited != graph.vertices: 
      return 
     do_it(visited)  # visited is a valid permutation 
    for i in graph.vertices: 
     if not i in visited and graph.has_edge(vertex, i): 
      dfs(i, visited + [i]) 

dfs(start_vertex, [start_vertex])