Поиск в глубину (графовый метод)

Я давно работаю над этой проблемой и почти достиг ее. По сути, я реализую поиск в глубину, отслеживая узлы, чтобы найти целевой узел и иметь возможность отслеживать путь от начального узла к целевому узлу. Я могу найти целевой узел и отслеживать путь, но проблема заключается в следующем:

Когда я пытаюсь воссоздать свой маршрут, я застреваю в бесконечном цикле, где, скажем, узел x1 указывает на узел x2, а узел x2 указывает на узел x1. Вот соответствующий код (на питоне):

# Starting position
stack = util.Stack()
currentState = problem.getStartState()
goalState = []
directions = {}
visited = []


if problem.isGoalState(currentState): return []
else:
    stack.push(currentState)

while stack.isEmpty() == False:
    currentState = stack.pop()
    if currentState in visited: 
        continue
    if problem.isGoalState(currentState): 
        goalState = currentState
        break
    visited.append(currentState)
    for state in problem.getSuccessors(currentState):
        stack.push(state[0])
        directions[state[0]] = (currentState, state[1])

print goalState
goalState = directions[goalState][0]
print goalState
goalState = directions[goalState][0]
print goalState
goalState = directions[goalState][0]
print goalState
goalState = directions[goalState][0]
print goalState
goalState = directions[goalState][0]
print goalState
goalState = directions[goalState][0]
print goalState
goalState = directions[goalState][0]

Каждое состояние представляет собой кортеж ((координата узла), «направление движения», стоимость). Я понимаю, что мне нужен цикл while, чтобы правильно вернуться к начальному состоянию, конечная часть кода предназначена только для того, чтобы показать вам, ребята, этот вывод:

(1, 1)
(2, 1)
(2, 2)
(2, 1)
(2, 2)
(2, 1)
(2, 2)

Любая помощь будет ОЧЕНЬ оценена! Пишу сюда впервые, надеюсь, все сделал правильно.


python algorithm depth depth-first-search
person devii    schedule 27.09.2014    source источник
comment
В алгоритме DFS вы должны пометить каждый узел как посещенный и проверить, посещен ли узел, прежде чем продолжить, чтобы избежать таких бесконечных циклов. Похоже, вы пытались это сделать. Вам нужно запустить отладчик, чтобы определить, почему он работает не так, как вы ожидаете.   -  person Code-Apprentice    schedule 28.09.2014

Ответы (1)


arrow_upward
1
arrow_downward

Вам нужно сохранить направление при посещении узла, а не при добавлении узла в стек.

В текущем коде вы будете перезаписывать словарь маршрутов.

(Чтобы исправить это, например, вы можете сохранить как новый узел, так и родительский узел в стеке, а затем записывать словарь направлений только при посещении узла.)

Кстати:

  1. тестирование, если узлы находятся в посещении, более эффективно, если вы используете набор, а не список
  2. если вам нужен путь с минимальной стоимостью, вы можете захотеть изучить приоритетную очередь (например, предоставленную модулем heapq Python) вместо стека
person Peter de Rivaz    schedule 27.09.2014
comment
Большое спасибо! Я слишком долго ломал голову над этим и никак не мог понять свою ошибку. - person devii; 28.09.2014