Предотвращение возврата после первого решения пары Фибоначчи

Семестр fib(N,F) верно, когда F это Nчисло Фибоначчи.

Следующий код Пролога обычно работает для меня:

:-use_module(library(clpfd)).
fib(0,0).
fib(1,1).
fib(N,F) :- 
  N #> 1, 
  N #=< F + 1, 
  F #>= N - 1,
  F #> 0, 
  N1 #= N - 1, 
  N2 #= N - 2, 
  F1 #=< F, 
  F2 #=< F,
  F #= F1 + F2, 
  fib(N1,F1),
  fib(N2,F2).

При выполнении этого запроса (в SICStus Prolog) первое (и правильное) совпадение найдено для N (довольно мгновенно):

| ?- fib(X,377).
X = 14 ?

При продолжении (путем ввода ";"), чтобы увидеть, есть ли какие-либо дальнейшие совпадения (что невозможно по определению), требуется огромное количество времени (по сравнению с первым совпадением), чтобы просто ответить без:

| ?- fib(X,377).
X = 14 ? ;
no

Будучи довольно новым для Пролога, я попытался использовать Cut-Operator (!) различными способами, но я не могу найти способ предотвратить поиск после первого совпадения. Возможно ли это даже с учетом приведенных выше правил? Если да, пожалуйста, дайте мне знать, как:)

Источник

3 ответа

Решение

Есть две части, чтобы получить то, что вы хотите.

Первый заключается в использованииcall_semidet/1что гарантирует, что есть только один ответ. Смотрите ссылки для реализации SICStus тоже. В маловероятном случае наличия более одного ответа,call_semidet/1выдаёт безопасную ошибку Обратите внимание, чтоonce/1а также !/0 в одиночку просто отрезают все, что там было.

Тем не менее, вы не будете очень довольныcall_semidet/1в одиночестве. По сути, он выполняет цель дважды. Один раз посмотреть, есть ли не более одного ответа, и только потом снова получить первый ответ. Таким образом, вы получите ответ намного позже.

Другая часть заключается в том, чтобы ускорить ваше определение так, чтобы вышеприведенное не слишком беспокоило вас. Решение, предложенное CapelliC, полностью меняет алгоритм, который специфичен для вашей конкретной функции, но не распространяется на другие функции. Но это также описывает другое отношение.

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

CLPFD как CLP(Z)

То, что вы делаете здесь, до сих пор не так часто встречается у многих программистов Prolog. Вы используете ограничения конечной области для общей целочисленной арифметики. Таким образом, вы используете CLPFD в качестве чистой замены для оценки измененного выражения, найденной в(is)/2,(>)/2и тому подобное. Таким образом, вы хотите расширить парадигму конечной области, которая предполагает, что мы выражаем все в конечных заданных интервалах. Фактически, было бы более уместно назвать это расширение CLP(Z).

Это расширение работает не во всех прологах, предлагающих конечные домены. Фактически, есть только SICStus, SWI и YAP, которые правильно обрабатывают случай бесконечных интервалов. Другие системы могут выйти из строя или преуспеть, когда они скорее должны преуспеть или потерпеть неудачу - главным образом, когда целые числа становятся слишком большими

Понимание не прекращения

Первая проблема заключается в том, чтобы понять фактическую причину, по которой ваша первоначальная программа не прервалась. Для этого я буду использовать срез сбоя. То есть я добавляю falseцели в вашу программу. Дело в том, что если результирующая программа не завершается, то и исходная программа не завершается. Таким образом, минимальная ошибка вашей (предполагаемой) исходной программы:

фибориг (0,0):-ложно.фибориг (1,1):- неверно.
фибориг (N,F):-
   N #> 1,
   N1 #= N-1,
   N2 #= N-2,
   F #= F1+F2,
   фибориг (N1,F1),ложь,фибориг (N2, F2).

Есть два источника для прекращения здесь: один для данного FЕсть бесконечно много значений дляF1а такжеF2, Это можно легко сделать, наблюдая, чтоF1 #> 0, F2 #>= 0,

Другой больше связан с механизмом исполнения Пролога. Для иллюстрации добавлю F2 #= 0, Опять же, поскольку результирующая программа не завершается, исходная программа также будет зациклена.

фибориг (0,0):- ложно.фибориг (1,1):- неверно.
фибориг (N,F):-
   N #> 1,
   N1 #= N-1,
   N2 #= N-2,
   F #= F1+F2,
   F1 #> 0,
   F2 #> = 0,F2 # = 0, фибориг (N1,F1),ложь,
   фибориг (N2, F2).

Таким образом, актуальная проблема заключается в том, что цель, которая может иметь 0как результат выполняется слишком поздно. Просто поменяйте две рекурсивные цели. И добавьте избыточное ограничениеF2 #=< F1для эффективности.

fibmin (0,0).
fibmin (1,1).
фибмин (N, F): -
   N #> 1,
   N1 # = N-1,
   N2 # = N-2,
   F1 #> 0,
   F2 #> = 0,
   F1 #> = F2,
   F# = F1 + F2,
   fibmin (Н2,F2),
   fibmin(N1,F1).

На моем хромом ноутбуке я получил следующие fib(N, 377):

SICStus SWI
             Ответ / всего
фибориг:     0,090 с /27,220 с 1,332 с /1071,380 с
фибмин:     0,080 с / 0,110 с 1.201 с / 1,506 с

Возьмите сумму обоих, чтобы получить время выполнения для call_semidet/1,

Обратите внимание, что реализация SWI написана только на Прологе, тогда как SICStus частично на C, частично на Прологе. Поэтому при переносе clpfd SWI (на самом деле @mat) в SICStus скорость может быть сопоставимой.

Есть еще много вещей для оптимизации. Подумайте об индексации и обработке "счетчиков", N, N1, N2,

Также ваша оригинальная программа может быть немного улучшена. Например, вы публикуете ограничение без необходимости F #>= N-1 три раза!

Источник

Если вы заинтересованы только в первом решении или знаете, что существует не более одного решения, вы можете использовать once/1 принять это решение:

?- once(fib(X, 377)).

+1 за использование CLP(FD) в качестве декларативной альтернативы арифметике более низкого уровня. Ваша версия может использоваться во всех направлениях, тогда как версия, основанная на примитивной целочисленной арифметике, не может.

Источник

Я немного поиграл с другим определением, я написал в стандартной арифметике и специально для этого вопроса перевел на CLP(FD).

Мое простое определение Пролога было

fibo(1, 1,0).
fibo(2, 2,1).
fibo(N, F,A) :- N > 2, M is N -1, fibo(M, A,B), F is A+B.

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

fibo(1, 1,0).
fibo(2, 2,1).
fibo(N, F,A) :-
  N #> 2,
  M #= N -1,
  M #>= 0,  % added
  A #>= 0,  % added
  B #< A,   % added - this is key
  F #= A+B,
  fibo(M, A,B). % moved - this is key

После добавления B #< A и перемещая рекурсию при последнем вызове, теперь это работает.

?- time(fibo(U,377,Y)).
% 77,005 inferences, 0.032 CPU in 0.033 seconds (99% CPU, 2371149 Lips)
U = 13,
Y = 233 ;
% 37,389 inferences, 0.023 CPU in 0.023 seconds (100% CPU, 1651757 Lips)
false.

изменить Чтобы учесть 0 последовательностей на основе, добавьте факт

fibo(0,0,_).

Может быть, это объясняет роль последнего аргумента: это аккумулятор.

Источник
Другие вопросы по тегам