Генерация возможных комбинаций в прологе - PullRequest
Новая
       18

Генерация возможных комбинаций в прологе

0 голосов
/ 05 января 2019

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

  1. По обе стороны острова и в лодке каннибалы не могут превосходить численность миссионеров.

  2. В лодке должен быть хотя бы один человек.

Я пытался добиться этого с помощью следующего кода: 

    % M = number of missionaries
    % C = number of cannibals

    % AM = number of missionaries on left island
    % BM = number of missionaries on right island

    % AC = number of cannibals on left island
    % BC = number of cannibals on right island

    % B = 1 if boat is on left island, -1 if boat is on right island
    % L = list of previous states / moves
    % K = maximum capacity of boat

Введите выше для всех следующих переменных: 

    checkIsland(M,C) :- C =< M.

    checkState(AM, AC, BM, BC) :-
        checkIsland(AM, AC),
        checkIsland(BM, BC).

    checkMove(AM,AC,BM,BC,B,L):-
        checkState(AM,AC,BM,BC),
        not(member([AM,AC,BM,BC,B],L)).

    checkBoat(M,C,K) :-
        C =< M,
        (M + C) =< K,
        (M + C) >= 1.

    state(_,0,0,_,_,-1,_).
    state(K,AM,AC,BM,BC,B,L) :-
        % checkMove(NewAM, NewAC, NewBM, NewBM, NewB, L),
        abs((NewAM - NewBM), FinalM),
        abs((NewAC - NewBC), FinalC),           
        checkBoat(FinalM, FinalC),
        append([AM,AC,BM,BC,B], L, NewL),
        state(K,NewAM, NewAC,NewBM,NewBC,NewB,NewL).

Я думаю, что я достаточно близок, поскольку основная (единственная?) Проблема связана с функцией state, так как я не понимаю, как вы должны генерировать возможные ходы / фактически делать ход. Может кто-нибудь, пожалуйста, сообщите.

Я пытаюсь решить эту проблему, в частности, используя функции, описанные выше, так как это вопрос экзаменационной работы.

Edit:

Чтобы прояснить назначение предиката state/7, он используется для поиска и вывода списка всех состояний, возникающих в процессе решения. Например.

Если вы позвоните по номеру state(2,2,1,0,0,1,[]) (в котором говорится, что на левом острове есть лодка вместимостью два, а на левом острове два миссионера и один каннибал, а на правом острове ноль миссионеров и ноль каннибалов), тогда распечатка результата L может дать: 

2, 1, 0, 0, 1    % The initially input state
1, 0, 1, 1, -1   % 1 missionary, 1 cannibal and the boat move to the right island
1, 1, 1, 0, 1    % 1 cannibal and the boat move to the left island
0, 0, 2, 1, -1   % 1 missionary, 1 cannibal and the boat move to the right island,
                   and the goal is met
...