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

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

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 21.01.2010, 16:19
Eugene86

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

Задача на поиск оптимального значения
Пусть в N-мерном пространстве задан вектор расстояний R={r1,…,rN} и вектор Q={q1,…,qN}, qk-целое, qk>=0, к=1,…,N. Переменные разбиты на М (M <= N) непересекающихся групп по Lj переменной в каждой, j=1,…M. Cумма sum(qk), входящих в каждую группу, равна Tj.
Требуется найти вектор W={w1,…,wN}, минимизирующий сумму J = sum(ck*yk) (суммирование по k=1,…,N),
и удовлетворяющий условиям:
yk >=0,
yk может принимать значения: qk, qk+1, qk-1,
sum(yk) = Tj, где суммирование ведется по переменным, входящим в j-ую группу (j=1<…,M).

Помогите мне освежить память.
Какие методы оптимизируют решение задачи?
  #2  
Старый 21.01.2010, 17:27
Eugene86

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

Насколько я понимаю программа, реализующая задачу будет выглядеть так:
Вводится вектор расстояний R и вектор Q.
Узнаю число разбиений множества Q из n элементов на m групп, пользуясь числами Стирлинга.
Далее вывожу все возможные разбиения множества Q на n групп. (Как это примерно релизовать?)
После этого пользователь указывает нужное разбиение и идёт решение задачи, например, симплекс-методом (прочитав книги, вспомнил, что это задача линейного программирования).
Только подскажите с алгоритмом разбиения на множества.
  #3  
Старый 21.01.2010, 19:30
MBo MBo вне форума
Местный

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

>Только подскажите с алгоритмом разбиения на множества.
проще всего рекурсивно разбивать.
нужно получить разбиение набора 1..N на ровно K непустых множеств?
  #4  
Старый 21.01.2010, 22:58
Eugene86

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

Сообщение от MBo Посмотреть сообщение
>Только подскажите с алгоритмом разбиения на множества.
проще всего рекурсивно разбивать.
нужно получить разбиение набора 1..N на ровно K непустых множеств?
Судя по условию задачи - Да.
  #5  
Старый 22.01.2010, 09:24
MBo MBo вне форума
Местный

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

алгоритм есть в книге
http://www.jjj.de/fxt/
глава Set partitions
  #6  
Старый 23.01.2010, 16:10
Eugene86

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

Спасибо
 


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

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


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
собственные значения матрицы гость Реализация, исходники, языки 2 10.12.2008 00:48
Задача на на поиск подстроки в строке Skytweak Сортировка и поиск 4 07.09.2008 23:07
обчисления значения многочлена гость Реализация, исходники, языки 12 06.04.2008 11:29
Быстрый поиск значения в отсортированной матрицы Igor Сортировка и поиск 2 17.02.2008 15:46
Быстрое определение попадания значения в период m_Fighter Сортировка и поиск 2 01.02.2008 08:37