2014 dxdy logo

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

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




 
 Совершенное паросочетания минимальной стоимости
Сообщение21.06.2014, 17:48 
Добрый день.
Никто не поможет ссылкой на алгоритм для нахождения совершенного паросочетания минимальной стоимости (по сути она же задача о назначениях) используя в основе поиск пути минимальной стоимости (дейкстры). День потратил, много где описано, что это есть, но алгоритм не нашел. По сути нужно только описание идеи.

 
 
 
 Re: Совершенное паросочетания минимальной стоимости
Сообщение21.06.2014, 20:13 
Если Вас интересует алгоритм Эдмондса, то я его видел в книге
Ловас. Пламмер. Прикладные задачи теории графов.

 
 
 
 Re: Совершенное паросочетания минимальной стоимости
Сообщение25.11.2015, 14:36 
Задача о назначениях довольно просто сводится к min-cost-max-flow. При решении min-cost-max-flow можно воспользоваться алгоритмом Дейкстры для поиска дополняющего пути.

 
 
 [ Сообщений: 3 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group