Решение задачи на переливание с помощью графа

В этом посте я покажу алгоритм решения с помощью графа известной задачи на переливание.

Для примера я возьму классическое условие: три сосуда на 3,5 и 8 литров соответственно. В 8-ми литровом сосуде у нас 8 литров жидкости. С помощью переливаний, удовлетворяющих следующим правилам надо получить в каком-нибудь из сосудов 4 литра жидкости:

• Переливать можно только полностью всю жидкость, или столько, сколько влезает в сосуд;
• Выливать жидкость вне сосуда нельзя;
• Наливать жидкость извне нельзя.

Граф будет задан в виде таблицы, описывающей количество жидкости в 3-х и 5-ти литровых сосудах. Количество жидкости в 8-ми литровом сосуде вычисляется вычитанием.

Первоначально таблица выглядит так:

Где, зеленая позиция — исходное состояние или нулевое, а красные — это то, куда мы должны попасть.
Теперь немного о правилах передвижения в этой таблице:

1. Переливать мы можем только полностью, так что задействованы будут только «края» таблицы
   
2. Направление для переливания 3=>8 или же 8=>3 вертикально, т.е. не затрагивается количество в 5-ти литровом сосуде
   
3. Направление для переливания 5=>8 или же 8=>5 горизонтально, т.е. не затрагивается количество в 3-х литровом сосуде соответственно
   
4. Направление для переливания 5=>3 или же 3=>5 по побочной диагонали, т.е. так, чтобы количество жидкости в 8-ми литровом сосуде не менялось
   

Теперь примемся за заполнение таблицы. Клетки таблицы будем заполнять таким образом, что бы в клетке был номер соответствующий минимальному количеству переливаний, за которое модно достичь этого состояния.

Из точки (0, 0) мы можем попасть в точку (3, 0) или же (0, 5), поставим там цифры 1:


Продолжим заполнять таблицу, пока не достигнем нужной нам ячейки:



Так же эту таблицу можно преобразовать в орграф — тогда задача сводится к классическому алгоритму поиска минимального пути:

Приведена маленькая таблица для удобства иллюстрирования графа.

Теперь еще несколько нюансов:

• А что, если воды будет дано больше, чем помещается в рассматриваемых сосудах(для этой задачи, например, девять)?
  Тогда в таблице будет недоступна клетка (0, 0), если еще меньше, то отсеется еще две клетки по побочной диагонали:
  
  
• А что, если будет наоборот — воды дано меньше?
  Тогда отсекаться клетки будут из противоположного угла:
  
  


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