aabzel28 сен в 19:40

Решение задачи про козу, капусту и волка через конечный автомат

Простой

6 мин

11K

Математика * Логические игрыЗанимательные задачки

Туториал

+17

Комментарии 23

Закреплённые комментарии

axion-1 29 сен в 09:35

Перебор всех состояний с проверкой на валидность показывает, что у нас всего только 16 реальных состояний

Проще закодировать состояние четырьмя битами, по одному для волка, козы, капусты и человека. Волк на левом берегу - 0, на правом - 1 и т.д. Не понадобится ничего перебирать и загромождать схему.

randomsimplenumber 28 сен в 19:58

С помощью нехитрых инструментов… (ц) :)

kovserg 28 сен в 20:07

Вообще-то есть вот такой хитрый инструмент: https://www.minizinc.org/

aabzel 29 сен в 11:01

Как им пользоваться и зачем это?

kovserg 29 сен в 21:00

Это программа позволяет решать оптимизационные задачи с ограничениями. Примерно так:

Сначала описываете модель
Затем ограничения
Просите найти решение

wgc.mzn

% Задача: Волк, Коза и Капуста

int: N = 8;
set of int: Steps = 1..N;
enum Side = { L,R };
array[Steps] of var Side: peasant;
array[Steps] of var Side: wolf;
array[Steps] of var Side: goat;
array[Steps] of var Side: green;

% Начальное состояние
constraint peasant[1]=L /\ wolf[1]=L /\ goat[1]=L /\ green[1]=L;

% Конечное состояние
constraint peasant[N]=R /\ wolf[N]=R /\ goat[N]=R /\ green[N]=R;

% Правила безопасности на каждом шаге
constraint forall(s in Steps) (
  (wolf[s]==goat[s] -> peasant[s]==wolf[s])
  /\
  (goat[s]==green[s] -> peasant[s]==goat[s])
);

% Правила переправы
constraint forall(s in 1..N-1) (
  peasant[s+1]!=peasant[s]
  /\
  (
    (wolf[s+1]!=wolf[s] /\ peasant[s]==wolf[s] /\ goat[s+1]==goat[s] /\ green[s+1]==green[s])  % Крестьянин везет волка
    \/
    (goat[s+1]!=goat[s] /\ peasant[s]==goat[s] /\ wolf[s+1]==wolf[s] /\ green[s+1]==green[s])  % Крестьянин везет козу
    \/
    (green[s+1]!=green[s] /\ peasant[s]==green[s] /\ wolf[s+1]==wolf[s] /\ goat[s+1]==goat[s]) % Крестьянин везет капусту
    \/
    (wolf[s+1]==wolf[s] /\ goat[s+1]==goat[s] /\ green[s+1]==green[s])                         % Крестьянин плывет один
  )
);

solve satisfy;

output [
    "\(s): Крестьянин=\(peasant[s]), Волк=\(wolf[s]), Коза=\(goat[s]), Капуста=\(green[s])\n" | s in Steps
];

И выводите результат

Running wgc.mzn

1: Крестьянин=L, Волк=L, Коза=L, Капуста=L
2: Крестьянин=R, Волк=L, Коза=R, Капуста=L
3: Крестьянин=L, Волк=L, Коза=R, Капуста=L
4: Крестьянин=R, Волк=R, Коза=R, Капуста=L
5: Крестьянин=L, Волк=R, Коза=L, Капуста=L
6: Крестьянин=R, Волк=R, Коза=L, Капуста=R
7: Крестьянин=L, Волк=R, Коза=L, Капуста=R
8: Крестьянин=R, Волк=R, Коза=R, Капуста=R

PROFIT

Более подробно там есть примеры, документация, обучение, песочница и обучающие курсы.

Siemargl 29 сен в 09:07

Мне кажется, автор в теорию КА ни бум бум. Превратить детскую логическую задачу в факториальную сложность, это 5!

Интересно, есть ли адекватная перекладка этой задачи на КА?

Навскидку, я бы выделил 3 объекта - лодка и два берега, состояния - их пассажиры, переход между состояниями - посадки/высадки.

aabzel 29 сен в 09:56

Мне кажется, автор в теорию КА ни бум бум. Превратить детскую логическую задачу в факториальную сложность, это 5!

