SWI-пролог: как составить круговой список, используя некоторые факты

Question

loop1(a).
loop1(b).
loop1(c).
loop1(d).

circular(d, a).
circular(b, c).
circular(b, d).
circular(a, b).

поэтому, когда я звоню:

in_cycle(a, Cycle). 

вернется:

[a,b,d,a]

если я позвоню:

in_cycle(b, Cycle).

вернется:

[b,d,a,b].

однако, если вы позвоните:

in_cycle(c, Cycle).

вернется:

false. (because no loop is included).

вот моя попытка:

in_cycle(C,Cycle) :- circular(C,Cycle1),in_cycle(Cycle1,Cycle).

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

Буду признателен, если кто-нибудь сможет мне помочь!

------- ------- обновленный

check([Y,_|Z]) :- check([Y|Z]).

in_cycle(C, [C]).
in_cycle(C, [C, C1|Cycle]) :-  circular(C, C1),check([C,C1|Cycle]),
                               in_cycle(C1, [C1|Cycle]).

Answer 1

Узел находится в цикле, если вы можете найти путь назад к этому самому узлу. Использование path/4:

in_cycle(C, [C|Cs]) :-
   circular(C, A),
   path(circular, Cs, A,C).

---

Теперь, этот предикат заканчивается? Как мы можем проверить это систематически? Как мы можем гарантировать, что мы не забудем ни одного особого случая? Для чистых монотонных программ, подобных этой, тестирование на завершение является тривиальным ¹ : просто возьмите самый общий запрос ! То есть:

?- in_cycle(C, Cs).
   C = d,
   Cs = "dabd"           % [d,a,b,d]
;  C = b,
   Cs = "bdab"
;  C = a, Cs = "abda"
;  false.                % it terminates!

(См. этот ответ как получить "bdab" вместо [b,d,a,b]).

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

И все это справедливо даже для любых переменных, свободных для фактов circular/2. Однако это доказательство не может быть выполнено так легко, как доказательство для определенного набора фактов.

---

^{_{1 Обратите внимание, что тривиально означает принадлежность к тривиум .}}

Answer 2

1. Какой самый короткий цикл вы могли бы иметь в своей базе данных фактов? Будет ли circular(a, a). цикл [a]? Знание самого короткого цикла может помочь вам найти (одно из) условие (я) завершения для вашего предиката.
2. Чтобы найти список, ваш предикат должен создать его. Ваш in_cycle/2 никогда не упоминает никаких списков. Вам нужно использовать конструкцию [Head | Tail] где-то там, чтобы иметь возможность добавлять элементы в список.
3. Вы уже знаете кое-что о том, как выглядит ваш циклический список. Первый и последний элементы совпадают, и они совпадают с символом, для которого вы пытаетесь найти цикл. Используйте эту информацию.
4. Чтобы узнать, когда вы завершили цикл, вам нужно запомнить, с какого символа вы начали. Чтобы быть в состоянии сделать это с помощью рекурсии, вам нужно сохранять состояние. Так что вам понадобится дополнительный предикат, где вы сохраняете это состояние. Например. что-то с предикатом типа in_cycle(Current_symbol, Cycle, Start_symbol). Затем вы можете позвонить с вашего in_cycle/2.

Давайте посмотрим на вашу попытку:

in_cycle(C, Cycle) :-
    circular(C, Cycle1),
    in_cycle(Cycle1, Cycle).

Вы можете использовать команду trace в приглашении, чтобы увидеть, что происходит: trace, in_cycle(a, X).

Нажмите Пробел , чтобы пройтись по вашей программе. Нажмите h для получения справки и a для выхода. Используйте notrace., чтобы снова выйти из режима трассировки.

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

Давайте попробуем составить список. Как я упоминал в пункте (3), вы уже знаете кое-что о списке. Первый элемент списка совпадает с первым аргументом in_cycle. Более того, элемент second в списке совпадает с элементом, который вы найдете в circular/2. Итак, мы знаем, что цикл имеет как минимум два элемента. Как насчет этого?

in_cycle(First, [First, Next|Cycle]) :-
    circular(First, Next),
    in_cycle(Next, [Next|Cycle]).

Если вы проследите это сейчас, вы увидите, что с X что-то происходит, но на самом деле ничего полезного нет. Cycle остается загадкой, и мы просто бесконечно изучаем факты. Вам нужно какое-то конечное условие здесь. Давайте попробуем простой:

in_cycle(First, [First]).
in_cycle(First, [First, Next|Cycle]) :-
    circular(First, Next),
    in_cycle(Next, [Next|Cycle]).

Вау! in_cycle(a, X) неожиданно дает результаты! Кажется, все возможные списки с использованием circular соединений начинаются с a. Это не совсем то, что мы хотим, но, может быть, мы приближаемся?

Одна проблема с этим заключается в том, что in_cycle(Next, [Next|Cycle]) на самом деле не правильно!

Если вы сделаете in_cycle(a, X), вы уже знаете, что X должно стать [a, b, d, a], поэтому, заполнив эти значения в in_cycle(First, [First, Next|Cycle]), вы получите:

First = a
Next = b
Cycle = [d, a]

Когда вы добираетесь до in_cycle(Next, [Next|Cycle]), это означает, что это in_cycle(b, [b, d, a]). Но [b, d, a] это не цикл! Вы должны уметь как-то различать эти две ситуации. Один из способов сделать это - вызвать отдельный предикат, как я упоминал в (4), чтобы отследить, каким был ваш начальный элемент.