Вниз
Скачать: 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.034 c
2-1165939314
Болт
2006-12-12 19:01
2006.12.31
Из какой папки зпущенна программа


1-1163079758
Сатир
2006-11-09 16:42
2006.12.31
Прорисовка формы на панели другой формы


2-1165594661
Серый
2006-12-08 19:17
2006.12.31
StrigGrid


15-1165475150
codeCleaner
2006-12-07 10:05
2006.12.31
Удобочитаем ли следующий код?


2-1165750746
arturich
2006-12-10 14:39
2006.12.31
TWebBrowser




   Наверх