Решить людоедов / миссионеров, используя поиск в ширину (BFS) в Прологе?
Я работаю над решением классической проблемы миссионеров (M) и каннибалов (C), начальное состояние - 3 M и 3 C на левом берегу, а состояние цели - 3M, 3C на правом берегу. Я выполнил базовую функцию в моей программе, и мне нужно реализовать поисковую стратегию, такую как BFS и DFS.
В основном мой код учиться из Интернета. Пока я могу успешно запустить программу с помощью метода DFS, но я пытаюсь запустить с BFS, он всегда возвращает false. Это моя самая первая программа SWI-Prolog, я не могу найти, в чем проблема моего кода.
Вот часть моего кода, надеюсь, вы можете помочь мне найти проблему
solve2 :-
bfs([[[3,3,left]]],[0,0,right],[[3,3,left]],Solution),
printSolution(Solution).
bfs([[[A,B,C]]],[A,B,C],_,[]).
bfs([[[A,B,C]|Visisted]|RestPaths],[D,E,F],Visisted,Moves) :-
findall([[I,J,K],[A,B,C]|Visited]),
(
move([A,B,C],[I,J,K],Description),
safe([I,J,K]),
not(member([I,J,K],Visited)
),
NewPaths
),
append(RestPaths,NewPaths,CurrentPaths),
bfs(CurrentPaths,[D,E,F],[[I,J,K]|Visisted],MoreMoves),
Moves = [ [[A,B,C],[I,J,K],Description] | MoreMoves ].
move([A,B,left],[A1,B,right],'One missionary cross river') :-
A > 0, A1 is A - 1.
% Go this state if left M > 0. New left M is M-1
.
.
.
.
.
safe([A,B,_]) :-
(B =< A ; A = 0),
A1 is 3-A, B1 is 3-B,
(B1 =< A1; A1 =0).
Я использую findall, чтобы найти все возможные пути, прежде чем перейти на следующий уровень. Только одно прохождение safe() будет считаться возможным следующим состоянием. Государство не будет использовать, если оно уже существует. Так как моя программа может работать с DFS, я думаю, что нет ничего плохого в предикате move() и safe(). Мой предикат BFS меняется в зависимости от кода DFS, но это не работает.
5 ответов
Существует очень простой способ превратить программу поиска в глубину в программу шириной в первую, при условии, что поиск в глубину напрямую сопоставлен с поиском Пролога. Эта техника называется итеративным углублением.
Просто добавьте дополнительный аргумент, чтобы гарантировать, что поиск будет идти только на N шагов. Итак, dfs-версия:
dfs(State) :-
final(State).
dfs(State1) :-
state_transition(State1, State2),
dfs(State2).
Преобразуется в BFS путем добавления аргумента для глубины. Например, используя преемник-арифметику:
bfs(State, _) :-
final(State).
bfs(State1, s(X)) :-
state_transition(State1, State2),
bfs(State2, X).
Цель bfs(State,s(s(s(0)))) теперь найдет все деривации, требующие 3 или менее шагов. Вы все еще можете выполнять DFS! Просто использовать bfs(State,X),
Чтобы найти все производные, используйте natural_number(X), bfs(State,X),
Часто полезно использовать список вместо номера s(X). Этот список может содержать все промежуточные состояния или конкретные выполненные переходы.
Возможно, вы не решитесь использовать эту технику, потому что она, кажется, пересчитывает много промежуточных состояний ("многократно расширенных состояний"). В конце концов, сначала он ищет все пути за один шаг, затем не более двух шагов, затем не более трех шагов... Однако, если ваша проблема связана с поиском, фактор разветвления здесь скрыт внутри state_transition/2 уменьшит эти накладные расходы. Чтобы увидеть это, рассмотрим фактор ветвления 2: у нас будет только накладные расходы в два раза! Часто есть простые способы восстановить этот фактор два: например, путем ускорения state_transition/2 или же final/1,
Но самое большое преимущество в том, что он не занимает много места - в отличие от наивных dfs.
Дистрибутив Logtalk включает в себя пример "поиск", который реализует структуру для поиска в пространстве состояний:
https://github.com/LogtalkDotOrg/logtalk3/tree/master/examples/searching
Включены "классические" проблемы (фермер, миссионеры и каннибалы, головоломка 8, мост, кувшины с водой и т. Д.). Некоторые алгоритмы поиска адаптированы (с разрешения) из книги Ивана Братко "Программирование пролога для искусственного интеллекта". Пример также включает в себя монитор производительности, который может дать вам некоторые базовые статистические данные о производительности метода поиска (например, коэффициенты ветвления и количество переходов состояний). Фреймворк легко расширяется как для новых задач, так и для новых методов поиска.
Пожалуйста, обратитесь к этой сути, чтобы увидеть возможное решение, возможно, полезное для вашей проблемы.
Если кто-то все еще заинтересован в этом для решения на Python, найдите следующее. Для упрощения учтено только количество миссионеров и каннибалов слева.
Это дерево решений.
#M #missionaries in left
#C #cannibals in left
# B=1left
# B=0right
def is_valid(state):
if(state[0]>3 or state[1]>3 or state[2]>1 or state[0]<0 or state[1]<0 or state[2]<0 or (0<state[0]<state[1]) or (0<(3-state[0])<(3-state[1]))):
return False
else:
return True
def generate_next_states(M,C,B):
moves = [[1, 0, 1], [0, 1, 1], [2, 0, 1], [0, 2, 1], [1, 1, 1]]
valid_states = []
for each in moves:
if(B==1):next_state = [x1 - x2 for (x1, x2) in zip([M, C, B], each)]
else:next_state = [x1 + x2 for (x1, x2) in zip([M, C, B], each)]
if (is_valid(next_state)):
# print(next_state)
valid_states.append(next_state)
return valid_states
solutions = []
def find_sol(M,C,B,visited):
if([M,C,B]==[0,0,0]):#everyne crossed successfully
# print("Solution reached, steps: ",visited+[[0,0,0]])
solutions.append(visited+[[0,0,0]])
return True
elif([M,C,B] in visited):#prevent looping
return False
else:
visited.append([M,C,B])
if(B==1):#boat is in left
for each_s in generate_next_states(M,C,B):
find_sol(each_s[0],each_s[1],each_s[2],visited[:])
else:#boat in in right
for each_s in generate_next_states(M,C,B):
find_sol(each_s[0],each_s[1],each_s[2],visited[:])
find_sol(3,3,1,[])
solutions.sort()
for each_sol in solutions:
print(each_sol)
Я решил сначала с глубиной, а затем с широтой, пытаясь четко отделить повторно используемую часть от алгоритма поиска состояния:
miss_cann_dfs :-
initial(I),
solve_dfs(I, [I], Path),
maplist(writeln, Path), nl.
solve_dfs(S, RPath, Path) :-
final(S),
reverse(RPath, Path).
solve_dfs(S, SoFar, Path) :-
move(S, T),
\+ memberchk(T, SoFar),
solve_dfs(T, [T|SoFar], Path).
miss_cann_bfs :-
initial(I),
solve_bfs([[I]], Path),
maplist(writeln, Path), nl.
solve_bfs(Paths, Path) :-
extend(Paths, Extended),
( member(RPath, Extended),
RPath = [H|_],
final(H),
reverse(RPath, Path)
; solve_bfs(Extended, Path)
).
extend(Paths, Extended) :-
findall([Q,H|R],
( member([H|R], Paths),
move(H, Q),
\+ member(Q, R)
), Extended),
Extended \= [].
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% problem representation
% independent from search method
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
initial((3,3, >, 0,0)).
final((0,0, <, 3,3)).
% apply a *valid* move
move((M1i,C1i, Bi, M2i,C2i), (M1f,C1f, Bf, M2f,C2f)) :-
direction(Bi, F1, F2, Bf),
who_move(MM, CM),
M1f is M1i + MM * F1, M1f >= 0,
C1f is C1i + CM * F1, C1f >= 0,
( M1f >= C1f ; M1f == 0 ),
M2f is M2i + MM * F2, M2f >= 0,
C2f is C2i + CM * F2, C2f >= 0,
( M2f >= C2f ; M2f == 0 ).
direction(>, -1, +1, <).
direction(<, +1, -1, >).
% valid placements on boat
who_move(M, C) :-
M = 2, C = 0 ;
M = 1, C = 0 ;
M = 1, C = 1 ;
M = 0, C = 2 ;
M = 0, C = 1 .
Я предлагаю вам структурировать ваш код аналогичным образом, используя предикат, аналогичный extension /2, который дает понять, когда следует прекратить поиск.
Если в вашей системе Prolog есть прямой цепочник, вы также можете решить эту проблему, смоделировав ее с помощью правил прямой цепочки. Вот пример того, как решить проблему кувшина с водой в Jekejeke Minlog. Состояние представлено предикатом состояния /2.
Сначала вы даете правило, которое фильтрует дубликаты, следующим образом. Правило гласит, что факт входящего состояния / 2 должен быть удален, если он уже находится в хранилище форвардов:
% avoid duplicate state
unit &:- &- state(X,Y) && state(X,Y), !.
Затем вы даете правила, которые утверждают, что поиск не должен продолжаться при достижении конечного состояния. В настоящем примере мы проверяем, что один из сосудов содержит 1 литр воды:
% halt for final states
unit &:- state(_,1), !.
unit &:- state(1,_), !.
В качестве следующего шага моделируются переходы состояний в качестве правил прямой цепочки. Это прямо вперед. Мы моделируем опорожнение, наполнение и розлив сосудов:
% emptying a vessel
state(0,X) &:- state(_,X).
state(X,0) &:- state(X,_).
% filling a vessel
state(5,X) &:- state(_,X).
state(X,7) &:- state(X,_).
% pouring water from one vessel to the other vessel
state(Z,T) &:- state(X,Y), Z is min(5,X+Y), T is max(0,X+Y-5).
state(T,Z) &:- state(X,Y), Z is min(7,X+Y), T is max(0,X+Y-7).
Теперь мы можем использовать движок прямой цепочки, чтобы сделать эту работу за нас. Он не будет выполнять итеративное углубление, а также не будет в первую очередь шире. Он просто выполнит преобразование единиц измерения с помощью стратегии, которая жадна до данного факта, и процесс только завершится, поскольку пространство состояний конечно. Вот результат:
?- post(state(0,0)), posted.
state(0, 0).
state(5, 0).
state(5, 7).
state(0, 7).
Etc..
Подход скажет вам, есть ли решение, но не объяснит решение. Один из способов сделать его объяснимым - это использовать состояние факта /4 вместо состояния факта /2. Последние два аргумента используются для списка действий и для длины списка.
Правило, которое избегает дубликатов, затем изменяется на правило, которое выбирает наименьшее решение. Это гласит следующее:
% choose shorter path
unit &:- &- state(X,Y,_,N) && state(X,Y,_,M), M<N, !.
unit &:- state(X,Y,_,N) && &- state(X,Y,_,M), N<M.
Затем мы получаем:
?- post(state(0,0,[],0)), posted.
state(0, 0, [], 0).
state(5, 0, [fl], 1).
state(5, 7, [fr,fl], 2).
state(0, 5, [plr,fl], 2).
Etc..
С помощью небольшого вспомогательного предиката мы можем вызвать объяснение действий, которые ведут к пути:
?- post(state(0,0,[],0)), state(1,7,L,_), explain(L).
0-0
fill left vessel
5-0
pour left vessel into right vessel
0-5
fill left vessel
5-5
pour left vessel into right vessel
3-7
empty right vessel
3-0
pour left vessel into right vessel
0-3
fill left vessel
5-3
pour left vessel into right vessel
1-7
до свидания
Исходный код: Water Jug State
http://www.xlog.ch/jekejeke/forward/jugs3.p
Исходный код: состояние кувшина и путь
http://www.xlog.ch/jekejeke/forward/jugs3path.p