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

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

Для примера я возьму классическое условие: три сосуда на 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:


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

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

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


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

You can't comment this post because its author is not yet a full member of the community. You will be able to contact the author only after he or she has been invited by someone in the community. Until then, author's username will be hidden by an alias.