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

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

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

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

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

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

CLPFD как CLP(Z)

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

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

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

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

fiborig(0,0) :- false.
fiborig(1,1) :- false.
fiborig(N,F) :-
   N #> 1,
   N1 #= N-1,
   N2 #= N-2,
   F #= F1+F2,
   fiborig(N1,F1), false,
   fiborig(N2,F2).

Здесь есть два источника незавершения: во-первых, для заданного F существует бесконечно много значений для F1 и F2. С этим можно легко справиться, заметив, что F1 #> 0, F2 #>= 0.

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

fiborig(0,0) :- false.
fiborig(1,1) :- false.
fiborig(N,F) :-
   N #> 1,
   N1 #= N-1,
   N2 #= N-2,
   F #= F1+F2,
   F1 #> 0,
   F2 #>= 0,
   F2 #= 0,
   fiborig(N1,F1), false,
   fiborig(N2,F2).

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

fibmin(0,0).
fibmin(1,1).
fibmin(N,F) :-
   N #> 1,
   N1 #= N-1,
   N2 #= N-2,
   F1 #> 0,
   F2 #>= 0,
   F1 #>= F2,
   F #= F1+F2,
   fibmin(N2,F2),
   fibmin(N1,F1).

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

               SICStus                  SWI
             answer/total
fiborig:     0.090s/27.220s           1.332s/1071.380s
fibmin:      0.080s/ 0.110s           1.201s/   1.506s

Возьмите сумму обоих, чтобы получить время выполнения для 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,_).

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