Скачать: 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.029 c