Рассмотрим граф, изображенный на рис. 5.

1.2.2. Пример

Рассмотрим граф, изображенный на рис. 5.

Предположим, что , т.е. нам нужно найти три кратчайших пути из вершины во все вершины графа.

Рис. 5. Пример применения алгоритма двойного поиска

Тогда матрица этого графа имеет вид:

Шаг 1: Составляем вектор начальных оценок длин трех кратчайших путей из вершины во все вершины графа. Т.к. является начальной вершиной, следовательно, первая компонента вектора равна 0, а остальные берем произвольно.

также возьмем произвольно и равными между собой.

Тогда .

Шаг 2:

При используем формулу обратного поиска , где матрица имеет вид:

(Изначально, в векторе оценок все компоненты равны : ).

Сначала находим четвертый элемент оценочной строки . Выполняем операцию обобщенного сложения . В “терминах строк и столбцов” это можно записать: , т.е.

Затем выполняем операцию обобщенной минимизации .

Таким образом, .

Ищем третий элемент оценочной строки (теперь используется третий столбец матрицы ).

Ищем второй элемент оценочной строки (теперь используется второй столбец матрицы ).

Ищем первый элемент оценочной строки (теперь используется первый столбец матрицы ).

Таким образом, .

Теперь используем формулу прямого поиска: , где матрица имеет вид:

Сначала ищем первый элемент оценочной строки . Выполняем операцию обобщенного сложения . В “терминах строк и столбцов” это можно записать: , т.е.

Затем выполняем операцию обобщенной минимизации .

Таким образом, .

Теперь ищем второй элемент оценочной строки . В “терминах строк и столбцов” операцию обобщенного сложения можно записать: , т.е.

Затем выполняем операцию обобщенной минимизации .

Таким образом, .

Теперь ищем третий элемент оценочной строки . В “терминах строк и столбцов” операцию обобщенного сложения можно записать: , т.е.

Затем выполняем операцию обобщенной минимизации .

Таким образом, .

Теперь ищем четвертый элемент оценочной строки . В “терминах строк и столбцов” операцию обобщенного сложения можно записать: , т.е.

Затем выполняем операцию обобщенной минимизации .

Таким образом, .

Пусть . Используем формулу обратного поиска .

Сначала находим четвертый элемент оценочной строки . Выполняем операцию обобщенного сложения . В “терминах строк и столбцов” это можно записать: , т.е.

Затем выполняем операцию обобщенной минимизации .

Таким образом, .

Ищем третий элемент оценочной строки .

Ищем второй элемент оценочной строки .

Ищем первый элемент оценочной строки .

Используем формулу прямого поиска: .

Пусть . Используем формулу обратного поиска: .

Используем формулу прямого поиска: .

Пусть . Используем формулу обратного поиска: .

Получилось, что . На этом этапе работа алгоритма заканчивается.

Табличная запись работы алгоритма двойного поиска представлена в таблице 2.

Чтобы узнать кратчайших пути из начальной вершины во все остальные вершины графа нужно провести процедуру трассировки. После ее проведения мы видим, что:

Из в с длиной пути равной 0: .

Из в с длиной пути равной 16: .

Из в с длиной пути равной 17: .

Из в с длиной пути равной 6: .

Из в с длиной пути равной 7: .

Из в с длиной пути равной 9: .

Из в с длиной пути равной 5: .

Из в с длиной пути равной 8: .

Из в с длиной пути равной 21: .

Из в с длиной пути равной 13: .

Из в с длиной пути равной 14: .

Из в с длиной пути равной 15: .

Дата добавления: 2015-08-29