Вниз
Скачать: CL | DM;

Венгерский алгоритм транспортной задачи   Найти похожие ветки 

← →
Strate ©   (2006-12-09 22:01) [0]

Здравствуйте. Не подскажете где можно почитать хорошее описание алгоритма? В частности интересует один момент, вычитанный в одном из описаний алогритма:

Шаг 2: Мы строим максимальное паросочетание на всех нулях полученных на предыдущем шаге.

Я конечно понимаю, что нужно построить паросочетание на графе, но что-то не представляю каким граф должен получится.
Была у нас допустим вот такая таблица:

5 3 2 1
4 3 5 2
5 6 10 2

после Шага 1 у нас она получилась вот такой:

2 1 0 0
0 0 2 0
1 3 7 0

Видим нули. Какой должен на них получиться граф?


← →
palva ©   (2006-12-10 01:24) [1]

У этого графа вершины это индексы строк и столбцов. Пишем для данного случая строчку с индексами строк, а потом строчку с индексами столбцов. Получаем:

1 2 3

1 2 3 4

Теперь соединяем ребрами  те вершины которые соответствуют нулям матрицы. Например, если a13 = 0, то соединяем 1 из верхней строчки с 3 в нижней. Вот такой получится граф.



Страницы: 1 вся ветка

Скачать: CL | DM;



Память: 0.45 MB
Время: 0.027 c
11-1142575284
Unknown Mystic
2006-03-17 09:01
2006.12.31
Ошибка в TKOLOpenDirDialog из MCK?


15-1165987596
balepa
2006-12-13 08:26
2006.12.31
OPC


3-1161253972
просто_человек
2006-10-19 14:32
2006.12.31
Помогите с растановкой приоритетов


15-1165919871
Jus
2006-12-12 13:37
2006.12.31
ADSL подключение


2-1166031511
callback
2006-12-13 20:38
2006.12.31
Массив с данными.




   Наверх