Реализация глубины Ограниченный поиск путей со стеком

Question

Эй, как название говорит, что я пытаюсь реализовать ограниченный по глубине поиск в Python3, который возвращает путь, заданный графиком, вершину вершины и вершину цели. Я немного борюсь с тем, как применять предел для поиска. До сих пор у меня есть:

def dfs(g, v, goal, limit=-1): 

    SENTINEL = object()  
    visitedStack = [v] 
    path = "" 

    while visitedStack: 
     currentVertex = visitedStack.pop()  

     if g.getVertex(currentVertex) != None: 
      if g.getVertex(currentVertex).visited == False: 
       path += currentVertex + ' -> ' 

       g.getVertex(currentVertex).hasBeenVisited() 

       if currentVertex == goal: 
        return path[:-3] 

       elif currentVertex == SENTINEL: 
        limit += 1 

       elif limit != 0: 
        limit -= 1 
        visitedStack.append(SENTINEL) 
        visitedStack.extend(g.getVertex(currentVertex).getConnections()) 

    return "Depth limit was reached" 

EDIT: Я изменил часть кода, чтобы проверить посещаемые вершины. После моего редактирования возвращаемый поиск не работает должным образом. Например, я установил ограничение глубины на 3, но вернемся к пути 4 или 5. В других случаях я установил предел в 7 и вернул «достигнутый лимит». ПРИМЕЧАНИЕ: наименьший путь равен 3

Answer 1

Когда поиск идет на более глубокий уровень, нажмите на дозор в стек и уменьшите предел. Когда вы выталкиваете часового с шагом стека уровня.

def dfs_limit(g, start, goal, limit=-1): 
    ''' 
    Perform depth first search of graph g. 
    if limit >= 0, that is the maximum depth of the search. 
    ''' 
    SENTINEL = object() 
    visitedStack = [start] 
    path = [] 

    while visitedStack: 
     currentVertex = visitedStack.pop() 

     if currentVertex == goal: 
      path.append(currentVertex) 
      return ' -> '.join(path) 

     elif currentVertex == SENTINEL: 
      #finished this level; go back up one level 
      limit += 1 
      path.pop() 

     elif limit != 0: 
      # go one level deeper, push sentinel 
      limit -= 1 
      path.append(currentVertex) 
      visitedStack.append(SENTINEL) 
      visitedStack.extend(g.getVertex(currentVertex).getConnections()) 

Если есть петли или несколько маршрутов через граф, вам необходимо также следить за которые посетили узлы, так что вы не дублировать работу или получить в бесконечном цикле.