Об алгоритме и постановках задач на переливание жидкости

[eugrita]

Известен тип задач на переливание жидкостей из одних емкостей в другие с целью получения заданного объема в емкости. Известно 2 основных типа таких задач -Водолей (одна емкость неограничена – можно сливать и выливать любое количество), Переливашка – все емкости ограничены. Рассмотрим 2 тип задач при $N=3$ емкостях.
Постановка.
Даны 3 емкости $N_1,N_2,N_3$
1-я емкость полна , т.е вектор количеств жидкости
$\bar{k}=(N_1,0,0)$
Надо :
1 вар) Получить заданное количество $m$ жидкости в одной из емкостей
2вар) Получить заданное распределение количеств во всех емкостях (с точностью до перестановок)
На рис.изображен граф переливаний для $N_1=12$.На нем указаны не все возможные переходы, а только самые короткие переходы. Возможные петли не изображены. Другими словами видимо построено кратчайшее дерево переходов.

Анализ этого примера показывает, что для 1-го варианта постановки есть недостижимое количество $M=9$, которое невозможно получить. Кроме того (2 постановка) есть множество недостижимых распределений количеств. Для данного примера это (с точностью до перестановок)
$(8,1,3), (8,2,2), (6,2,4), (4,4,4),(10,1,1)$
Возникают интересные вопросы об алгоритме построения кратчайших количеств переливаний $k(m)$ для заданного $m$ $0<m<N_1$
а также нахождения недостижимых количеств и распределений количеств. А также об оценках функции роста этого алгоритма, и оценках мах количества шагов для заданного количества $m$
Программистский способ решения задачи –видимо в написании рекурсивной программы строящий множество достижимых количеств (вершины) и находящей кратчайшие пути.
Есть ли применения этой задачи в других областях?

[Deggial]

Тема перемещена из форума «Олимпиадные задачи (М)» в форум «Карантин»
Причина переноса: нечёткая формулировка задач и мусор

eugrita, наберите текст темы чётко, последовательно и без лирических отступлений и ответвлений.

После исправлений сообщите в теме Сообщение в карантине исправлено, и тогда тема будет возвращена.

Тема перемещена из форума «Карантин» в форум «Олимпиадные задачи (М)»
Ура! Возвращено.

[Sender]

Геометрическая интерпретация представляется более наглядной, на мой взгляд. Если мы сопоставим каждому вектору количеств точку в $3$-мерном евклидовом пространстве с соответствующими координатами, получим примерно такую картину. Недостижимые конфигурации в данном случае представлены точками, лежащими внутри параллелограмма.

[eugrita]

поясните это. рис. подобный вашему я видел (это т.н. "бильярдная" интерпретация) но не задачи Переливашка а Водолей.
В моем случае надо бы тогда уж использовать 3-мерн вариант не прямоугольник а параллелепипед. Из приведенного вами рис никаких выводов сделать не могу ни я ,Ни кто другой

[Sender]

Нетрудно заметить, что при любых переливаниях общее количество жидкости остаётся постоянным, т.е. всё происходит в плоскости $x+y+z=12$. На рисунке изображена проекция этой плоскости на одну из координатных плоскостей. Поскольку сумма объёмов двух меньших сосудов не превышает объём третьего, задача эквивалентна "водолею" с объёмами сосудов $5$ и $7$.

[eugrita]

Может и так, только "скрытие" одной из степеней свободы искажает истинную геометрическую картину. И я не согласен ,что задача эквивалента Водолею. Не эквивалентна!
Предлагаю всем подумать над другим.
Фактически в моем примере показано кратчайшее остовное дерево графа состояний. Тем самым эта задача близка к задаче поиска кратчайших путей графа и могут быть применены метод Краскалла, Дейкстры, Флойда???
Т.е. возможен ли компьютерный алгоритм который сначала строит все вершины состояний (в нашем случае вершина-тройка чисел) а после (или в процессе построения вершин) строит это самое дерево кратчайших путей.
Результат в виде этого дерева и будет выходом алгоритма.
Например в известной олимпиадной задаче даны 3 бочки с квасом
$N_1=16 , N_2=11, N_3=6$ (1-я полная),требуется разлить квас поровну. Конечным состоянием в построенном дереве будет $(8,8,0)$ . Мы ищем эту вершину в построенном дереве и выдаем результат. (можно конечно это же дерево построить ручками и убедиться что$k=17$ )
Аналогично если 1 постановка задачи, например "Найти количество переливаний
для получения 2л, или скажем, 3л тогда опять же просмотром построенного дерева состояний находим результат $k(2)=15$ или $k(3)=12$

[Munin]

eugrita в сообщении #877064 писал(а):

Может и так, только "скрытие" одной из степеней свободы искажает истинную геометрическую картину.

