Решение этой проблемы требует немного абстрактного мышления. Когда я использую эту задачу в классах, первая общая идея - смоделировать каждый контейнер как узел на графе. Эта модель имеет интуитивно понятный смысл - контейнеры - единственные вещи в проблеме, поэтому, конечно, они будут узлами . Но эта идея терпит неудачу, когда мы пытаемся продолжить с процессом моделирования. Вот несколько вопросов, которые я задаю, чтобы помочь студентам увидеть разбивку:
- Если узлы являются контейнерами, есть ли только два узла во всем графе?
- Если узлами являются три контейнера, каковы края?
- Если узлами являются три контейнера, какой объект на графике представляет собой контейнер с 6 литрами воды?
На эти вопросы сложно ответить, если узлы являются контейнерами. Итак, что еще мы могли выбрать в качестве узлов? Решение состоит в том, чтобы сделать каждый узел текущим состоянием обоих контейнеров. Теперь мы можем выбрать, чтобы края отображали действия, которые мы можем предпринять. В частности, мы можем перелить жидкость из одной емкости в другую и попасть в новый узел. В этой модели может быть несколько узлов, которые представляют решение - любой узел, в котором один из трех контейнеров имеет ровно шесть литров, является решением.
В этой модели также определен начальный узел. В формулировке проблемы говорится, что 12-литровый контейнер полон, а два других пусты. Вот небольшое подмножество графика:
В этой модели наши края ориентированы - переливание из 12-литрового контейнера в 5-литровое - это не то же самое, что переливание из 5-литрового контейнера в 12-литровое. Кроме того, наши действия не всегда обратимы. Рассмотрим нижнее правое состояние на изображении выше: если бы мы налили 12-литровый контейнер в 8-литровый, мы бы добавили 3 литра к 8-литровому контейнеру, оставив нам 4/12 и 8/8. Если бы мы попытались «повернуть вспять» это действие, нам пришлось бы перелить все 8 литров обратно в 12-литровый контейнер, и мы вернулись бы к началу.
Наконец, наши края невзвешены. Все эти действия могут быть выполнены в равной степени, и, что касается нашего вопроса, на самом деле нет разницы в масштабах выполнения одного действия над другим. Мы могли бы заставить эту задачу требовать утяжеления по краям, спросив, какое наименьшее количество жидкости может быть перенесено, чтобы в одном кувшине было ровно 6 литров воды. Но не будем забегать вперед - нам еще предстоит решить легкую версию. Вот путь в нашем графе, который решает загадку:
Графики, подобные этому, где узлы - это состояния, а края - действия / переходы между состояниями, называются «конечными автоматами», и они довольно распространены. Интернет-протоколы, такие как TCP, используют конечные автоматы для облегчения связи между двумя компьютерами в Интернете. Алгоритмы обучения с подкреплением и марковские процессы принятия решений используют и расширяют концепцию конечного автомата. Парсеры регулярных выражений также обычно используют конечный автомат.
Следующая статья из серии: Поиск в ширину и глубину
