Экстремальные пути и контуры на графах
Далее цитата - В.Н. Бурков, Д.А. Новиков. Элементы теории графов.
Задачи поиска кратчайших и длиннейших путей на графах возникают в различных областях управления. Сначала мы рассмотрим задачи о кратчайшем пути, затем задачи об экстремальных контурах.
Задача о кратчайшем пути. Пусть задана сеть из n + 1 вершины, то есть ориентированный граф, в котором выделены две вершины – вход (нулевая вершина) и выход (вершина с номером n). Для каждой дуги заданы числа, называемые длинами дуг. Длиной пути (контура) называется сумма длин входящих в него дуг (если длины дуг не заданы, то длина пути (контура) определяется как число входящих в него дуг). Задача заключается в поиске кратчайшего пути (пути минимальной длины) от входа до выхода сети.
Задача о ранце. Пусть имеется n предметов, которые могут быть полезны в походе. Полезность i-го предмета оценивается числом ai, вес предмета (или его объем) – bi. Суммарный вес, который может нести турист (объем рюкзака), ограничен величиной R. Требуется найти набор предметов, обладающий максимальной суммарной полезностью и удовлетворяющий ограничению.
Задача поиска контура минимальной длины. Если известно, что искомый контур содержит некоторую вершину, то нужно определить кратчайшей путь от этой вершины до нее же.
Задача поиска контура минимальной средней длины заключается в поиске контура, для которого минимально отношение его длины к числу содержащихся в нем дуг.
Путь максимальной эффективности. Пусть задана сеть, в которой для каждой дуги (i; j) определены два числа (Эij; Sij), интерпретируемые как эффект при осуществлении соответствующей операции – Эij и затраты на эту операцию – Sij. Эффективность K(m) пути m определяется как отношение его эффекта Э(m) = к затратам S(m) = , то есть K(m) = Э(m) / S(m). Задача заключается в поиске пути m* максимальной эффективности: K(m) -> max.
Путь максимальной эффективности с учетом штрафов.
В разработке
Первая страница