Решить динамическое программирование в Прологе с помощью corecursion - PullRequest
Новая
       28

Решить динамическое программирование в Прологе с помощью corecursion

0 голосов
/ 01 сентября 2018

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

Есть здание n этажей с лифтом, которое может только подняться на 2 этажа одновременно и спуститься на 3 этажа одновременно. С помощью динамическое программирование написать функцию, которая будет вычислять количество шагов, необходимое лифту, чтобы добраться от пола я в пол к.

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

Пример потока из них: 

 one(1, one).

Предикат взятия Haskell может быть затем просто закодирован следующим образом: 

 take(0, _, L) :- !, L = [].
 take(N, C, [X|L]) :- N > 0, 
    call(C, X, D), 
    M is N-1, 
    take(M, D, L).

Вот пример запуска: 

 ?- take(5, one, X).
 X = [1, 1, 1, 1, 1].

 ?- take(10, one, X).
 X = [1, 1, 1, 1, 1, 1, 1, 1, 1|...].

1 Ответ

0 голосов
/ 01 сентября 2018

В этом ко-рекурсивном решении Пролог нам нужны два строительных блока.

Один строительный блок - это способ перечисления дерева поиска ко-рекурсивно в Прологе. Мы принимаем идею о том, что термин закрытия Пролога должен содержать повестку дня с путями и, следовательно, узлами, которые должны быть расширены. Затем мы можем начать с повестки дня, которая содержит только корень: 

% tree(-Path, -LazyPaths)
tree(H, T) :-
   tree([[]], H, T).

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

% tree(+Paths, -Path, -LazyPaths)
tree([X|Y], X, tree(Z)) :-
   append(Y, [[0|X],[1|X]], Z).

Вот пример запуска: 

?- take(5, tree, L).
L = [[],[0],[1],[0,0],[1,0]]

?- take(10, tree, L).
L = [[],[0],[1],[0,0],[1,0],[0,1],[1,1],[0,0,0],[1,0,0],[0,1,0]]

В случае проблемы с оценщиком у нас будет путь и, следовательно, расширение узла, которое не всегда приведет к двум преемникам. Если мы находимся на уровне k, лифт может перейти на уровень k + 2 или k-3, только при условии, что лифт остается внутри здания. Таким образом, мы с готовностью приходим к ко-рекурсивным шагам предиката, которые имитируют все возможные пути лифта: 

?- take(5, steps(7,[[2]]), L).
L = [[2],[4,2],[1,4,2],[6,4,2],[3,1,4,2]]

?- take(10, steps(7,[[2]]), L).
L = [[2],[4,2],[1,4,2],[6,4,2],[3,1,4,2],[3,6,4,2],
    [5,3,1,4,2],[5,3,6,4,2],[2,5,3,1,4,2],[7,5,3,1,4,2]]

Последнее препятствие и второй строительный блок - получить Haskell dropWhile в Прологе. Мы не стремились к предикату, который принимает аргумент термина закрытия Пролога для логического условия, но вместо этого предоставили только предикат, который перечисляет ленивые элементы списка, и пользователь предиката может фильтровать в продолжении Пролога. 

% drop_while(+LazyList, -Element)
drop_while(C, P) :-
   call(C, Q, T),
   (P = Q; drop_while(T, P)).

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

?- elevator(7,2,6,L), length(L,N).
L = [6,4,2],
N = 3 ;
L = [6,4,2,5,3,1,4,2],
N = 8 ;
L = [6,4,7,5,3,1,4,2],
N = 8
...