Пролог графа глубина первого поиска - PullRequest
Новая
       35

Пролог графа глубина первого поиска

0 голосов
/ 08 июня 2018

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

[0-[1,5], 1-[0,2], 2-[1,3], 3-[2,0], 5-[0]]

Это набор значений ключа, где ключ представляет узел, а список: -[] представляет егососедей.

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

dfs(v, visited):
  if visited[v] then return
  visited.insert(v)
  foreach neighbor of v:
    dfs(neighbor, visited)

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

Потому что, если я переведу это на пролог: 

% here Graph contains the entire key-value pairs list,
% Node-Neighbor is the current node with its neighbors.
dfs(Graph, Node-Neighbors, Visited) :-
    \+ member(Node, Visisted),
    % Now here I could get the next neighbor within neighbor, like so:
    member(Node1,Neighbors),
    % Then gets its own neighbors too by:
    member(Node1-Neighbors1, Graph),
    % but here I'm stuck...

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

Спасибо.

Ответы [ 2 ]

0 голосов
/ 09 июня 2018

Просто переведите ваш код в Пролог.Не думай об этом;скажи, что ты имеешь в виду: 

/* dfs(v, visited):
     if visited[v] then return
     visited.insert(v)
     foreach neighbor of v:
       dfs(neighbor, visited) */

dfs(Graph, V, Visited, Return) :-
   visited(V, Visited),
   return(Graph, V, Visited, Return).

dfs(Graph, V, Visited, Return) :-
   \+ visited(V, Visited),
   appended(Visited, [V], Visited2),
   neighbor(Graph, V, N),
   dfs(Graph, N, Visited2).

Предикаты visited/2, return/4, appended/3, neighbor/3 должны быть простыми в реализации.

Сначала правильность, а эффективность позже.

0 голосов
/ 09 июня 2018

Традиционный алгоритм DFS включает рекурсию и стек, который по сути является механизмом обратного отслеживания.В Прологе, если вы пытаетесь «накапливать» список, это может быть затруднительно, если необходимые элементы получены при возврате.

Следующий код представляет собой очень простую визуализацию поиска DFS и выпишетузлы в поиске DFS: 

dfs(Graph, StartNode) :-
    dfs(Graph, StartNode, []).

dfs(Graph, Node, Visited) :-
    \+ member(Node, Visited),
    member(Node-Neighbors, Graph),
    write(Node), nl,
    member(NextNode, Neighbors),
    dfs(Graph, NextNode, [Node|Visited]).

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

Запрашивая это, вы получите: 

| ?- dfs([0-[1,5], 1-[0,2], 2-[1,3], 3-[2,0], 5-[0]], 0).
0
1
2
3
5

yes
| ?-

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

dfs(Graph, StartNode, Node) :-
    dfs(Graph, StartNode, [], Node).

dfs(Graph, ThisNode, Visited, Node) :-
    \+  member(ThisNode, Visited),
    (   Node = ThisNode                     % Succeed finding a new node
    ;   member(ThisNode-Neighbors, Graph),  % Or... find the next node
        member(NextNode, Neighbors),
        dfs(Graph, NextNode, [ThisNode|Visited], Node)
    ).

В результате: 

| ?- dfs([0-[1,5], 1-[0,2], 2-[1,3], 3-[2,0], 5-[0]], 0, Node).

Node = 0 ? a

Node = 1

Node = 2

Node = 3

Node = 5

no
| ?-

Теперь вы можете использовать findall/3чтобы получить узлы в виде списка: 

dfs_path(Graph, StartNode, Nodes) :-
    findall(Node, dfs(Graph, StartNode, Node), Nodes).

Теперь вы можете написать: 

| ?- dfs_path([0-[1,5], 1-[0,2], 2-[1,3], 3-[2,0], 5-[0]], 0, Nodes).

Nodes = [0,1,2,3,5]

yes
| ?-
...