Как пролог использует возврат для поиска решений? - PullRequest
Новая
       20

Как пролог использует возврат для поиска решений?

0 голосов
/ 10 мая 2019

У меня есть этот пролог-код, который генерирует подмножества. 

subset([], []).

subset([E|Tail], [E|NTail]):-
     subset(Tail, NTail).

subset([_|Tail], NTail):-
     subset(Tail, NTail).

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

Если кто-то может шаг за шагом объяснить мне, как пролог находит решения для простого запроса, такого как 

subset([1,2,3],X).

, что было бы наиболее полезным.

1 Ответ

2 голосов
/ 10 мая 2019

Пролог пытается доказать subset([1,2,3],X). - это факт.Он делает это, пытаясь понять, поддерживает ли какой-либо из предикатов эту цель.

Первоначально он пытается subset([], []). - что не удается, поскольку [1,2,3] не может объединиться с [].

Затем он пытается subset([E|Tail], [E|NTail]):- subset(Tail, NTail)..Он может объединиться с головой, так что теперь он пытается доказать хвост.Он пытается доказать subset([2,3], NTail).

, что приводит к доказательству subset([3], NTail) (другой NTail) и затем subset([], NTail) (снова другой NTail).Теперь он преуспевает с subset([], [])., который завершает поиск в глубину, и теперь он выполняет резервное копирование стека вызовов, создавая результат для X, который равен [1|[2|[3|[]]]] или [1, 2, 3].

.в результате цель ?- subset([1,2,3],X). достигает успеха с [1, 2, 3].

Теперь, если вы попросите Пролога дать второй ответ, он смотрит на последний предикат, который сработал, и предполагает, что вместо этого он потерпел неудачу.Это была цель subset([], NTail).Для этой цели не существует предикатов, которые могли бы быть успешными, поэтому он возвращается еще на один шаг.Он доказал subset([3], NTail) с subset([E|Tail], [E|NTail]):- subset(Tail, NTail)., но теперь он будет предполагать, что это не удалось, поэтому он продолжает и пытается subset([_|Tail], NTail):- subset(Tail, NTail)., который успешен и эффективно отбрасывает 3, поэтому он продолжает как прежде, чтобы продолжить доказывать цель.В конечном итоге это приводит к [1, 2].

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

В конечном итоге вы получите этот результат: 

[1, 2, 3]
[1, 2]
[1, 3]
[1]
[2, 3]
[2]
[3]
[]
...