Оптимизация пути в графах с контурами

Пример.

Постановка задачи оптимизации пути в графах без контуров.

Теорема оптимальности 2.

То же самое, что и в предыдущей теореме. только вместо l_i=j(x_i) пишем m_ij=j(x_i,x_j)

Задан граф без контуров с порядковой функцией и одной из числовых. Найти путь из вершины x_i в вершину x_j с минимальным (максимальным) значением числовой функции. Вершины x_i и x_j единственны в своих уровнях.

Пример. Задан граф с порядковой функцией и числовой на дугах. Найти мин. путь.

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

2. Выбор минимального пути после разметки осуществляется одним из двух способов:

а). Начинаем выбор с вершины x_i, помеченной меткой "0". Выбираем далее вершины x_j в соответствии с рисунком:

В нашем случае

б). Начинаем выбор с конечной вершины пути. Выбираем далее вершины x_i в соответствии с рисунком:

В нашем случае:

Обоснованием предложенного алгоритма являются теоремы оптимальности.

Условие применимости - наличие у графа порядковой функции.

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

Рассмотрим теперь случай, когда начальный и/или конечный уровни содержат более одной вершины.

Общая постановка задачи:

Задан граф без контуров с порядковой функцией и одной из числовых функций. Найти оптимальный путь между уровнями Е_n и Е_r, причём r>n.

Решение. Ищется предложенным ранее способом с некоторой модификацией. Для этого на графе вводятся дополнительные две вершины - вход E и выход S. Вход Е соединяется дугами со всеми вершинами уровня Е_n. При этом каждой дуге приписывается значение "0". Все вершины уровня Е_r соединяются дугами с выходом S, при этом каждой дуге также приписывается значение "0".

Затем граф размечается и ищется минимальный путь из Е в S.

Для графов с контурами поиск максимального пути затруднён, т.к. он может не существовать. Для отыскания минимального пути существуют разные алгоритмы.

Алгоритм Форда.

Общая постановка задачи:

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

Примечание: Порядковая функция графа не задана.

Решение: Для поиска минимального пути между x₀ и x_n руководствуются следующими правилами:

1. Вершине x₀ приписывается метка l₀ =0. Всем остальным x_i приписывается l_i=¥.

2. Выбирается произвольная дуга x₀®x_i и вершине x_i приписывается метка l_i¢=l₀+l(x₀,x_i), где l(x₀,x_j) - вес дуги между x₀ и x_i.

3. Для вершины x_j с меткой l_j ищется вершина x_i, от которой идёт такая дуга в x_j, что l_j¢ < l_j и где: l_j¢=l_i+l(x_i,x_j).

Вершине x_j приписывается метка l_j¢.

4. После разметки всех вершин графа для произвольной вершины x_j с меткой l_j рассматриваем все вершины x_i с дугами, ведущими в вершину x_j, и выбирается новая метка l_j¢ < l_j и такая, что l_j¢ является минимальной из всех возможных меток.

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

6. Выбор минимального пути осуществляют по правилам получения минимального пути для графа без контуров.

Дата добавления: 2015-01-03