재귀 함수의 반복 문제

Question

주어진 코드는 maxTotalDist 및 maxDistOutdoors 제약 조건을 기반으로 최단 경로를 찾는 데 사용됩니다. 나는 그것을 가지고있다 대부분은 일하고있다. 그러나 내가 가지고있는 문제는 내가 (어떤 주어진 문제들에서) 길을 찾을 수있다하더라도 그것이다. 나는 을 확인할 수 없다.을 찾았습니다.

예를 들어 경로가 발견되면 코드의 "visited"목록은 내가 얻은 전체 경로 여야합니다 (경로는 "가장 짧아야" 통로"). 그러나, 어떤 노드가 내가 타격 중인지 확인하기 위해 구현하려고하는 모든 인쇄 문은 인쇄되지 않습니다. (예 : 노드 'A'에서 노드 'C'로가는 경로를 찾으려고 할 때, 노드 A는 자식 [ 'b', 'c']를가집니다. 만약 샘플을 만들면 문 (방문한 경우 [=] c '), print 문은 꺼지지 않습니다.

어쨌든, 나는 이것이 정말로 잘못 쓰여졌을 것이라는 것을 알고 있지만, 도움이 될 것입니다. 감사.

def bruteForceSearch1(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 

    #This is the iterator talked about in the question 
    for node in digraph.childrenOf(start): 

     if (str(node) not in visited): 
      visited = visited + [str(node)] 

      #Sample print statement 
      if visited[0] == 'nodeName': 
       print "Node is part of search" 

      newPath = bruteForceSearch1(digraph, node, end, maxTotalDist, maxDistOutdoors, visited) 
      if newPath == None: 
       continue 
      if shortest != None: 
       totalShort, outdoorShort = digraph.getDistances(shortest) 
      total, outdoor = digraph.getDistances(path + newPath) 
      if (total <= maxTotalDist) and (outdoor <= maxDistOutdoors): 
       if (shortest == None): 
        shortest = newPath 
       else: 
        if (len(newPath) < len(shortest)): 
         shortest = newPath 
        elif (len(newPath) == len(shortest)) and (total <= totalShort) and (outdoor <= outdoorShort): 
         shortest = newPath 
    if shortest != None: 
     path = path + shortest 
    else: 
     path = None 
    return path 

Answer 1

모든 재귀 호출에는 visited[0]과 동일한 값이 표시됩니다. 항상 원래 start 가치의 첫 번째 자녀가됩니다. 목록의 끝에 다른 모든 값을 추가하기 때문에 visited의 첫 번째 값으로 그 자식을 대체 할 수있는 것은 없습니다.

아마도 visited[0] 대신 node과 같은 특정 이름을 확인하고 싶습니다.

코드에 다른 문제가있을 수 있습니다. 예를 들어 a->b 경로가있는 경우 경로 a->c->b을 고려하지 않습니다 (을 선택한 후 b이 visited에 있기 때문에). 삼각형 부등식이 유지되지 않는 일부 그래프에서는 첫 번째 경로가 두 번째 경로보다 짧을 수 있습니다. 그래프에서 가능하지 않다면 괜찮을 수도 있지만 모든 그래프에서 가정해야하는 것은 아닙니다.