Найти все возможные пути без петель в графике в Прологе

Question

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

?- find(a,[r(a,[b,d]),r(b,[a,c,e]),r(c,[b]),r(d,[a,e]), 
    r(e,[b,d,f]),r(f,[e,g]),r(g,[f])],Path). 

Пролог должен возвращать все возможные пути в данном графике. Термины R (X, Список) определит граф, а это означает, что узлы в списке могут быть достигнуты от узла X. В этом случае выходной сигнал будет:

Path = [a,b,c] ; 
Path = [a,b,e,d] ; 
Path = [a,b,e,f,g] ; 
Path = [a,d,e,b,c] ; 
Path = [a,d,e,f,g] ; 
false. 

Хотя я получить повесить многочисленные решения здесь, в SE и в Интернете в целом, к аналогичным проблемам, я как-то слишком глуп, чтобы понять, как работать с определением графика в этом задании.

Я полагаю, что find (Start, ...) следует вызывать рекурсивно со всеми членами списка в r (Start, List), но в качестве новичка для Prolog (мы просто сделали стандартное семейное древо. ..) Я не знаю, как это сделать.

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

/Edit:

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

find([],_,_). 

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

find(_,[],_). 

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

Теперь фактический звонок. Возможно, что-то вроде

find(Start,[r(Start,[Adjacent|Restadj])|Rest],Path):- 
      find(???). 

Моих проблем здесь следующее:

-Кака я сделать программу использовать элементы списка в г (...) термин, как при следующем запуске?

-Как проверить, если узел уже «посетили»/Как я могу удалить узел из определенного списка в г

-Как я помещал найденные узлы в списке Path? Просто добавить? Или выполнить рекурсивный вызов с помощью чего-то вроде [Путь | Старт]?

Как вы видите, это не так много. Некоторые наводящие вопросы, было бы хорошо, так как Пролог кажется довольно интересным, и поэтому интересно узнать ...

---

Пробыв некоторое время с аккуратным инструментом трассировки PDT-Eclipse, я думаю, я понял, что делает программа. То, что я не понимаю на этом, - это то, почему последний узел всегда теряется. После того, как откат завершился неудачно, например, потому что r (c, [b]) - следующий найденный член, а memberchk (b, [b]) терпит неудачу из-за отрицания (это то, что я делаю +), и никакого другого термина с r (c , X), он начинается с поиска других возможностей перехода от узла b, у которого есть соседние узлы, оставшиеся в r (b, [...]). Но почему программа забывает поместить узел c в список Path?Есть ли возможность сделать какой-то, если-то-иначе в случае

member(r(Node, Adjacent), Graph), 
member(AdjNode, Adjacent), 
\+ memberchk(AdjNode, Seen), 

не удается, еще добавить последний узел в пути?

Answer 1

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

find(_, _, []). 
find(Node, Graph, [Node|Path]) :- 
    member(r(Node,Adjacent), Graph), 
    member(AdjNode, Adjacent), 
    find(AdjNode, Graph, Path). 

Посмотрите, как я использую member/2 найти данные в графике. Это решение неверно, потому что оно петли. Улучшение может быть таким:

find(Node, Graph, Path) :- find(Node, Graph, Path, []). 

find(_, _, [], _). 
find(Node, Graph, [Node|Path], Seen) :- 
    member(r(Node, Adjacent), Graph), 
    member(AdjNode, Adjacent), 
    \+ memberchk(AdjNode, Seen), 
    find(AdjNode, Graph, Path, [Node|Seen]). 

Это одна в основном такая же, как выше версии, кроме него есть «видели» список, чтобы отслеживать, где она уже была. Это все равно не дает желаемого результата, но я думаю, этого будет достаточно, чтобы вы на правильном пути.

Редактировать в ответ на ваши изменения,

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

Да. Я выбрал ваш первый случай, потому что я не думаю, что вы можете безопасно «потреблять» график во время обхода. Я полагаю, вы могли бы использовать select/3 вместо member/2 и передать граф без этого узла вперед. Это может быть интересно попробовать (предложение!).

• Как мне сделать программу использовать элементы списка в г (...) срок, как при следующем запуске?

Как было показано, использовать member/2 для извлечения вещи из графика. Это смешно, потому что вы использовали точное слово для предиката, в котором вы нуждаетесь. :)

• Как проверить, если узел уже «посетили»/Как я могу удалить узел из определенного списка в г

Как показано на втором наборе кода, у вас есть другой параметр для вашего вспомогательного предиката и используйте memberchk/3 или member/3.

• Как я кладу найденные узлы в списке Path? Просто добавить? Или выполнить рекурсивный вызов с помощью чего-то вроде [Путь | Старт]?

Я пошел с рекурсивным звонком. append/3 было бы дороже.

Edit: Использование findall/3 на комментарий Уилла, мы можем найти все пути сразу:

all_paths(From, Graph, Paths) :- findall(Path, find(From, Graph, Path), Paths). 

Вы можете вызвать это так:

?- all_paths(a, [r(a,[b,d]),r(b,[a,c,e]),r(c,[b]),r(d,[a,e]), 
       r(e,[b,d,f]),r(f,[e,g]),r(g,[f])], AllPaths). 

Я не проверял, что но он должен работать.

Answer 2

здание на отлично ясном кода Даниэль Лайонс, в ширину первого поиска:

all_paths(Node, Graph, Paths) :- 
    bfs(Graph, [[Node]-[]], R, []),  % or dfs(...) 
    maplist(fst, Paths, R). 

fst(A, A-_).  % utility 
pair(B, A, A-B). % helpers 
add(LS,H,[H|LS]). % 

bfs(_G, [], Z, Z).    % queue is empty 
bfs(Graph, [H|Q], [H|R], Z) :- 
    H = Path-Seen, Path = [Node|_], 
    findall(Next, member(r(Node, Next), Graph), NS), 
    flatten_diff(NS, Seen, WS), % working set of nodes 
    maplist(add(Path), WS, PS), % new paths 
    maplist(pair([Node|Seen]), PS, QH), % new addition to the queue 
    %% append(QH, Q, Q2),  % DFS 
    append( Q, QH, Q2),  % BFS 
    bfs(Graph, Q2, R, Z). 

(не проверено). flatten_diff(A,B,C) должен сгладить список списков A, удаляя его элементы, которые также отображаются в списке B, в результате чего получается список C.

---

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

find(Node, Graph, [Node|Path]) :- find(Node, Graph, Path, []). 

find(_, _, [], _). 
find(Node, Graph, [AdjNode|Path], Seen) :- 
    member(r(Node, Adjacent), Graph), 
    member(AdjNode, Adjacent), 
    \+ memberchk(AdjNode, Seen), 
    find(AdjNode, Graph, Path, [Node|Seen]). 

Там нет пустых путей, производимых в настоящее время, и она работает, как ожидалось:

11 ?- find(a,[r(a,[b,d]),r(b,[a,c,e]),r(c,[b]), r(d,[a,g]), 
       r(e,[b,d,f]),r(f,[e,g]),r(g,[f])], Path). 
Path = [a] ; 
Path = [a, b] ; 
Path = [a, b, c] ; 
Path = [a, b, e] ; 
Path = [a, b, e, d] ; 
Path = [a, b, e, d, g] ; 
Path = [a, b, e, d, g, f] ; 
Path = [a, b, e, f] ; 
Path = [a, b, e, f, g] ; 
Path = [a, d] ; 
Path = [a, d, g] ; 
Path = [a, d, g, f] ; 
Path = [a, d, g, f, e] ; 
Path = [a, d, g, f, e, b] ; 
Path = [a, d, g, f, e, b, c] ; 
false.