Решение задачи на переливание с помощью графа
В этом посте я покажу алгоритм решения с помощью графа известной задачи на переливание.
Для примера я возьму классическое условие: три сосуда на 3,5 и 8 литров соответственно. В 8-ми литровом сосуде у нас 8 литров жидкости. С помощью переливаний, удовлетворяющих следующим правилам надо получить в каком-нибудь из сосудов 4 литра жидкости:
- Переливать можно только полностью всю жидкость, или столько, сколько влезает в сосуд;
- Выливать жидкость вне сосуда нельзя;
- Наливать жидкость извне нельзя.
Граф будет задан в виде таблицы, описывающей количество жидкости в 3-х и 5-ти литровых сосудах. Количество жидкости в 8-ми литровом сосуде вычисляется вычитанием.
Первоначально таблица выглядит так:
Где, зеленая позиция — исходное состояние или нулевое, а красные — это то, куда мы должны попасть.
Теперь немного о правилах передвижения в этой таблице:
- Переливать мы можем только полностью, так что задействованы будут только «края» таблицы
- Направление для переливания 3=>8 или же 8=>3 вертикально, т.е. не затрагивается количество в 5-ти литровом сосуде
- Направление для переливания 5=>8 или же 8=>5 горизонтально, т.е. не затрагивается количество в 3-х литровом сосуде соответственно
- Направление для переливания 5=>3 или же 3=>5 по побочной диагонали, т.е. так, чтобы количество жидкости в 8-ми литровом сосуде не менялось
Теперь примемся за заполнение таблицы. Клетки таблицы будем заполнять таким образом, что бы в клетке был номер соответствующий минимальному количеству переливаний, за которое модно достичь этого состояния.
Из точки (0, 0) мы можем попасть в точку (3, 0) или же (0, 5), поставим там цифры 1:
Продолжим заполнять таблицу, пока не достигнем нужной нам ячейки:
Так же эту таблицу можно преобразовать в орграф — тогда задача сводится к классическому алгоритму поиска минимального пути:
Приведена маленькая таблица для удобства иллюстрирования графа.
Теперь еще несколько нюансов:
- А что, если воды будет дано больше, чем помещается в рассматриваемых сосудах(для этой задачи, например, девять)?
Тогда в таблице будет недоступна клетка (0, 0), если еще меньше, то отсеется еще две клетки по побочной диагонали:
- А что, если будет наоборот — воды дано меньше?
Тогда отсекаться клетки будут из противоположного угла:
Так же с помощью этой таблицы или графа можно легко вычислить, что переливание будет недостижимо.
Спасибо за внимания, надеюсь, этот алгоритм вы нашли интересным.