그래프에서 제약 조건을 만족하는 최단 경로를 찾는 방법

Question

가중치 그래프에서 최단 경로를 찾으려면 경로가 일부 매개 변수 (1000이라고 가정) 미만의 총 거리를 가져야한다는 제한 조건을 고려하십시오.

다음과 같이 시도했지만 내 코드가 잘못된 이유를 알지 못합니다.

def directedDFS(digraph, start, end, maxTotalDist): 
    visited = [] 
    if not (digraph.hasNode(start) and digraph.hasNode(end)): 
     raise ValueError('Start or end not in graph.') 
    path = [str(start)] 
    if start == end: 
     return path 
    shortest = None 
    for node in digraph.childrenOf(start): 
     if (str(node) not in visited): 
      visited = visited + [str(node)] 
      firststep_distance = digraph.childrenOf(start)[node][0] 
      firststep_outer_distance = digraph.childrenOf(start)[node][1] 
      if (firststep_distance <= maxTotalDist): 
       newPath = directedDFS(digraph, node, end, maxTotalDist-firststep_distance) 
       if newPath == None: 
        continue 
       if (shortest == None or TotalDistance(digraph,newPath) < TotalDistance(digraph,shortest)): 
        shortest = newPath 
    if shortest != None: 
     path = path + shortest 
    else: 
     path = None 
    return path 

또 다른 것은

내가 지정된 노드에서 시작하는 경로의 거리를 기준으로하지만, 원래의 시작 지점에서 전체 경로의 거리를 기준으로 비교할 없다는 것입니다. 그래도 내가 할 수있는 최선의 방법은 모르겠지만.

Answer 1

제공된 코드의 머리 부분이나 꼬리 부분을 정말로 만들 수 없습니다 (firststep_distance? firststep_outer_distance?). 구현하려는 알고리즘의 이름을 제공해 주시겠습니까?

무언가를 즉석에서 만들고 교육 목적으로 그래프 이론을 재발 명한다는 목표를 가지고 있지 않다면 표준 최단 경로 알고리즘을 찾아 보도록 권합니다. 가중치가 음이 아닌 것을 보장 할 수 있다면, 표준은 Dijkstra의 알고리즘입니다. Wikipedia는 피보나치 힙을 사용하여 복귀 한 경우 개선 된 점심 시간 런타임을보고하지만 그 함정에 빠지지는 않습니다. 실제로 피보나치 힙은 실제로 끔찍한 성능을 보입니다.

Dijkstra 's가 충분하지 않은 경우 A*-search 방법을 살펴보십시오. 모든 알고리즘 질문에서와 마찬가지로 CLR이 최고의 가이드이지만 Wikipedia는 아주 가깝습니다. 희망이 도움이됩니다!

Answer 2

나는 또한 정말 더 코드 나 정보없이 무슨 일이 일어나고 있는지 알 수는 없지만,이 직결되어 다음 firststep_distance (내가 가정하는

 if (firststep_distance <= maxTotalDist): 
      newPath = directedDFS(digraph, node, end, maxTotalDist-firststep_distance) 

각 재귀 호출에 maxTotalDistance 감소하는 경우 경로의 무게)는 남은 거리보다 커야합니다.