2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Как быстро вычислить минимальную сумму
Сообщение20.01.2011, 14:54 
Аватара пользователя


05/06/08
479
Задача формулируется предельно просто и чем-то напоминает вычисление дискриминанта.
Есть матрица с положительно определёнными элементами:
$A = a_{n,m} $
$a_{n,m} \ge 0$ и $m \ge n$
Требуется вычислить минимальную сумму:
$\Delta  = \mathop {\min }\limits_{p\left( {\alpha _n ,m} \right)} \left\{ {\sum\limits_{i = 1}^n {a_{i,\alpha _i } } } \right\}$
Где минимизация ведётся по всевозможным перестановкам:
$p\left( {\alpha _n ,m} \right) = \alpha _1 ,\alpha _2 ,...,\alpha _n$
для
$\alpha _n  \in \left\{ {1,2,...,m} \right\}$ и $\alpha _k  \ne \alpha _l $
Так как число перестоновок равно
$\left| {p\left( {\alpha _n ,m} \right)} \right| = \frac{{m!}}{{\left( {m - n} \right)!}}$
то прямой поиск минимума для больших матриц - задача экспоненциальной сложности,
и у меня вопрос, как найти минимум с полиномиальным числом операций.
Наверняка существуют алгоритмы типа метода Гаусса для вычисления дискриминантов.

 Профиль  
                  
 
 Re: Как быстро вычислить минимальную сумму
Сообщение20.01.2011, 15:38 
Заслуженный участник
Аватара пользователя


11/03/08
10215
Москва
Это у Вас "Задача о назначении".
Решаема, например "Венгерским методом" (сложность кубическая).
Описан в учебниках по оптимизации и матпрограммированию.

 Профиль  
                  
 
 Re: Как быстро вычислить минимальную сумму
Сообщение20.01.2011, 18:46 
Аватара пользователя


05/06/08
479
Евгений Машеров в сообщении #402258 писал(а):
Это у Вас "Задача о назначении".
Решаема, например "Венгерским методом" (сложность кубическая).
Описан в учебниках по оптимизации и матпрограммированию.

Спасибо за ссылку.
А задача точно не NP-hard?
Ибо сильно похожа на транспортную задачу.
PS Действительно О($n^3$)

 Профиль  
                  
 
 Re: Как быстро вычислить минимальную сумму
Сообщение20.01.2011, 22:15 
Заслуженный участник
Аватара пользователя


11/03/08
10215
Москва
Да, это частный случай транспортной задачи. Особенность в том, что в оптимальном решении не n+m-1 ненулевых "перевозок", а ровно n, так что метод потенциалов трудноприменим.
Но транспортная задача частный случай ЛП, а оно полиномиально.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 4 ] 

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



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

Сейчас этот форум просматривают: nimepe


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

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