Никак не могу с Вами согласиться. Конечные автоматы это достаточно простая тема и я ее уже много раз эффективно применял.

Вот доказательства.

Техникум: Конечный Aвтомат Обработки Сигнала с Кнопки
https://habr.com/ru/articles/760088/

Техникум: Распознавание Вещественного Числа из Строчки
https://habr.com/ru/articles/757122/

Cross-Detect для Проверки Качества Пайки в Электронных Цепях
https://habr.com/ru/articles/762142/

Load-Detect для Проверки Качества Пайки
https://habr.com/ru/articles/756572/

H-мост: Load Detect (или как выявлять вандализм)
https://habr.com/ru/articles/709374/

Задача про две ёмкости для жидкости
https://habr.com/ru/articles/662561/

Синтаксический разбор CSV строчек
https://habr.com/ru/articles/765066/

Пуск Беспроводной CLI на Микроконтроллере
https://habr.com/ru/articles/929086/

Конечный Aвтомат Аппаратного I2C-Трансивера
https://habr.com/ru/articles/856548/

Принцип Определения Дальности Между UWB Трансиверами (Конечный Автомат Для DS-TWR)
https://habr.com/ru/articles/723822/

Теория управления шаговым двигателем (или как вертеть PTZ камеру)
https://habr.com/ru/articles/709500/

Load‑detect в hi‑side ключах
https://habr.com/ru/articles/1071882/

Квантование на Триггерах Шмитта
https://habr.com/ru/articles/1003262/

Конечный автомат инкрементного энкодера
https://habr.com/ru/articles/1044930/

Обзор Протокола ISO-TP [ISO 15765-2]
https://habr.com/ru/articles/798489/

ПасТильда: ещё одна прошивка
https://habr.com/ru/articles/706470/

SoftSerial: Программный UART на STM32
https://habr.com/ru/articles/973392/

Декодирование BPSK Модуляции из Звука (или передача данных по воздуху)
https://habr.com/ru/articles/848068/

Запуск I2S Трансивера на Artery [часть 2] (DMA, FSM, PipeLine)
https://habr.com/ru/articles/834304/

Передача и прием данных по лазерному лучу (SDR декодирование BPSK в реальном времени)
https://habr.com/ru/articles/1023062/

aabzel 29 сен в 10:06

Интересно, есть ли адекватная перекладка этой задачи на КА?

Сделаем игру Волк-Коза-Капуста https://marsohod.org/projects/plata1/70-koza?ysclid=mumi7qzhnc461417348

https://habr.com/ru/articles/95745/ Самостоятельное изучение схемотехники. Синтез автоматов на триггерах. Часть 1 @Brotherofken

Siemargl 29 сен в 10:19

это всё не отменяет того, что как и любой инструмент, КА хорошо подходит не для любой задачи

и элемент понимания заключается в том, куда КА совать не стоит

aabzel 29 сен в 11:24

И где же КА неприменимы?

Siemargl 29 сен в 12:23

Эта задача уже неудобна

Таблица переходов тут получается весьма громоздкая.

А будет не 4 персонажа, а 5?

misha_erementchouk 29 сен в 10:58

Сложность, скорее, экспоненциальная. Отражает то обстоятельство, что представленное решение подразумевает некоторое обобщение (когда только и имеет смысл говорить о сложности) и то, что это обобщение может быть НП-сложным, вообще говоря, особенно не удивляет.

Siemargl 29 сен в 11:18

все задачи о количестве в перестановках - факториал (максимум)

misha_erementchouk 29 сен в 11:47

На здоровье. Здесь не решается задача о перестановках. В задаче всего состояния (количество берегов в степени количества перемещаемых объектов). Решается через построение графа переходов (для этого используется формализм конечных автоматов) и поиск в нем маршрута, не проходящего через указанные вершины. Сложность этой задачи линейна по числу вершин и ребер. Отсюда получается, в худшем случае, экспонента.

Где здесь можно факториал углядеть, ума не приложу.

Siemargl 29 сен в 12:19

Где здесь можно факториал углядеть, ума не приложу.

В учебнике. Количество элементов - это одно, количество перестановок этих эл-тов - другое.

Задача коммивояжера - построение путей через граф - NP-полная, факториальная сложность.

