Как пролог проходит через этот код

Как работает этот код? Я wold жестко работал на первые возможные значения C и X, но как-то это петли.Как пролог проходит через этот код

path(A, B, [A, B], X) :- 
    route(A, B, X). 
path(A, B, PathAB, Length) :- 
    route(A, C, X), 
    path(C, B, PathCB, LengthCB), 
    PathAB = [A | PathCB], 
    Length is X + LengthCB.

есть routes оп ределяется, как route(bahirdar, mota, 32)..

источник

2016-02-04 Amanuel Nega

В этом случае Prolog не «зацикливается». Пролог пытается определить, является ли запрос «истинным». Если это правда, он переходит к следующему запросу (при использовании оператора запятой (',')). Если запрос является «ложным», то Prolog «обращается к предыдущему запросу» и пытается найти другой способ сделать его успешным (посредством различной инстанцирования переменных), и, если возможно, он снова двинется вперед. Таким образом, в действительности, он отскакивает назад и вперед, пытаясь сделать предикат успешным. :) – lurker

@ lurker Можете ли вы ответить на этот вопрос, это то, что я искал! Но где это ложь? Я не вижу там, где там ложь. –

Я опубликую что-нибудь более объяснительное позже этим вечером, когда у меня будет время (если кто-то не бьет меня к нему :) :). – lurker

Принимая простой пример, предположим, что у вас есть следующие факты:

foo(1). 
foo(2).

Затем запрос:

| ?- foo(X).

Пролог преуспеет с X = 1 и запрос:

X = 1 ?

? указывает, что была точка выбора (это foun г дополнительные возможности для изучения для foo), и если вы нажмете ; и Enter, это будет отступиться и попытаться найти другое решение, которое он делает, и предлагает:

X = 2 ?

Теперь, если нажать ; и Enter он потерпит неудачу и остановится, потому что он не сможет преуспеть в дальнейшем.

Давайте попробуем нечто более сложное с конъюнкцией. Используйте факты:

foo(1). 
foo(2). 
foo(3).

И правило:

odd(X) :- X /\ 1 =:= 1. % X is odd if X bit-wise and with 1 is 1

А потом сделать запрос, который говорит, что я хочу X быть fooи Я хочу X быть odd:

| ?- foo(X), odd(X). 
X = 1 ? ; 
X = 3 ? ; 
no 
| ?-

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

Пролог называет foo(X) и успешно с X = 1.
Пролог называет odd(1) (так как X инстанциируется как 1) и успешно
Пролог показывает результат X = 1.
Пользователь указывает на откат желательно (найти больше решений)
Пролог откатывается к odd(1), который не имеет переменные reinstantiate, поэтому Пролог откатывается далее
Пролог откатывается к foo(X) и успешно с X = 2 и переходит вперед снова
Пролог вызывает odd(2) и не работает.Неудача заставляет Пролог возвратиться к foo вызова
Пролог откатывается к foo(X) и преуспевает с X = 3 и исходящим вперед снова
Пролог вызывает odd(3) и преуспевает и отображает решение X = 3 <
...

Применить это сейчас к вашему предикату:

path(A, B, [A, B], X) :- 
    route(A, B, X). 
path(A, B, PathAB, Length) :- 
    route(A, C, X), 
    path(C, B, PathCB, LengthCB), 
    PathAB = [A | PathCB], 
    Length is X + LengthCB.

Если запрос сделан path, Prolog сначала пытается сопоставить запрос с заголовком первого предложения path(A, B, [A, B], X). Совпадение с этой головой означало бы, что третий аргумент должен быть списком, состоящим из ровно 2 элементов. Если есть совпадение, Prolog вызовет route(A, B, X). Если route(A, B, X) преуспеет, Prolog отображает значения A, B и X, что привело к успеху. Если пользователь запрашивает больше решений, Prolog будет возвращать назад, который либо (a) снова вызовет route(A, B, X), если в предыдущем вызове остался пункт выбора, либо (b) назад, и попытайтесь сопоставить исходный вызов с path со вторым , path(A, B, PathAB, Length). Аналогичным образом, если исходный вызов route(A, B, X) не удался, Prolog вернется, чтобы попытаться выполнить второе предложение.

Если вы выполняете второе предложение, у вас есть пример соединения, как показано в предыдущем упрощенном примере. Здесь это конъюнктивная последовательность из четырех вызовов, начинающихся с route(A, C, X). Prolog будет последовательно выполнять каждый из этих вызовов и переходить к следующему, пока предыдущие удастся. Когда возникает сбой, Prolog вернется к предыдущему вызову и, если есть точка выбора, попытается восстановить аргументы, чтобы сделать предыдущий вызов еще успешным и т. Д.

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

while (something) do 
    A 
    B 
    C 
end

Что бы выполнить, как A B C A B C A B C ..., пока условие цикла не будет выполнено. В Прологе, вы можете иметь:

A, 
B, 
C,

Что может выполнять, как: A(succeeds) B(fails - backtrack) A(succeeds) B(fails - backtrack) A(succeeds) B(succeeds) C(fails - backtrack) B(succeeds) C(succeeds), а затем, наконец, дают результаты.

Если бы это был действительно хороший ответ, я бы включил кучу диаграмм, чтобы проиллюстрировать это. Но я надеюсь, что описание поможет. :)

источник

2016-02-05 02:48:00 lurker

Как пролог проходит через этот код

ответ

Смежные вопросы