Граф состояний Водолея
Граф состояний Водолея — это модель задачи о переливаниях, в которой каждое состояние сосудов является вершиной, а разрешённое переливание — ребром графа. Такой граф помогает увидеть все возможные действия исполнителя и найти путь от начального состояния к требуемому.
Как задаётся состояние
Если вместимости сосудов равны \(A\) и \(B\), состояние можно записать парой \((x,y)\), где \(x\) — количество воды в первом сосуде, а \(y\) — во втором. Всегда выполняются ограничения \(0\le x\le A\) и \(0\le y\le B\). Например, \((2,5)\) означает, что в первом сосуде 2 единицы воды, а во втором — 5.
Из состояния проводятся рёбра по всем командам, которые можно выполнить. Точный набор команд определяется правилами исполнителя; их удобно повторить на странице команд исполнителя Водолей. После каждого переливания записывают новое состояние и соединяют его с предыдущим.
Пусть сосуды имеют вместимости 3 и 5, а текущее состояние — \((3,2)\). Переливаем из первого сосуда во второй: во втором свободно \(5-2=3\) единицы, поэтому вода из первого полностью переливается. Получаем состояние \((0,5)\). В графе появляется ребро \((3,2)\to(0,5)\). Если переливать обратно, получится другое ребро.
Какое утверждение правильно описывает ребро графа состояний?
Состояние сосудов — это вершина, например \((1,4)\). Переливание из него — это переход, или направленное ребро, к новому состоянию. Один и тот же результат может быть достигнут разными рёбрами, а некоторые состояния могут вообще не иметь пути из начального.
Чтобы найти решение, в графе ищут путь от начальной вершины до вершины, где выполнено условие задачи. Для поиска кратчайшего числа команд обычно применяют поиск решения по графу состояний. Само описание отдельных вершин рассматривается в статье «Состояние сосудов».
Главное
- Вершина графа — это пара объёмов воды \((x,y)\).
- Ребро показывает выполнение одной разрешённой команды и направлено от старого состояния к новому.
- Решение задачи — путь от начального состояния к подходящей конечной вершине.