Необразованность тут чую я.

misha_erementchouk 29 сен в 12:44

А вы не в учебник, а на задачу смотрите.

Алгоритм Дейкстры

Siemargl 29 сен в 14:05

Ок, согласен, у нас нет задачи обойти все вершины, как у коммивояжера. Задача Дейкстры ближе, причем все ребра у нас равноценны.

Итого при n участниках и одноместной лодке 2^n узлов графа и менее 2^n*(n-1) ребер (менее - отбрасывая недопустимые).

Это и будет сложность.

misha_erementchouk 29 сен в 15:35

Да, примерно так, только ребер не больше, чем узлов в квадрате, поэтому число ребер не превосходит 2^(2n). Любопытность в том, что если не ставить задачу сначала полностью задать весь КА и потом искать маршрут, а начать искать маршрут, скажем, поиском в ширину, и по надобности достраивать КА, то сложность начинает выглядеть куда меньше, чем грубая оценка.

Проблема здесь в том, что обобщений много, а таких чтобы они были интересными и при этом имели решение - гораздо меньше. Например, в задачу можно добавить камни, которые никому неинтересны и которым никто не нужен. Несложно увидеть, что, направив поиск в ширину в нужном направлении, сложность будет линейно зависеть от числа камней. Что все еще хуже, чем нужно (от числа камней не зависит), но, по крайней мере, никакой экспоненты нет: до главного массива состояний, которые отличаются перестановкой камней, поиск никогда не дойдет.

А можно добавить новых персонажей со сложной картиной взаимных конфликтов. Легко попасть в ситуацию, когда решения нет, за исключением случая, когда лодка вмещает больше двух пассажиров. Возникает задача о минимальной вместимости, когда решение есть. Эту вместимость называют числом Алкуина, и как показано в работе, на которую я выше дал ссылку (свободно доступную версию можно найти здесь), задача о нахождении этого числа является НП-сложной. Найти что-нибудь про сложность восстановления расписания перевозки, когда емкость лодки равна числу Алкуина навскидку не получилось. В принципе, варианты разные могут быть.

Siemargl 29 сен в 16:00

Я неочевидно записал формулу кол-ва ребер, яснее так. Поскольку в лодку помещается обязательно мужик и остается n-1 вариант пассажиров (ребро - это перевозка мужик+кто-то), то ребер будет

$2^{n} \cdot (n - 1)$

А даже наверно, если еще посчитать вариант без пассажиров то

$2^{n} \cdot n$

А КА при этом вообще не нужен, поскольку задача чисто переборная. Автор строил КА руками, а при этом легко потерять или узел или ребро графа. А при таком росте вообще бессмысленно для большего числа участников.

axion-1 29 сен в 09:35

Перебор всех состояний с проверкой на валидность показывает, что у нас всего только 16 реальных состояний

aabzel 29 сен в 09:42

Проще закодировать состояние четырьмя битами, по одному для волка, козы, капусты и человека. Волк на левом берегу - 0, на правом - 1 и т.д. Не понадобится ничего перебирать и загромождать схему.

Гениально!

misha_erementchouk 29 сен в 10:43

Здесь характерный паттерн возникает. Возьмем, скажем, волка, и пусть берегов будет больше, чем два, скажем . Мы начинаем с того, что вводим - битный вектор состояний, например, для двух берегов - 00, 01, 10, 11. Ключевое наблюдение: из всех этих состояний допустимыми являются только те, где есть ровно одна единица. Скажем, для получаем 001, 010, 100. Т.е. ни что иное как унитарный код. Отсюда выводим, что "настоящей" переменной, определяющей состояние, будет переменная, принимающая значений, и его битовое представление оказывается вторичным.

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

wataru 30 сен в 11:31

Тоже зашел, чтобы оставить этот комментарий. Это кажется очевидным же. Все состояния - это произведение всех возможных состояний каждой части всей системы. Каждая часть (волк, коза...) могут иметь 2 состояния.

wataru 30 сен в 11:33

Тут кажется натягивание совы на глобус. При чем тут автоматы? Тут есть пространство состояний и переходы между ними. Задача найти путь в пространстве сосотяний. Это задача на графы.

Зарегистрируйтесь на Хабре, чтобы оставить комментарий