Правила форума
В этом разделе
нельзя создавать новые темы. Если Вы хотите задать новый вопрос, то
не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".
Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть
удалены без предупреждения.Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса
обязан привести свои попытки решения и указать конкретные затруднения.
Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть
удалена или перемещена в
Карантин, а Вы так и не узнаете, почему.
|
DidiSD |
Совершенное паросочетания минимальной стоимости  21.06.2014, 17:48 |
|
07/06/13
2
|
|
Добрый день.
Никто не поможет ссылкой на алгоритм для нахождения совершенного паросочетания минимальной стоимости (по сути она же задача о назначениях) используя в основе поиск пути минимальной стоимости (дейкстры). День потратил, много где описано, что это есть, но алгоритм не нашел. По сути нужно только описание идеи.
|
|
|
|
 |
|
sup |
Re: Совершенное паросочетания минимальной стоимости 21.06.2014, 20:13 |
|
| Заслуженный участник |
 |
22/11/10
1184
|
|
Если Вас интересует алгоритм Эдмондса, то я его видел в книге
Ловас. Пламмер. Прикладные задачи теории графов.
|
|
|
|
|
|
helgui |
Re: Совершенное паросочетания минимальной стоимости 25.11.2015, 14:36 |
|
18/12/13
17
|
|
Задача о назначениях довольно просто сводится к min-cost-max-flow. При решении min-cost-max-flow можно воспользоваться алгоритмом Дейкстры для поиска дополняющего пути.
|
|
|
|
|
  |
Страница 1 из 1
|
[ Сообщений: 3 ] |
|
Модераторы: Модераторы Математики, Супермодераторы
