Практическое занятие 3 Тема: матричный алгоритм поиска оптимальных путей Контрольные вопросы

1. Виды матричных алгоритмов поиска множества путей.

2. Сущность матричного алгоритма поиска оптимальных путей при воз-ведении матрицы в степень Rmax_.

3. Построение элементов матричного алгоритма.

4. Условия получения оптимальной матрицы .

Матричные методы основываются на превращении исходных матриц и других в матрицы оптимальных длине , рангу , стоимости и др. характеристик путей, каждый элемент которых определяет длину (ранг, стоимость) оптимального пути из узла и к узлу j.

100

Рисунок 3.1 – Изображение графа для поиска

Для получения матриц ( , ) необходимо исходную матрицу весов последовательно умножить на себя, возвести в степень Rmax=n–1, где (n– количество узлов сети), изменив процедуру перемножения матриц и введя операцию «Δ»:

.

Каждый элемент с_іj матрицы определяется как минимум из почленных сумм элементов i-й строки матрицы и j-го столбца матрицы , т.е.

(3.0)

Для графа, изображенного на рис. 3.1, матрица длин которого сведена в матрицу 3.1, процедура формирования элементов матрицы осуществляется в соответствии с выражением:

подписать

	0	50		20		Первая строка
	50	0	40	30	10	, второй столбец
	50	50		50		почленные суммы

откуда = min (50, ) = 50.

Аналогично определяются все элементы матрицы , потом и, наконец, .

Эту процедуру используют для получения матриц путей минимальной стоимости , придав элементам смысл стоимости ветви .

Исходной для определения путей минимального ранга является матрица , полученная из матрицы , в которой элементы заменены на .

Для графа (рис. 3.1) матрица записана в виде матрицы (3.2).

Процедура возведения матрицы в степень Rmax аналогична рассмотренной для матрицы .

Следует отметить, что при преобразовании матрицы на любом этапе, новые значения Rij достаточно определить лишь для элементов , поскольку, если на предыдущем этапе определенный ранг пути , то в дальнейшем найденное значение ранга оптимизировать (уменьшить) не возможно.

	0	1		1		первая строка
	1	0	1	1	1	, (3.3) второй столбец
	1	1		2		почленные суммы

где = min (1, 2, ) = 1.

Заметим также, что при возведении матрицы R⁽¹⁾ в любую степень операцию (3.3) нужно применять лишь к тем элементам матрицы , которые еще не определены, то есть . Как только при возведении в очередную степень q матрицы R⁽¹⁾ все элементы (i,j = 1, n, граф G – связный), процесс вычисления R_опт нужно прекратить.

Полученная матрица R^(q) = R_опт.