겹치는 동일한 경로의 다른 경로

Question

나는 경로를 끝내기 위해 A와 B 사이에 조니가 있습니다. 경로는 초기 및 최종 킬로미터로 정의됩니다.

path 0 -> (0, 10) 
path 1 -> (10, 25) 
path 2 -> (10, 15) 
path 3 -> (15, 20) 
path 4 -> (20, 30) 
path 5 -> (25, 35) 
path 6 -> (30, 35) 
path 7 -> (35, 40) 
path 8 -> (40, 50) 

위에서 볼 수 있듯이 겹치는 경로가 있습니다.

path 0 -> NONE 
path 1 -> 2,3,4 
path 2 -> 1 
path 3 -> 1 
path 4 -> 1,5 
path 5 -> 4,6 
path 6 -> 5 
path 7 -> NONE 
path 8 -> NONE 

내가 싶어하면 경로에서 중복 경로없이 모든 가능한 경로하지만 하나는주의해야한다 : 사실, 우리는 중복 경로의 목록을 얻을 수 있습니다. 이 문제를 해결할 수있는 알고리즘이 있습니까? 재귀 또는 스택과 같은 유용한 데이터 구조로 구현하려고 시도했지만 최종 가능한 경로 목록을 얻기가 매우 어려웠고 문제를 역으로 처리하고 폐기 된 경로의 목록을 얻으려고 시도했습니다. :

route 0-2-3-4-6-7-8 -> [1,5] discarded 
route 0-2-3-5-7-8 -> [1,4,6] discarded 
route 0-1-6-7-8 -> [2,3,4,5] discarded 
route 0-1-5-7-8 -> [2,3,4,6] discarded 

Answer 1

예. 이것은 간단한 그래프 문제입니다. 이러한 경로를 겹치는 경로로 보는 대신 마일스톤이 연결되지 않은 노드라는 사실을 인식하십시오. 예를 들어, 당신이 마일스톤 20에 있다면, 당신이 할 수있는 유일한 전진 이동은 30입니다 - 그리고 다른 세그먼트와 중복은 전혀 중요하지 않습니다. 아마도 당신이 도시를 번호가 매겨진 도시로 향하는 노선으로 생각할 때 더 효과적 일 수 있습니다.

다양한 그래프 탐색 알고리즘을 찾아 알고리즘을 선택할 수 있습니다. 이것은 간단합니다. 결정 사항은 단 하나뿐입니다 (마일스톤 10). 선택을하면 나머지 경로가 결정됩니다.

거기에서 가져갈 수 있습니까?

Answer 2

마지막으로 코드가 생깁니다. (가능하면 개선 될 수 있음) :

from copy import deepcopy 

discarded_overlapped = [] 
def overlap(overlapped,discarded): 
    if all(x is None for x in overlapped): 
     discarded.sort() 
     if discarded not in discarded_overlapped: 
      discarded_overlapped.append(discarded) 
     return 
    for i in range(len(overlapped)): 
     if not overlapped[i] == None: 
      overlapped_copy = deepcopy(overlapped) 
      discarded_copy = deepcopy(discarded) 
      for j in overlapped[i]: 
       if j not in discarded: 
        discarded_copy.append(j) 
        overlapped_copy[j] = None 
      overlapped_copy[i] = None 
      overlap(overlapped_copy,discarded_copy) 


Data = [None,[2,3,4],[1],[1],[1,5],[4,6],[5],None,None] 
overlap(Data,[]) 
print(discarded_overlapped) 
# [[2, 3, 4, 6], [2, 3, 4, 5], [1, 5], [1, 4, 6]]