퍼뮤 테이션 세트 (파이썬)에서 불법 에지 제거

Question

원본 경로와 대상 노드 (OD 쌍) 간의 최단 경로를 찾기 위해 무차별 방식을 적용하려고합니다. networkX를 사용하여 네트워크를 만들고 순열을 호출 한 다음 무차별 대입을 적용합니다.
네트워크의 모든 노드가 다른 모든 노드와 연결되어 있으면이 작업이 정상입니다. 그러나 일부 또는 많은 가장자리가 없으면이 방법은 효과가 없을 것입니다. 맞도록, 나는 불법적 인 가장자리를 포함하는 모든 permuations을 삭제해야합니다. 예를 들어

개의 순열 튜플

[(1,2,3,4,5), (1,2,4,3,5)]

및에 있다면 내 네트워크 노드 2와 3 사이의 가장자리가 존재하지 않는 경우 언급 된 목록의 첫 번째 튜플을 삭제해야합니다.

첫 번째 질문 : 우선 순열을 만들고 거기에 가서 불법적 인 가장자리를 포함하는 것을 삭제하는 것이 효율적인 방법입니까? 만약 내가 뭘해야하지?

두 번째 질문 : 그래, 내 전략은 처음 "G.has_edge (U, V)"명령 networkx에서 모든 불법 가장자리를 포함하는 튜플의 목록을 만든 다음 순열로가는 경우 찾고 있다는 것입니다 경우 그런 가장자리는 존재하고, 그 순열을 삭제한다. 좋은 전략입니까? 그렇지 않다면, 당신은 또 무엇을 제안합니다.

감사합니다 :)

이

Answer 1

일반 TSP에 대한 정확한 솔루션이 아닌 다항식으로 인식하고 있습니다. 가장 순진한 접근법 인 모든 순열을 열거하는 것은 그 복잡성이 O(n!) 임에도 불구하고 유효합니다. 자세한 내용은 wikipedia page of TSP을 참조하십시오.

특정 문제에 대해서는 그래프를 통해 depth-first search을 사용하여 올바른 순열을 생성 할 수 있습니다. 이 알고리즘을 보여주는

파이썬 같은 의사 코드는 다음과 같습니다 :

죄송합니다

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