2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Об алгоритме и постановках задач на переливание жидкости
Сообщение03.07.2014, 00:47 
Заслуженный участник
Аватара пользователя


15/10/08
11536
Метод треугольника полезен, ежели сосудов (внезапно!) три. Когда их четыре, можно попытаться, конечно, порисовать пути в пирамиде, но мало у кого имеется настолько развитое пространственное воображение. Так что алгоритмы рулят.

 Профиль  
                  
 
 Re: Об алгоритме и постановках задач на переливание жидкости
Сообщение03.07.2014, 11:56 
Заслуженный участник
Аватара пользователя


30/01/06
72407
Вообще-то с четырьмя это даёт ещё большее упрощение по сравнению с "алгоритмами".

 Профиль  
                  
 
 Re: Об алгоритме и постановках задач на переливание жидкости
Сообщение19.07.2014, 19:40 
Заслуженный участник


08/04/08
8556
Рассмотрим задачу о переливании с 3-я конечными сосудами. Попробуем определить, какие состояния достижимы с помощью переливаний, а какие - нет.
Используем предложенную выше геометрическую интерпретацию. Если в $j$-м сосуде налито $x_j$ литров жидкости, то $(x_1;x_2;x_3)$ - целая точка в 3-хмерном пространстве. $x_1+x_2+x_3=V=\mathrm{const}, x_j\geqslant 0$ - это соотношения ограничивают треугольник в $\mathbb{R}^3$, далее, если $n_j$ - объем $j$-й банки, то получим еще ограничения $x_j\leqslant n_j$ - это 3 плоскости, при отсечении ими можем получить 3,4,5- или 6-иугольник. Фигуру и ее внутренности обозначим $F$, пересечение $F\cap \mathbb{Z}^3$ обозначим $G$. Допустимым переливаниям из банки в банку соответствуют отображения $\varphi$ точек из $G$ в $G$ по прямым, лежащим внутри $G$, параллельным какой-то координатной плоскости. Действие отображений незачем ограничивать только целыми точками $G$, лучше распространить его сразу на все $F$.
Задача о переливании примет вид: дана точка $M$ в $F$ и отображения $\varphi$. Определить, достижима ли или нет какая-то точка $H\in F$.
У $F$ есть собственно внутренность, границы и вершины. Ясно, что если исходная точка лежит на внутренности $F$, то любое действие переводит ее на границу $F$, причем не более чем 3-я способами. Далее рассматриваем только точки на границе.
Рассмотрим произвольную граничную точку из $F$, не являющуюся вершиной. Из нее можно сделать 4 варианта хода: 2 переводят точку в вершины, еще 2 - в другую граничную точку, не являющуюся вершиной. Первые 2 хода не рассматриваем. После того, как выбран один из 2-х вариантов хода, все последующие нетривиальные ходы (не отменяющие предыдущие) определяются единственным образом. Т.обр., у нас получается класс граничных точек, изоморфный $\mathbb{Z}$ по связности. Точки внутри класса достижимы. Достижимость точек, не явлющихся вершинами - отношение эквивалентности, так что граница $\partial F$ разбивается на классы. Если мы учтем еще и вершины, то мы получим, что граница фигуры $\partial F$ разбивается на 2 множества: $\partial F=F_1+F_2$, $F_1$ - множество вершин $\partial F$ и достижимых из них точек, $F_2=\partial F\setminus F_1$. Все точки $F_1$ достижимы из любой точки $F_2$, обратное неверно. $F_1$ представляет собой один класс эквивалентности по отношению достижимости, а $F_2$ может оказаться разбитым на множество классов.
Ясно, что все точки $F_1$ достижимы, остается рассмотреть $F_2$.
Будем рассматривать самый общий случай, когда $\partial F$ - 6-иугольник.
Покажем, что на длины сторон 6-иугольника можно наложить некоторые ограничения, не уменьшающие общности. Рассмотрим пары параллельных сторон 6-иугольника. Если в одной из пар стороны достаточно длинные, то их можно "уменьшить" следующим образом. Пусть $ABCDEF$ - 6-иугольник ($F$ здесь - это не та $F$, которая выше, а другая). Пусть $AB$ и $DE$ достаточно длинны. Тогда, если исходная точка $M\in AB$ например, то ее путь в границе $ABCDEF$ в результате отображений имеет вид: $M_0=M\to M_1\to M_2\to M_3\to...$, где $M_0, M_2, M_4,... \in AB$, а $M_1,M_3,...\in DE$. Если параллелограмм $M_0M_1M_3M_2$ "влазит" (существует) в $ABCDEF$, то его можно "вырезать" - построить новый 6-иугольник, получающийся склеиванием кусков $M_0ABCM_1$ и $M_2M_3DEF$, причем классы $F_2$ в новом 6-иугольнике являются ограничениями классов $F_2$ старого 6-иугольника (это несложно показать, я не буду это писать, а то длинно будет).
Будем применять подобную операцию "обрезания" исходного 6-иугольника до тех пор, пока она возможна. Полученный в результате 6-иугольник обозначим $F_X$. Заметим, что исходная задача на $F$ может быть сведена к рассмотрению аналогичной задачи в $F_X$ - вместо исходных точек в ней лишь следует брать их образа после преобразования "обрезания" $F$. В итоге, мы можем изначально считать $F$ обрезанным.
Далее, рассмотрим действие $\varphi$ на $F$. Это действие не является даже группоидом. Однако, действие можно свести к рассмотрению действия некоей группы на некотором множестве.
В качестве множества выберем 2 некоторых смежных ребра $F$ - $AB$ и $BC$ (точнее - все их точки из $F_2$) - "ломаная" $L$. В качестве действия на $M\in L$ выберем такую степень $k$ (возможно, зависящую от $M$), что $\varphi^k(M)$ снова лежит в $L$ (т.е. просто отображаем точку, пока она не вернется снова куда-то в $L$). Такое $k$ действительно существует для каждой точки (я, честно говоря, доказательство не писал явно, однако Вы можете убедиться в этом сами. Для этого нужно перебрать все возможные варианты сторон, в которые может попадать $M$ в результате действия $\varphi$ какое-то количество раз и увидеть, что какой-то образ $M$ опять попадает в $L$. (я специально выбрал в качестве $L$ две смежные стороны, одной стороны недостаточно. А вот для 5-иугольника можно выбрать одну сторону - у меня есть явный расчет) Далее, я замечу, что число шагов $k$ ограничено - в "обрезанном" 6-иугольнике верхняя его граница не зависит от параметров $V, n_j$, потому в $L$ попадает множество точек класса достижимости "конечного индекса").
Обозначим отображение, действующее в пределах $L$ буквой $\pi$. Действие $\varphi$ на пары точек в $\partial F$ локально сохраняет метрику, потому $\pi$ тоже ее сохраняет в $L$, потому, если $x$ - локальная координата в $L$, то $\pi(x)=A\pm x$. Значит $\pi$ - кусочно-линейная функция на $L$. Докажем, что число кусков в $L\cap G$, на которых $\pi$ линейна, ограничено абсолютной константой, не зависящей от параметров фигуры (т.е., что $\pi$ - перестановка). Для этого вернемся к рассмотрению $\varphi$ и вспомним, что стороны 6-иугольника - целые числа (а значит существует их НОД). Возьмем произвольную сторону $l\in L$ 6-иугольника. Рассмотрим ее образ $\varphi(l)$. Если он лежит внутри стороны 6-иугольника, то все нормально - отображаем дальше. Если он попал на несколько разных сторон 6-иугольника, то разобъем его на несколько отрезков так, чтобы отрезки отображались целиком внутрь своего ребра. Т.к. число сторон 6-иугольника ограниченно, то число таких отрезков тоже будет ограниченно. После нескольких разбиений отрезки из $l\in L$ снова попадут в $L$. Если $l$ и его образ пересекаются - разобъем их их пересечением. Получим, что каждая сторона $L$ была разбита на ограниченное число кусков, на которых $\pi$ действует линейно.
Таким образом, $\pi$ действует на $L$ кусочно-линейно, причем число кусков ограниченно абсолютной константой. Значит при действии $\psi$ на целую точку в $L\cap G$ мы получим орбиту ограниченной мощности. Поскольку 6-иугольник был "обрезан", то в "обрезанном" 6-иугольнике орбита каждой точки имеет ограниченную мощность.
Теперь уже понятно, что орбита вершин также имеет ограниченную мощность.
Отсюда следует, что если параметры 6-иугольника будут достаточно велики, то мы получим, что $F_2$ имеет $>1$ класса достижимости. В результате получаем, что задача может быть решена следующим образом - "обрезаем" нашу фигуру, после чего число достижимых состояний в результате переливаний станет равным $O(1)$ - все достижимые точки можно тупо вычислить. Если искомая точка находится среди достижимых, то задача имеет решение и его можно явно найти, иначе - нет.
Кроме того, для достаточно больших параметров $V, n_j$ существуют как 6-иугольники, в которых все точки достижимы, так и 6-иугольники, в которых некоторые точки недостижимы.

Надеюсь, что этот текст понятен :-(
Могу пояснить детально.
Времени мало, но я могу еще подумать и написать более понятно.

 Профиль  
                  
 
 Re: Об алгоритме и постановках задач на переливание жидкости
Сообщение19.07.2014, 23:07 
Заслуженный участник
Аватара пользователя


15/10/08
11536
Я упрощу: все достижимые состояния можно отыскать прямым перебором.

 Профиль  
                  
 
 Re: Об алгоритме и постановках задач на переливание жидкости
Сообщение19.07.2014, 23:19 
Заслуженный участник


08/04/08
8556

(нифига)

Утундрий в сообщении #888837 писал(а):
Я упрощу: все достижимые состояния можно отыскать прямым перебором.
Не, Вы написали, что число решений равно $O(V)$, а я - что число решений после "обрезания" фигуры равно $O(1)$.
Бе-бе-бе :bebebe:

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 20 ]  На страницу Пред.  1, 2

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group