Нет. Если бы какие-то два разных состояния проецировались в одно - искажало бы. А так нет.

[eugrita]

Наверное так. Интерпретации могут быть разные. Только как вы с помощью этой картинки будете решать поставленные задачи? как будете моделировать количество шагов для попадания или проверки недостижимости заданной точки?
Критерий выхода из цикла? До первого попадания в пройденную точку? (т.е. до замыкания дерева?) В принципе это возможно. Принцип Дирихле говорит, что нельзя в $N$ клеток рассадить $N+1$ кроликов по одному
2)Эта интерпретация 2-мерная и потому наглядная. А в общем случае $n>3$ емкостей? В этом случае вам на каждом шаге приходилось бы выбирать не $0,1,2$вариантов а больше. Т.е. дерево-есть дерево но не обязательно двоичное.
3)Я попробую на матлаб реализовать ваш вариант алгоритма "отражения от стенок", но для общего случая мне видится все-таки рекурсивная программа на С++ или другом яз.

[iifat]

Ну, если картинка соответствует дереву, то и любому алгоритму на дереве соответмтвует алгоритм на картинке. Только (имхо!) картинка нагляднее.

[Munin]

eugrita в сообщении #877091 писал(а):

Только как вы с помощью этой картинки будете решать поставленные задачи?

А разве не видно?

[eugrita]

при такой геометрической интерпретации 1 постановка (получение заданного количества $m$) для 2d-случая видимо соответствует первому приходу в состояние $x=m$ или $y=m $ или $x+y=N-m$ где $N=N_1+N_2+N_3$
в многомерном случае сложнее
Ну что-ж вынужден уже не в 1-й раз признать, что источником многих математических задач является физика
Хочу также обратить внимание на известное в литературе условие разрешимости этой задачи.
Если объемы 2 меньших сосудов взаимно простые числа, а объем большего сосуда больше или равен сумме объемов двух меньших, то можно отмерить любое целое количество $m$
$NOD(N_2,N_3)=1, N_1 \ge N_3+N_2$

[arseniiv]

eugrita в сообщении #877101 писал(а):

Ну что-ж вынужден уже не в 1-й раз признать, что источником многих математических задач является физика

Переливание жидкости в идеальных стаканчиках — физика?

($\TeX.$)

Ну ведь так просто написать \text{НОД} или \mathrm{GCD}:

$$\text{НОД}(N_2,N_3),\quad\mathrm{GCD}(N_2,N_3).$$

(Хотя правильнее будет \operatorname{\text{НОД}} и \operatorname{GCD} — вёрстка во многих случаях будет аккуратнее, включая обращение с пробелами в зависимости от окружения. \text тут везде используется только из-за неотображения кириллицы в математической моде; насколько помню, есть пакеты, это исправляющие.)

[eugrita]

К сожалению, я обладаю. способностью высказывать ошибочные и неточные утверждения. Обращаю внимание на то,что на рис. Sender изображена вовсе не траектория в виде прямолинейных отрезков,отражаемых от стенок а дерево или, точнее, граф (cвоебразная укладка графа). С опозданием, жалею о высказанной мной физической аналогии между этой задачей и отражением луча от стенок прямоугольника.
В самом деле, из точки$(0,0)$ возможно 2 пути:
$(0,0),(7,0)$ и $(0,0),(0,4)$
из точки $(7,0)$ тоже 2 пути: $(7,0),(2,5)$ но и $(7,0),(7,5)$ и т.д.
Поэтому без графов или как минимум, двоичных деревьев не обойтись. И задача сложнее моделирования движения шарика в прямоугольнике.
Поэтому мне интересно, как это Munin на вопрос об алгоритме ответил что все "видно из рис." - ничего не видно, надо считать, сравнивать

[eugrita]

Попытаемся выявить основное звено алгоритма. Думаю так
$k_1,k_2,k_3$ текущие количества жидкостей
ЕСЛИ $k_2=N_2 \bigwedge k_3=N_3$ ТО ВОЗВРАТ (переливания невозможны)
ЕСЛИ $k_2<N_2 ТО
(ЕСЛИ $k_1>0$ ТО $1\to 2 \bigvee ЕСЛИ $k_2>0$ ТО 2 \to 1 $)
ЕСЛИ $k_3<N_3 ТО
(ЕСЛИ $k_1>0$ ТО $1\to 3 \bigvee ЕСЛИ $k_2>0$ ТО 3 \to 1 $)
именно эти условия определяют ветвление. (Можно условные операторы выписать математически точно а не схематично как у меня)

[Psw]

Такие задачи удобно решать в трилинейной СК, можно посмотреть здесь - http://e-science.ru/forum/index.php?showtopic=19400
Там в 7-ом посту есть ссылка