Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Задан граф без контуров с порядковой функцией и одной из числовых. Найти путь из вершины xi в вершину xj с минимальным (максимальным) значением числовой функции. Вершины xi и xj единственны в своих уровнях.
Пример. Задан граф с порядковой функцией и числовой на дугах. Найти мин. путь.
Решение. 1. Начиная с xi рассмотрим последовательно все вершины графа, в порядке возрастания его порядковой функции. Вершины одного и того же уровня рассматриваем в произвольном порядке. Приписываем каждой вершине А число, равное минимальному значению пути из xi в А. Такие приписывания будем показывать цифрами в кружочках.
2. Выбор минимального пути после разметки осуществляется одним из двух способов:
а). Начинаем выбор с вершины xi, помеченной меткой "0". Выбираем далее вершины xj в соответствии с рисунком:
В нашем случае
б). Начинаем выбор с конечной вершины пути. Выбираем далее вершины xi в соответствии с рисунком:
В нашем случае:
Обоснованием предложенного алгоритма являются теоремы оптимальности.
Условие применимости - наличие у графа порядковой функции.
В описанном алгоритме рассматривался оптимальный путь между начальным и конечным уровнями с единственной вершиной.
Рассмотрим теперь случай, когда начальный и/или конечный уровни содержат более одной вершины.
Общая постановка задачи:
Задан граф без контуров с порядковой функцией и одной из числовых функций. Найти оптимальный путь между уровнями Еn и Еr, причём r>n.
Решение. Ищется предложенным ранее способом с некоторой модификацией. Для этого на графе вводятся дополнительные две вершины - вход E и выход S. Вход Е соединяется дугами со всеми вершинами уровня Еn. При этом каждой дуге приписывается значение "0". Все вершины уровня Еr соединяются дугами с выходом S, при этом каждой дуге также приписывается значение "0".
Затем граф размечается и ищется минимальный путь из Е в S.
Дата публикования: 2015-01-13; Прочитано: 219 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!