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

13 апреля 2011 г.

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

Для примера я возьму классическое условие: три сосуда на 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), если еще меньше, то отсеется еще две клетки по побочной диагонали:
  • А что, если будет наоборот — воды дано меньше?
    Тогда отсекаться клетки будут из противоположного угла:
  • Так же с помощью этой таблицы или графа можно легко вычислить, что переливание будет недостижимо.
    Спасибо за внимания, надеюсь, этот алгоритм вы нашли интересным.

Теги: рубрика Программирование
  • Похожие статьи
  • Предыдущие из рубрики