Поиск решения задачи Водолей по графу состояний

Задачи «Водолей» удобно решать не перебором случайных последовательностей команд, а поиском по графу состояний. Каждая вершина графа описывает, сколько воды находится в каждом сосуде, а каждое ребро соответствует одному допустимому переливанию; поиск в ширину находит путь с минимальным числом переливаний.

Модель задачи: состояния и переходы

Перед построением графа нужно определить вместимости сосудов, их начальные объёмы и условие цели. Например, для сосудов вместимостью \(5\) и \(3\) литра состояние можно записывать парой \((x,y)\): \(x\) — количество воды в первом сосуде, \(y\) — во втором. Начальное состояние обозначим \(S_0\), а целевым назовём любое состояние, удовлетворяющее условию задачи.

Описание формата состояния и допустимых действий важно прочитать заранее: состояние сосудов задаёт вершины графа, а команды исполнителя Водолей задают переходы между ними. В некоторых задачах разрешены только переливания, в других можно также наполнить сосуд или вылить его содержимое.

Для двух сосудов число потенциальных состояний не превосходит \((A+1)(B+1)\), если вместимости выражены целыми литрами. Однако реально достижимых состояний может быть меньше. Например, при некоторых вместимостях сохраняется общий делитель, поэтому часть пар никогда не появится.

Как строятся переходы

Рассмотрим переливание из сосуда \(X\) вместимостью \(A\) в сосуд \(Y\) вместимостью \(B\). Если текущее состояние \((x,y)\), то из первого сосуда можно перелить объём \(d\), равный минимуму доступной воды и свободного места во втором сосуде.

Аналогично для переливания из \(Y\) в \(X\):

Если разрешены дополнительные команды, для каждого состояния добавляются переходы наполнения и опустошения. Например, наполнить первый сосуд можно так: \((x,y)\to(A,y)\), а вылить его содержимое: \((x,y)\to(0,y)\). Все команды, которые не изменяют состояние, не добавляются: переход из вершины в саму себя не помогает найти более короткое решение.

Поиск кратчайшего решения

Все операции имеют одинаковую стоимость: одна команда — одно переливание или другое действие исполнителя. Поэтому используется минимальное число переливаний, а алгоритмически это поиск в ширину (BFS). Он просматривает сначала начальное состояние, затем все состояния на расстоянии \(1\), потом на расстоянии \(2\) и так далее.

Для каждой найденной вершины хранят три сведения: посещалась ли она, расстояние от начала и предшествующее состояние. Предшественник нужен, чтобы восстановить не только длину решения, но и саму последовательность переливаний. Очередь обеспечивает порядок обработки по слоям.

очередь := [начальное состояние]
посещено[начальное состояние] := истина
расстояние[начальное состояние] := 0
предок[начальное состояние] := нет

пока очередь не пуста:
    s := удалить из начала очереди
    если s — целевое состояние:
        восстановить путь по предкам
    для каждого состояния t, получаемого одной командой из s:
        если t не посещено:
            посещено[t] := истина
            расстояние[t] := расстояние[s] + 1
            предок[t] := s
            добавить t в конец очереди

если очередь пуста:
    решения нет

Множество посещённых состояний обязательно: один и тот же узел может быть получен разными последовательностями команд. Если добавлять его в очередь повторно, возникнут циклы и лишняя работа. Это связано с общей идеей обхода пространства состояний исполнителем.

Разобранный пример: сосуды 5 и 3 литра

Пусть оба сосуда изначально пусты, разрешены наполнения, опустошения и переливания, а требуется получить ровно \(4\) литра в первом сосуде. Обозначим состояние как \((x,y)\), где вместимости равны \(5\) и \(3\).

Получена последовательность из \(8\) команд. В реальной задаче BFS не угадывает эту цепочку, а строит её автоматически: для каждого состояния рассматриваются все разрешённые команды, а при достижении цели сохраняются предки.

Оценка перебора и практический алгоритм

Если вместимости равны \(A\) и \(B\), число пар состояний не превосходит \((A+1)(B+1)\). Для каждой вершины проверяется постоянное число команд, поэтому время работы BFS имеет порядок \(O(AB)\), а память — также \(O(AB)\). Для трёх и более сосудов число состояний становится произведением \((A_1+1)(A_2+1)\cdots(A_n+1)\).

Перед программированием полезно составить таблицу переходов вручную для нескольких состояний. Это помогает проверить, не перепутаны ли вместимости, направление переливания и условие остановки. Если команды имеют разные стоимости, обычный BFS уже не подходит: тогда нужен другой алгоритм поиска кратчайшего пути.