О задачах обхода графа
5
2.
В данном разделе будут рассмотрены две задачи о достижении
системой определенного состояния. Для задачи 2.1 [7] будет разобрано
решение, использующее графы [7], для 2.2 — булевы функции. Также
приведена задача об обходе шахматной доски.
2.1. Задача о переливании.
Имеется три кувшина с водой: один
объемом 8 л, заполненный водой, и два пустых, объемом 5 и 3 л.
Требуется разделить 8 л пополам, т. е. получить две емкости по че-
тыре литра в каждой.
Решение задачи с помощью графов.
Будем обозначать каждое состояние системы из трех кувшинов
парой чисел (
a
,
b
), обозначающих количество литров в кувшинах ем-
костью соответственно 5 и 3 л. На самом деле, полное описание —
это тройка (
a
,
b
,
c
), но содержимое третьего кувшина
c
(объемом 8 л)
определяется условием
a
+
b
+
c
= 8. Числа
a
,
b
,
c
— натуральные.
Начальное состояние системы — (0, 0). Желаемое состояние —
(4,0). Другие варианты не подходят, так как
b
≤ 3.
Пары (
a
,
b
) будут вершинами графа. Ориентированными ребрами
будем обозначать возможный переход из одного состояния в другое с
помощью однократного переливания.
Вопрос сводится к тому, достижима ли вершина (4,0) из вершины
(0,0) в таком графе и каким образом. Рассмотрим подробнее, как
устроен граф.
Из вершины не может выходить более шести ребер. Действи-
тельно, состояние (
a
,
b
,
c
) может измениться, если перелить воду,
например, из первого кувшина во второй или третий. Причем в зави-
симости от количества воды в другом кувшине можно либо вылить в
него всю воду, либо долить доверху, и тогда в первом кувшине еще
останется вода.
Если перелить воду из первого кувшина во второй, то состояние
будет (0,
a
+
b
,
c
) при
a
+
b
≤ 3 или (
a
– 3 +
b
, 3,
c
) при
а
+
b
> 3, а если
в третий кувшин, то (0,
b
,
c
+
a
) или (
a
– 8 +
c
,
b
, 8). Аналогично
возможны, самое большее, по два изменения при переливе воды из
второго и третьего кувшинов. Но не из каждой вершины выходит
ровно шесть ребер, возможны следующие случаи:
4 ребра, если один из меньших кувшинов полон (
a
= 5 или
b
= 3) или пуст (
a
= 0 или
b
= 0);
3 ребра, если один кувшин пуст, а другой полон (это случаи
(5, 0) или (0, 3));
2 ребра, если меньшие кувшины оба полны или оба пусты (это
(0, 0) и (5, 3));
Вершины можно изображать как точки на плоскости с координа-
тами (
a
,
b
).
На рис. 2 изображен граф с вершинами, достижимыми из (0,0).
Ребро со стрелками на обоих концах означает пару ребер с проти-
