매개 변수 내에서 가장 짧은 그래프 찾기

def shortestPath(digraph, start, end, maxTotalDist, maxDistOutdoors, 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 
    MinimumTotalDist = 0 
    for node in digraph.childrenOf(start): 
     if (str(node) not in visited): #avoid cycles 
      visited = visited + [str(node)] #new list 
      FirstStepDist = digraph.childrenOf(start)[node][0] 
      FirstStepOutdoors = digraph.childrenOf(start)[node][1] 
      newPath = shortestPath(digraph, node, end, maxTotalDist, maxDistOutdoors, visited) 
      if newPath == None: 
       continue 
      TotalDist = int(FirstStepDist) + TotalDistance(digraph,newPath) 
      TotalOutdoorDist = int(FirstStepOutdoors) + TotalOutdoorDistance(digraph,newPath) 
      **if TotalOutdoorDist > maxDistOutdoors: 
       continue** 
      if (shortest == None or TotalDist < MinimumTotalDist): 
       shortest = newPath 
       MinimumTotalDist = TotalDist 
    if shortest != None: 
     path = path + shortest 
    else: 
     path = None 

    if TotalDistance(digraph,path) <= maxDistOutdoors: 
     return path

정확한 답을주지 못합니다. 올바른 경로를 반환합니다. 그러나 반환하는 경로는 최단 경로가 아닙니다. 전체 옥외 거리가 maxDistOutdoors 제약 조건보다 큰 경우 경로를 건너 뛰는 굵은 선으로 문제가 발생하지만이를 변경하는 방법을 모르겠습니다. 그 굵은 선을 제거 할 때 올바른 최소 경로를 얻지 만 maxDistOutdoors보다 적은 총 거리가있는 최소 경로를 찾고 싶기 때문에 거기에 체크를해야합니다.매개 변수 내에서 가장 짧은 그래프 찾기

인쇄 문구를 이미 시험해 보았습니다. 이제 막 포기합니다. 나는 왜 지금 그것이 틀린 지 이해하지 못한다.

출처

2011-05-07 Glassjawed

코드가 잘못된 이유가 확실하지 않습니다. 그러나, 당신은 그것이 매우 비효율적이라는 것을 알고 있습니까? 가장 짧은 경로를 찾으려면 시작 노드에서 시작하는 가능한 모든 비순환 경로를 검색하는 것처럼 보입니다. 일을하는 데 훨씬 빠른 방법이 있습니다. –

나는 알고있다. 그러나 나는 그런 방법을 코딩하는 법을 모른다. 그래, 내 if 문이 어떤 결과를 왜 버리는 이유는 끝내지 못한다. – Glassjawed

간단한 최단 경로 기능을 보려면 http://www.python.org/doc/essays/graphs/를 참조하십시오. 도움이 될지도 몰라. –

사용중인 알고리즘 (DFS)이 최단 경로를 반환하지 않기 때문에 코드에서 가능한 최단 경로를 반환하지 않습니다. 대신 BFS을 사용해보세요.

그러나 무게 제한 (실외 거리)이 있으므로 Dijkstra's shortest path algorithm을 확인해야합니다. 제약 조건을 쉽게 통합 할 수 있어야합니다.

출처

2011-06-17 03:28:54

매개 변수 내에서 가장 짧은 그래프 찾기

답변

관련 문제