Формулировка в прологе

Question

В настоящее время у меня есть следующая проблема, которую я хочу решить с помощью Пролога. Это простой пример, который будет легко решить в 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)?

Answer 1

Ваша проблема может быть сформулирована как последовательность переходов между конфигурациями. Сначала подумайте, как вы хотите представить одну конфигурацию. Для этого вы можете использовать список, например [->, <-, ->, <-, ->, <-], чтобы представить начальную конфигурацию. Один шаг может быть описан с помощью шага / 2 отношения, который используется в качестве шага (State0, State) и описывает отношение между двумя конфигурациями, которые «достижимы» друг от друга путем переключения двух соседних стрелок. В целом это будет недетерминированным. Ваш основной предикат затем описывает последовательность переходов состояний, которые приводят к желаемому целевому состоянию из исходного состояния. Поскольку вы хотите описать список (конфигураций), DCG хорошо подходят: </p>

solution(State0, Target) -->
    (    { State0 == Target } -> []
    ;    { step(State0, State1) },
         [State1],
         solution(State1, Target)
    ). 

А затем используйте итеративное углубление, чтобы найти решение, если оно существует, как в:

?- length(Solution, _), phrase(solution([->,<-,->,<-,->,<-], [<-,<-,<-,->,->,->]), Solution).

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

Answer 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.

Answer 3

Вот мое решение:

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)).

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

Answer 4

удалось преобразовать код мата в ртуть:

:- 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 вывести подписи и детерминизм