поиск в глубине первого графика, который возвращает путь к цели - PullRequest
Новая
       66

поиск в глубине первого графика, который возвращает путь к цели

6 голосов
/ 11 сентября 2011

Я пробовал это всю неделю и не могу, на всю жизнь, понять это.

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

Я так растерялся, что даже не могу точно сформулировать, в чем проблема, кроме рекурсии.

Спасибо за любую помощь.

РЕДАКТИРОВАТЬ: ОК, я немного уточнить. Меня смущает то, что путь возвращается, когда у узла нет соседей. Сначала может быть возвращен целевой путь, но затем, поскольку помощник все еще рекурсивен, он может вернуть тупиковый путь. Я полагаю, что запутался в возврате.

Ответы [ 2 ]

6 голосов
/ 11 сентября 2011

Википедия на самом деле имеет довольно неплохой псевдокод для обхода в глубину. Эти алгоритмы обхода маркируют все узлы на графике в порядке их появления в обходе. Вместо этого вы хотите сразу же вернуть путь к цели, когда цель найдена.

Итак, давайте изменим алгоритм Википедии: 

( INCORRECT ALGORITHM DELETED WHICH THE OP COMMENTED ON CORRECTLY BELOW )

Вот реализация Python: 

g = {
    'A': ['B', 'C', 'D'],
    'B': ['C', 'E', 'F'],
    'C': ['A'],
    'D': ['B', 'F', 'G', 'H'],
    'E': ['G'],
    'F': ['A', 'F'],
    'G': ['H', 'I'],
    'H': [],
    'I': []
}

def DFS(g, v, goal, explored, path_so_far):
    """ Returns path from v to goal in g as a string (Hack) """
    explored.add(v)
    if v == goal: 
        return path_so_far + v
    for w in g[v]:
        if w not in explored:
            p = DFS(g, w, goal, explored, path_so_far + v)
            if p: 
                return p
    return ""

# Hack unit test
assert DFS(g, 'A', 'I', set(), "") == "ABEGI"
assert DFS(g, 'A', 'E', set(), "") == "ABE"
assert DFS(g, 'B', 'B', set(), "") == "B"
assert DFS(g, 'B', 'B', set(), "") == "B"
assert DFS(g, 'A', 'M', set(), "") == ""
assert DFS(g, 'B', 'A', set(), "") == "BCA"
assert DFS(g, 'E', 'A', set(), "") == ""

Идея в том, что вы хотите найти в графе g путь от v до goal, учитывая, что вы уже прошли по пути в path_so_far. path_so_far должен закончиться как раз перед v.

Если v является целью, вы можете добавить v к этому пути и все.

В противном случае вам нужно будет исследовать все ребра, исходящие из v, которые еще не исследовали узлы на другом конце ребра. Для каждого из этих ребер вы можете выполнять поиск (рекурсивно), используя ваш путь до текущего узла плюс Если от v нет пути к цели, вы вернете пустой путь.

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

1 голос
/ 11 сентября 2011

Рекурсия сводится к сведению проблемы к набору мелких проблем.

В этом случае, допустим, вы пытаетесь найти маршрут от узла A к узлу Z. Сначала вы посмотрите на соседей AДопустим, это B, C и D.

Теперь у вас есть три подзадачи: поиск маршрута от B до Z, от C до Z и от D до Z. Если вы можете решить любую изЭти проблемы, вы также решили большую проблему поиска пути от А до Я.

Итак, вы рекурсивны.Вы используете свой метод findPath на B, на C и на D, предоставляя каждому список посещенных до сих пор узлов, содержащих A (чтобы предотвратить их обратный ход) [1].Если кто-то из них говорит: «Я нашел путь», вы выбираете тот путь, который они возвращают, вставляете А в начале и называете его днем.

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

[1] Примечание: если вы очень умны, вы также поместите B в список, который вы передаете рекурсивному вызову на C, и B + C в список, который вы передаете D.

...