Формулировка в прологе
В настоящее время у меня есть следующая проблема, которую я хочу решить с помощью Пролога. Это простой пример, который будет легко решить в Java/C/ что угодно. Моя проблема в том, что я считаю, что слишком привязан к мышлению Java, чтобы фактически сформулировать проблему таким образом, чтобы использовать логическую силу Пролога.
Проблема в..
У меня есть набор из 6 стрелок, указывающих влево или вправо. Давайте предположим, что они находятся в следующей стартовой конфигурации:
->
<-
->
<-
->
<-
Теперь я могу переключать две стрелки, пока они находятся рядом друг с другом. Моя цель - выяснить, какая последовательность действий превратит первоначальную конфигурацию стрелок в
<-
<-
<-
->
->
->
Моя первая попытка сформулировать проблему
right(arrow_a).
left(arrow_b).
right(arrow_c).
left(arrow_d).
right(arrow_e).
left(arrow_f).
atPosition(1, arrow_a).
atPosition(2, arrow_b).
atPosition(3, arrow_c).
atPosition(4, arrow_d).
atPosition(5, arrow_e).
atPosition(6, arrow_f).
Это скажет Прологу, какова начальная конфигурация стрелок. Но как мне вставить в него дополнительную логику? Как реализовать, например, switchArrows(Index)? Правильно ли даже указывать начальные условия в Прологе? Не помешает ли это позже, когда я попытаюсь установить, например, что arrow_a находится в положении 6, atPosition(6, arrow_a)?
4 ответа
Ваша проблема может быть сформулирована как последовательность переходов между конфигурациями. Сначала подумайте, как вы хотите представить одну конфигурацию. Для этого вы можете использовать список, например [->,<-, ->,<-, ->,<-], чтобы представить начальную конфигурацию. Один шаг может быть описан с помощью шага /2 отношения, который используется в качестве шага (State0, State) и описывает отношение между двумя конфигурациями, которые "достижимы" друг от друга путем переключения двух смежных стрелок. В целом это будет недетерминированным. Ваш основной предикат затем описывает последовательность переходов состояний, которые приводят к желаемому целевому состоянию из исходного состояния. Поскольку вы хотите описать список (конфигураций), DCG хорошо подходят:
solution(State0, Target) -->
( { State0 == Target } -> []
; { step(State0, State1) },
[State1],
solution(State1, Target)
).
А затем используйте итеративное углубление, чтобы найти решение, если оно существует, как в:
?- length(Solution, _), phrase(solution([->,<-,->,<-,->,<-], [<-,<-,<-,->,->,->]), Solution).
Приятно то, что Prolog автоматически возвращает обратно после того, как все последовательности заданной длины были опробованы и целевое состояние еще не было достигнуто. Вы только должны выполнить шаг /2 сейчас и все готово.
Поскольку полное решение уже опубликовано, вот мое:
solution(State0, Target) -->
( { State0 == Target } -> []
; { step(State0, State1) },
[State1],
solution(State1, Target)
).
flip(->, <-).
flip(<-, ->).
step([], []).
step([A|Rest0], [A|Rest]) :- step(Rest0, Rest).
step([A0,A1|Rest], [B0,B1|Rest]) :- flip(A0, B0), flip(A1, B1).
Пример запроса:
?- length(Solution, _), phrase(solution([->,<-,->,<-,->,<-], [<-,<-,<-,->,->,->]), Solution).
Solution = [[->, <-, ->, <-, <-, ->],
[->, <-, ->, ->, ->, ->],
[->, ->, <-, ->, ->, ->],
[<-, <-, <-, ->, ->, ->]].
Поскольку используется итеративное углубление, мы знаем, что более короткое решение (менее 4 шагов) невозможно.
У меня также есть общий комментарий к тому, что вы сказали:
Это простой пример, который будет легко решить в Java/C/ что угодно. Моя проблема в том, что я считаю, что слишком привязан к мышлению Java, чтобы фактически сформулировать проблему таким образом, чтобы использовать логическую силу Пролога.
Лично я думаю, что этот пример уже намного больше, чем можно было ожидать от начинающего, скажем, Java-программиста. Пожалуйста, попробуйте решить эту проблему в Java/C/ что угодно и посмотрите, как далеко вы продвинулись. По моему опыту, когда студенты говорят, что они "слишком привязаны к мышлению Java" и т. Д., Они также не могут решить проблему в Java. Пролог отличается, но не настолько отличается, что, если у вас есть четкое представление о том, как решить его в Java, вы не сможете перевести его напрямую в Пролог. Мое решение использует встроенный механизм поиска Prolog, но вам не нужно: вы можете осуществлять поиск самостоятельно, как в Java.
Вот мое решение:
solution(Begin, End, PrevSteps, [Step | Steps]) :-
Step = step(Begin, State1),
Step,
forall(member(step(S, _), PrevSteps),
State1 \= S
), % prevent loops
( State1 == End
-> Steps = []
; solution(State1, End, [Step | PrevSteps], Steps)
).
rev(->,<-).
rev(<-,->).
step([X,Y|T], [XX,YY|T]) :- rev(X,XX), rev(Y, YY).
step([A,X,Y|T], [A,XX,YY|T]) :- rev(X,XX), rev(Y, YY).
step([A,B,X,Y|T], [A,B,XX,YY|T]) :- rev(X,XX), rev(Y, YY).
step([A,B,C,X,Y|T], [A,B,C,XX,YY|T]) :- rev(X,XX), rev(Y, YY).
step([A,B,C,D,X,Y], [A,B,C,D,XX,YY]) :- rev(X,XX), rev(Y, YY).
run :-
solution([->,<-,->,<-,->,<-], [<-,<-,<-,->,->,->],[],Steps),
!,
forall(member(Step,Steps),writeln(Step)).
Он находит только первое решение из всех возможных, хотя я полагаю, что найденное решение не является оптимальным, а скорее первое рабочее.
Удалось преобразовать код мата в ртуть:
:- module arrows.
:- interface.
:- import_module io.
:- pred main(io, io).
:- mode main(di, uo) is cc_multi.
:- implementation.
:- import_module list, io, int.
:- type arrow ---> (->); (<-).
:- mode solution(in, in, in, in, out, in) is cc_nondet.
solution(State0, Target, MaxDepth, CurrentDepth) -->
{CurrentDepth =< MaxDepth},
( { State0 = Target } -> []
; { step(State0, State1) },
[State1],
solution(State1, Target, MaxDepth, CurrentDepth + 1)
).
flip(->, <-).
flip(<-, ->).
step([], []).
step([A|Rest0], [A|Rest]) :- step(Rest0, Rest).
step([A0,A1|Rest], [B0,B1|Rest]) :- flip(A0, B0), flip(A1, B1).
main -->
(({
member(N, 1..10),
solution([->,<-,->,<-,->,<-], [<-,<-,<-,->,->,->], N, 0, Solution, [])
})
-> print(Solution)
; print("No solutions")
).
Компилирование с помощью mmc --infer-all arrows.m для определения сигнатур и детерминизма