fork download
copy 
  1. prolog
  2. Копировать
  3. % Представление состояния: state(Миссионеры_слева, Каннибалы_слева, Лодка, Миссионеры_справа, Каннибалы_справа)
  4.  
  5. % Начальное и конечное состояния
  6. начальное_состояние(state(3, 3, left, 0, 0)).
  7. целевое_состояние(state(0, 0, right, 3, 3)).
  8.  
  9. % Операторы (переправы)
  10. оператор(m1). % 1 миссионер
  11. оператор(c1). % 1 каннибал
  12. оператор(m2). % 2 миссионера
  13. оператор(c2). % 2 каннибала
  14. оператор(mc). % 1 миссионер, 1 каннибал
  15.  
  16. % Правила переходов (определяют, как оператор меняет состояние)
  17. переход(state(M1, C1, left, M2, C2), m1, state(M1_next, C1, right, M2_next, C2)) :-
  18.   M1 > 0,  % Проверяем, есть ли миссионеры для переправы
  19.   M1_next is M1 - 1,
  20.   M2_next is M2 + 1,
  21.   безопасное_состояние(state(M1_next, C1, right, M2_next, C2)).
  22.  
  23. переход(state(M1, C1, left, M2, C2), c1, state(M1, C1_next, right, M2, C2_next)) :-
  24.   C1 > 0,  % Проверяем, есть ли каннибалы для переправы
  25.   C1_next is C1 - 1,
  26.   C2_next is C2 + 1,
  27.   безопасное_состояние(state(M1, C1_next, right, M2, C2_next)).
  28. % ... (добавьте правила для остальных операторов)
  29.  
  30. переход(state(M1, C1, right, M2, C2), m1, state(M1_next, C1, left, M2_next, C2)) :-
  31.   M2 > 0,
  32.     M1_next is M1 + 1,
  33.     M2_next is M2 - 1,
  34.   безопасное_состояние(state(M1_next, C1, left, M2_next, C2)).
  35.  
  36. % Предикат безопасного состояния
  37. безопасное_состояние(state(M, C, _, M_goal, C_goal)) :-
  38.   безопасно(M, C),
  39.   безопасно(M_goal, C_goal).
  40.  
  41. безопасно(M, C) :-
  42.     (M >= C ; M = 0),
  43.     M >= 0,
  44.     C >= 0.
  45.  
  46. % Поиск в глубину
  47. решить(Начальное_состояние, Целевое_состояние, Путь) :-
  48.     решить_dfs(Начальное_состояние, Целевое_состояние, [Начальное_состояние], [], Путь).
  49.  
  50. решить_dfs(Текущее_состояние, Целевое_состояние, Посещенные,  ПутьДоТекущегоСостояния, [Текущее_состояние | ПутьДоТекущегоСостояния]) :-
  51.     Текущее_состояние = Целевое_состояние,
  52.     !.
  53.  
  54. решить_dfs(Текущее_состояние, Целевое_состояние, Посещенные, ПутьДоТекущегоСостояния, Путь) :-
  55.     % Вот тут вызываем визуализацию текущего состояния
  56.     вывести_состояние(Текущее_состояние), % <----  ДОБАВЛЕНО
  57.  
  58.     findall(Следующее_состояние, (переход(Текущее_состояние, _, Следующее_состояние), \+ member(Следующее_состояние, Посещенные)), Возможные_состояния),
  59.     member(Новое_состояние, Возможные_состояния),
  60.     решить_dfs(Новое_состояние, Целевое_состояние, [Новое_состояние | Посещенные], [Текущее_состояние | ПутьДоТекущегоСостояния], Путь).
  61.  
  62. % Визуализация состояния (ПРИМЕР 1 - базовый)
  63. вывести_состояние(state(M1, C1, Лодка, M2, C2)) :-
  64.     write('Состояние:'), nl,
  65.     write('  Левый берег: Миссионеры = '), write(M1), write(', Каннибалы = '), write(C1), nl,
  66.     write('  Лодка: '), write(Лодка), nl,
  67.     write('  Правый берег: Миссионеры = '), write(M2), write(', Каннибалы = '), write(C2), nl, nl.
  68.  
  69. % Визуализация состояния (ПРИМЕР 2 - с рекой)
  70.  
  71. % Раскомментируйте этот блок, чтобы использовать визуализацию с рекой
  72. вывести_состояние(state(M1, C1, left, M2, C2)) :-
  73.     gen_string(M1, 'M', Миссионеры_лево),  % Вспомогательный предикат
  74.     gen_string(C1, 'C', Каннибалы_лево),  % Вспомогательный предикат
  75.     gen_string(M2, 'M', Миссионеры_право),
  76.     gen_string(C2, 'C', Каннибалы_право),
  77.     atomic_list_concat([Миссионеры_лево, Каннибалы_лево, ' |~~~~~| ', Миссионеры_право, Каннибалы_право], Строка),
  78.     write(Строка), nl,
  79.     write('Лодка: <---'), nl, nl.
  80.  
  81. вывести_состояние(state(M1, C1, right, M2, C2)) :-
  82. % Аналогично, но лодка плывет вправо
  83.     gen_string(M1, 'M', Миссионеры_лево),  % Вспомогательный предикат
  84.     gen_string(C1, 'C', Каннибалы_лево),  % Вспомогательный предикат
  85.     gen_string(M2, 'M', Миссионеры_право),
  86.     gen_string(C2, 'C', Каннибалы_право),
  87.     atomic_list_concat([Миссионеры_лево, Каннибалы_лево, ' |~~~~~| ', Миссионеры_право, Каннибалы_право], Строка),
  88.     write(Строка), nl,
  89.     write('Лодка: --->'), nl, nl.
  90.  
  91. gen_string(0, _, '') :- !.
  92. gen_string(N, Char, String) :-
  93.   N > 0,
  94.   N1 is N - 1,
  95.   gen_string(N1, Char, Rest),
  96.   atomic_list_concat([Char, Rest], String).
  97.  
  98.  
  99.  
  100. % Точка входа для запуска решения
  101. go :-
  102.     начальное_состояние(Начальное),
  103.     целевое_состояние(Целевое),
  104.     решить(Начальное, Целевое, Путь),
  105.     reverse(Путь, Обратный_путь),
  106.     write('Решение:'), nl,
  107.     вывести_путь(Обратный_путь).
  108.  
  109. вывести_путь([]).
  110. вывести_путь([H|T]) :-
  111.     write(H), nl,
  112.     вывести_путь(T).
Success #stdin #stdout #stderr 0.02s 7040KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
ERROR: /home/m8h8Ik/prog:1:7: Syntax error: Operator expected
Warning: /home/m8h8Ik/prog:50:
	Singleton variables: [Посещенные]
ERROR: '$runtoplevel'/0: Undefined procedure: program/0
   Exception: (3) program ? EOF: exit
https://ideone.com/EAUNgs
language:
Prolog (swi 7.6.4)
created:
18 hours ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!