7 апреля 2011 в 04:31

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

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

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


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