Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 13.02.2009, 12:14
гость

 
Сообщений: n/a

Оптимальное наполнение резервуаров
Подскажите где можно найти информацию об оптимальном алгоритме наполнения резервуаров. Задач следующая. Имеются произвольное количество резервуаров произвольного объема и произвольное количество различных жидкостей произвольного объема. Необходимо наполнить резервуары так, чтобы максимально вместить жидкости в резервуары, при этом разные жидкости нельзя смешивать. Заранее благодарю.
  #2  
Старый 13.02.2009, 13:50
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Какой критерий - минимальный общий остаток жидкостей?
  #3  
Старый 13.02.2009, 13:53
Пользователь

Отправить личное сообщение для subdmitry Посмотреть профиль Найти все сообщения от subdmitry
 
Регистрация: 21.05.2008
Сообщений: 64

Сообщение от гость Посмотреть сообщение
Подскажите где можно найти информацию об оптимальном алгоритме наполнения резервуаров. Задач следующая. Имеются произвольное количество резервуаров произвольного объема и произвольное количество различных жидкостей произвольного объема. Необходимо наполнить резервуары так, чтобы максимально вместить жидкости в резервуары, при этом разные жидкости нельзя смешивать. Заранее благодарю.
В принципе если число_сосудов^число_жидкос ей не больше допустимых вычислительных ресурсов (скажем, порядка 10^10-10^13 (секунды-дни)), то можно это просто перебрать. Иначе могу порекомендовать что-то из http://en.wikipedia.org/wiki/Global_optimization. Затрудняюсь так навскидку сказать, что из приведенных там подходов в данном случае будет лучше работать. В принипе можно попробовать Monte-Carlo with optimization (генерируем случайно начальные подмножества сосудов для каждой жидкости и пытаемся их улучшить перебрасыванием из группы в группу так, чтобы качество решения только возрастало, и так много раз, запоминая лучшее найденное решение), similated annealing, genetic algorithms, memetic algorithms.
  #4  
Старый 13.02.2009, 14:35
гость

 
Сообщений: n/a

Сообщение от MBo Посмотреть сообщение
Какой критерий - минимальный общий остаток жидкостей?
да
  #5  
Старый 13.02.2009, 14:37
гость

 
Сообщений: n/a

Сообщение от MBo Посмотреть сообщение
Какой критерий - минимальный общий остаток жидкостей?
и максимальный свободный остаток пустоты в резервуарах
  #6  
Старый 13.02.2009, 14:45
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Пардон, сначала показалось, что эти критерии могут конфликтовать
  #7  
Старый 13.02.2009, 16:11
гость

 
Сообщений: n/a

может какие нибудь комбинированные методы, например, перебор с нечеткой логикой смешать, думал генетическим методом, но довольно трудно сообразить, как делать операции (скрещивание и т.п.)
  #8  
Старый 13.02.2009, 17:20
Пользователь

Отправить личное сообщение для subdmitry Посмотреть профиль Найти все сообщения от subdmitry
 
Регистрация: 21.05.2008
Сообщений: 64

А вышеупомянутые вероятностные методы почему попробовать не хотите? Или с английским проблема?
  #9  
Старый 13.02.2009, 17:30
MBo MBo вне форума
Местный

Отправить личное сообщение для MBo Посмотреть профиль Найти все сообщения от MBo
 
Регистрация: 21.09.2006
Адрес: Новосибирск
Сообщений: 1,374

Задача похожа на задачу о назначениях (и сводится к ней при равенстве количеств сосудов и резервуаров, и решается венгерским методом за полиномиальное время). Интересно, не получится ли по аналогии свести к задаче нахождения максимального потока (здесь ограничение действует на единственность дуги, вхдящей в резервуар)
  #10  
Старый 13.02.2009, 18:32
гость

 
Сообщений: n/a

Сообщение от subdmitry Посмотреть сообщение
А вышеупомянутые вероятностные методы почему попробовать не хотите? Или с английским проблема?
да, проблемы, но я приблизительно понял, попробую, но хотелось каким нибудь комбинаторным...
Сообщение от MBo Посмотреть сообщение
...
количество сосудов и резервуаров абсолютно произвольное... А что за "нахождения максимального потока" ? Какой принцип?
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Оптимальное размещене многоугольника Wiedzmin Вычислительная геометрия 0 13.04.2008 17:54
Оптимальное разбиение числа на сумму кубов Belyaev_Igor Математические алгоритмы (другое) 5 06.02.2008 00:45
Оптимальное распределение ресурсов Silen Математические алгоритмы 2 20.12.2007 13:06
Оптимальное расположение триангулярной сетки по заданным точкам alexiy Вычислительная геометрия 11 05.08.2007 10:29
оптимальное размещение Rufus Математические алгоритмы 1 06.12.2006 00:10