Не думайте с точки зрения циклов, нуждающихся в операторах выхода. На самом деле, вообще не используйте отладчик, это сильно сбивает с толку, даже если вы действительно знаете, что происходит в процессоре Prolog.
Вы начинаете с сети узлов, соединенных набором ребер ( отношение).
В этом случае узлы представлены атомами (обозначающими города), набор ребер отношения называется directFlight/2.
Теперь вы хотите наложить еще один набор ребер, который называется flight/2.
Поэтому вы должны спросить себя, когда у меня есть flight/2 ребро между двумя атомами A и B
Существует два случая:
- Если между ними есть
directFlight/2 (базовый случай) - Если существует промежуточный узел
I таким, что существует flight/2 от A до I и directFlight/2 между I и B. - В качестве альтернативы, если существует промежуточный узел
I, такой что существует directFlight/2 между A и I и flight/2 от I до B.
Пролог найдет flight/2 край сам по себе при запросе
flight(sofia, dublin).
(так же, как реляционная база данных находит результат запроса SQL), но вы должны обратить внимание на завершение. Альтернативный случай (3) выше приведет к успешному поиску или «ложь». Случай (2) приведет к не прекращению - полностью из-за стратегии поиска Пролога (где должны быть приняты решения о том, как машина реального мира выполняет поиск в сети, в данном случае, сначала в глубину, в крайнем левом направлении).
Вот базовый случай для flight/2 (первое изображение), все flight/2, выведенные рекурсией 1 глубокого вызова, и все flight/2, выведенные рекурсией 2 глубоких вызовов.
Итак:
directFlight(sofia, varna).
directFlight(sofia, paris).
directFlight(sofia, london).
directFlight(london, edinburg).
directFlight(paris, new_york).
directFlight(new_york, seattle).
directFlight(london, dublin).
flight(City1, City2) :- directFlight(City1, City2).
flight(City1, City2) :- directFlight(City1, City3), flight(City3, City2).
А затем:
?- flight(sofia,dublin).
true ;
false.
?- flight(sofia,X).
X = varna ;
X = paris ;
X = london ;
X = new_york ;
X = seattle ;
X = edinburg ;
X = dublin ;
false.
?- flight(X,sofia).
false.
Приложение 1
Выше Программа может быть прочитана:
- "от ВЛЕВО: - ВПРАВО " (как это делает Пролог). Это поиск, чтобы установить, имеет ли место факт
flight/2 или могут быть найдены значения, которые делают его истинным. - "от ВПРАВО -: ВЛЕВО ". Ментальный образ постоянно накапливает новые факты о
flight/2, пока не соберет их все и больше ничего не будет добавлено: поиск снизу вверх (это как-то легче для мозга, по крайней мере для меня). Безопаснее, чем поиск, так как вы не рискуете попасть в бесконечный провал рекурсии только потому, что предложения расположены неудачно, и это то, что делают некоторые реализации Datalog.
Логическое чтение (или 2) оператор («программа»), который задает ограничения на то, как flight/2 должен быть структурирован:
∀(City1, City2) :
(flight(City1, City2) <=
directFlight(City1, City2))
∧
∀(City1, City2) :
(flight(City1, City2) <=
(∃City3: directFlight(City1, City3) ∧ flight(City3, City2))
Обратите внимание, что в приведенном выше нет ничего, что исключало бы, что flight(X,Y) может выполняться для ДРУГОГО причины, чем заявлено. Мы предполагаем, однако, что мы знаем все о том, когда flight(X,Y) имеет место: Предположение о закрытом мире.
Приложение 2
Часто забывают, что рекурсивного вызова вообще не требуется. Рекурсию можно «развернуть», а прямое связывание можно сделать явным:
directFlight(sofia, varna).
directFlight(sofia, paris).
directFlight(sofia, london).
directFlight(london, edinburg).
directFlight(paris, new_york).
directFlight(new_york, seattle).
directFlight(london, dublin).
flight(City1, City2) :- directFlight(City1, City2).
flight(City1, City2) :- directFlight(City1, Ia),
directFlight(Ia, City2).
flight(City1, City2) :- directFlight(City1, Ia),
directFlight(Ia, Ib),
directFlight(Ib, City2).
flight(City1, City2) :- directFlight(City1, Ia),
directFlight(Ia, Ib),
directFlight(Ib, Ic),
directFlight(Ic, City2).
Ни один из городов не расположен на расстоянии более 3 прыжков, поэтому вышеуказанная программа найдет все flight/2 соединений.
На самом деле, другим упражнением было бы создание вышеуказанной программы с указанием в качестве аргумента "максимальной глубины".