Как формализовать реку, берега и персонажей
Человеку свойственно решать подобные загадки методом проб и ошибок в уме. В простых случаях такой перебор срабатывает быстро, но при увеличении числа персонажей или усложнении ограничений мозг начинает ходить по кругу. Чтобы передать решение компьютеру, задачу нужно строго формализовать на языке дискретной математики.
Каждое фиксированное положение всех участников процесса называется состоянием системы. Для классической задачи с волком, козой и капустой участников четверо. Обозначим их буквами: крестьянин (K), волк (W), коза (G) и капуста (C). Река делит мир ровно на две части. Персонаж всегда находится либо на левом берегу, либо на правом.
В программировании положение каждого участника удобно кодировать булевым значением. Ноль обозначает левый берег, а единица обозначает правый берег. Тогда текущее положение дел записывается кортежем из четырёх бит в строгом порядке K-W-G-C. Например, кортеж 0000 фиксирует старт, когда все находятся на левом берегу. Кортеж 1111 задаёт целевое состояние, означающее успешную переправу всей компании на правый берег.
Фильтрация запрещённых вершин
Поскольку участников четверо и у каждого есть ровно два варианта расположения, общее число комбинаций составляет два в четвёртой степени. Это даёт ровно шестнадцать потенциальных состояний. Значительная часть этих комбинаций нарушает правила выживания персонажей.
Правило безопасности формулируется просто. Волк нападает на козу, если они остаются на одном берегу без человека. Коза съедает капусту, если они остаются вдвоём без человека. Присутствие крестьянина гарантирует полную безопасность любого соседства.
- Состояние 0110 запрещено, потому что волк и коза оказались на правом берегу без присмотра крестьянина.
- Состояние 1001 запрещено, так как волк и коза брошены на левом берегу, пока человек уплыл на правый.
- Состояние 0011 запрещено из-за козы и капусты, оставленных на правом берегу.
- Состояние 1100 запрещено по той же причине, но уже на левом берегу.
- Состояние 0111 запрещено, ведь волк с козой и капустой остались на правом берегу совершенно одни.
- Состояние 1000 зеркально запрещено, так как крестьянин уехал направо, оставив всю цепочку хищников и добычи на левом берегу.
Из шестнадцати исходных комбинаций шесть отбрасываются сразу. В сухом остатке остаётся ровно десять допустимых вершин, между которыми и будут строиться маршруты.
Построение рёбер между состояниями
Ребро между двумя вершинами графа существует только тогда, когда между ними возможен прямой переход за один рейс лодки. Переход подчиняется строгим физическим законам задачи. Лодка не способна плыть самостоятельно, поэтому координата крестьянина обязана меняться при каждом переходе с нуля на единицу или наоборот.
Вместимость лодки строго ограничена. Крестьянин может плыть в одиночку либо взять с собой ровно одного пассажира. При этом попутчик обязан находиться на том же берегу, откуда отправляется лодка. Значит, при любом допустимом ходе меняется либо один бит человека, либо бит человека вместе с битом ровно одного взятого спутника. Менять положение сразу двух грузов за один рейс запрещено.
Поскольку любой рейс лодки можно совершить туда и обратно, граф получается неориентированным. Переход из состояния А в состояние Б означает равноправную возможность вернуться из Б в А.
Почему для поиска пути используется BFS
Когда граф построен, задача сводится к поиску пути между вершиной 0000 и вершиной 1111. В теории графов существуют два базовых метода обхода: поиск в глубину (DFS) и поиск в ширину (BFS). Для поиска наименьшего количества рейсов всегда выбирают поиск в ширину.
Поиск в глубину идёт по первой попавшейся ветке до упора. Он легко заходит в длинные обходные пути или зацикливается, если не хранить историю посещений. В результате алгоритм находит какой-то путь, но длина этого маршрута может оказаться далека от идеала.
Поиск в ширину работает иначе. Он использует структуру данных очередь (FIFO) и исследует граф концентрическими кругами. Сначала алгоритм просматривает все вершины, достижимые за один шаг. Затем проверяются все вершины, достижимые за два шага, потом за три, и так далее. На невзвешенном графе ребро каждого шага имеет одинаковую стоимость, равную единице. Первая же встреча с целевой вершиной 1111 при послойном обходе гарантирует строго минимальную длину пути.
Пошаговый разбор кратчайшего маршрута
Запуск BFS на нашем графе из десяти безопасных вершин даёт кратчайший маршрут ровно из семи переправ. Вот как выглядит этот путь на языке векторов состояний.
- Шаг первый: переход из 0000 в 1010. Человек везёт козу на правый берег. Волк и капуста спокойно ждут на левом.
- Шаг второй: переход из 1010 в 0010. Человек возвращается на левый берег один. Коза остаётся справа в полной безопасности.
- Шаг третий: переход из 0010 в 1110. Человек забирает волка и перевозит его на правый берег.
- Шаг четвёртый: переход из 1110 в 0100. Ключевой маневр задачи. Человек не может оставить волка с козой, поэтому забирает козу обратно на левый берег.
- Шаг пятый: переход из 0100 в 1101. Человек оставляет козу на левом берегу, забирает капусту и отвозит её к волку на правый берег. Волк капусту не ест.
- Шаг шестой: переход из 1101 в 0101. Человек возвращается на левый берег один, оставляя волка с капустой на правом берегу.
- Шаг седьмой: переход из 0101 в 1111. Человек забирает козу и завершает переправу.
На третьем шаге существует симметричная ветка. Вместо волка крестьянин мог отвезти капусту, затем вернуть козу, привезти волка и последним рейсом снова забрать козу. Длина пути при этом остаётся неизменной и составляет ровно семь рейсов.
Масштабирование метода на сложные задачи
Графовый подход ценен своей универсальностью. Задача о волке, козе и капусте проста, но точно такой же математический аппарат применяется к гораздо более массивным сюжетам.
Классический пример посложнее — задача о миссионерах и людоедах. Три миссионера и три каннибала должны пересечь реку на двухместной лодке. Если на любом берегу людоедов окажется больше, чем миссионеров, миссионеров съедят. Состояние здесь описывается парой чисел для одного берега, а общее пространство состояний насчитывает 16 пар с учётом положения лодки. Вручную не запутаться в переходах уже сложно, а алгоритм BFS находит оптимальную цепочку из одиннадцати переправ за долю миллисекунды.
По аналогичной схеме работают планировщики в робототехнике, логистические калькуляторы и алгоритмы прохождения лабиринтов. Пространство параметров превращается в вершины, допустимые физические действия становятся рёбрами, а поиск оптимального плана действий сводится к нахождению кратчайшего пути на графе.
Частые вопросы
Почему нельзя использовать алгоритм Дейкстры вместо BFS?
Алгоритм Дейкстры использовать можно, но в этом нет практического смысла. Дейкстра предназначен для взвешенных графов, где переходы имеют разную стоимость или разное время. В классической переправе каждый рейс лодки стоит ровно единицу. На таких невзвешенных графах BFS работает быстрее и требует меньше вычислительных ресурсов, обходясь обычной очередью вместо очереди с приоритетом.
Что делать, если граф состояний слишком большой и не помещается в память?
В масштабных задачах граф не генерируют целиком заранее. Вершины и переходы создают на лету прямо во время обхода. Для гигантских пространств состояний применяют эвристический алгоритм A* (A-star) или алгоритм IDA*, которые оценивают примерное расстояние до цели с помощью математической функции и исследуют в первую очередь самые перспективные ветки.
Как алгоритм защищается от бесконечного зацикливания лодки?
Алгоритм хранит множество уже посещённых вершин (visited set). Если лодка совершает рейс туда и обратно, вернувшись в конфигурацию, которая уже встречалась ранее, алгоритм отбрасывает эту ветку и не добавляет её в очередь повторно.
Всегда ли существует решение у задач о переправе?
Существование решения определяется связностью графа. Если начальная и целевая вершины лежат в одной компоненте связности, решение гарантированно есть. Если правила задачи делают невозможным ни один безопасный ход из какого-то положения, граф распадается на изолированные части, и путь найти невозможно.