Пролог Путь Поиск с предпосылками

Question

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

Если задано задание T в сети, путь к T представляет собой список заданий. начиная с задачи X, которая не имеет предварительных условий, заканчивая T и так что каждый элемент списка, кроме X, имеет своего предшественника в виде Предпосылка.

• Если у задачи T нет предварительных условий, то существует единственный путь к ней по списку [T].

• В противном случае пути к T можно найти, рассчитав список всех пути к предпосылкам T и расширение этих путей с помощью элемента Т.

• Список всех путей к задачам в списке Ts можно рассчитать, запустив с пустым списком и добавлением путей, которые ведут к каждому последовательный элемент.

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

?- paths(f,Paths).

Paths = [[b, c, f]]

?- paths(g,Paths).

Paths = [[e, g], [b, c, f, g], [k,h,g]].

Предпосылки сделаны так:

prereqs(e,[]).
prereqs(f,[c]).
prereqs(g,[e,f,h]).

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

add(X, List, [X|List]).

path(T, [H|Hs]) :-
    prereqs(T, []),
    add(T, [], [H|Hs]).

path(T, [H|Hs]) :-
    prereqs(T, [N|_]),
    add(T,[] , Hs),
    path(N, H).

Я получаю ответы на вопросы:

?- path(f, Path).
Path = [[[b], c], f] .

?- path(e, Path).
Path = [e] .

На данный момент, я не понимаю, как сделать это правильно.

Answer 1

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

Давайте попробуем понять, что означает add в двух случаях, когда вы его используете. В первом пункте path у вас есть цель add(T, [], [H|Hs]). Мы можем спросить Пролога, что это значит:

?- add(T, [], [H|Hs]).
T = H,
Hs = [].

Таким образом, первое предложение path может применяться, только если Hs является пустым списком (следовательно, [H|Hs] совпадает с [H]), а T совпадает с H. Поэтому мы можем переписать это предложение так:

path(T, [T]) :-
    prereqs(T, []).

Это выглядит разумно, и на самом деле это прямой перевод на пролог соответствующей части спецификации:

Если задача T не имеет предварительных условий, то существует единственный путь к ней, заданный списком [T].

Теперь давайте попробуем то же самое для использования add во втором предложении path. Он принимает следующую форму:

?- add(T, [], Hs).
Hs = [T].

Упрощение второго предложения path, как указано выше, с использованием этого уравнения приводит к:

path(T, [H, T]) :-
    prereqs(T, [N|_]),
    path(N, H).

Обратите внимание, что вторым аргументом в заголовке является [H, T], поскольку [H|Hs] = [H|[T]] = [H, T]. Так что это может быть успешным только для двухэлементных списков, что вы и видите. (Первым элементом каждого из этих списков может быть другой вложенный двухэлементный список.)

Вместо этого вы ищете нечто большее:

path(T, Path) :-
    prereqs(T, [N|_]),
    path(N, PathToPrerequisite),
    append(PathToPrerequisite, [T], Path).

Это все еще имеет ошибку в том, что он не может найти все пути, но он может, по крайней мере, уже генерировать те, которые он нашел, в правильном формате:

?- path(f, Path).
Path = [b, c, f] ;
false.