Кратчайшие пути в графе. Способы их отыскания в зависимости от типа графа

Рассмотрим нагруженные графы , в которых каждой дуге поставлено в соответствие число . Очевидно, что если граф связный и существуют не единственные пути (маршруты), соединяющие вершины s и t, то интересует вопрос об отыскании пути из s в t минимальной длины. Если, конечно, в графе существуют циклы отрицательного веса, то минимального пути не существует. Поэтому имеет смысл задача поиска минимальных путей (маршрутов), число дуг (ребер) которых ограничено сверху. Приведем некоторые свойства минимальных путей в орграфе : 1. если для любого , то минимальный путь является простой цепью; 2. если – «минимальный» путь, то для любых i,j таких, что , путь также минимален; 3. если – минимальный путь среди путей из в , содержащих не более k дуг, то - минимальный путь среди путей из в , содержащих не более k-2 дуг. Все сказанное справедливо и для неориентированных графов. Рассмотрим несколько вариантов задач поиска кратчайших путей. Случай неотрицательной матрицы весов. Один из наиболее эффективных алгоритмов решения задачи о кратчайшем (s-t) – пути дал Дейкстра. Он основан на приписывании вершинам временных пометок, дающих верхнюю границу длины пути от s к этим вершинам. В итерационном процессе эти пометки уменьшаются, причем на каждом шаге одна из пометок обязательно становится постоянной, что указывает на равенство пометки кратчайшему пути от s к указанной вершине. Тогда можем ввести пометку вершины в виде , где – величина пометки, – признак пометки: , если пометка временная; , если пометка постоянная. Алгоритм Дейкстры. Шаг 1. Присвоение начальных значений. Положить и для всех . Положить p=s. Шаг 2. Обновление пометок. Все вершины такие, что ( и ) приобретают пометки в соответствии с правилом: . Шаг 3. Превращение пометки в постоянную. Находим . Шаг 4. Полагаем и . Шаг 5. а) (Если надо найти лишь путь от s к t) Если p=t, является длиной кратчайшего пути. Останов. б) (Если требуется найти пути от s ко всем остальным вершинам.) Если все , то – дают длины кратчайших путей. Останов. Если найдется такое, что перейти к шагу 2. Если требуется найти кратчайшие пути между s и всеми другими вершинами полного связного графа с числом вершин |X|=n, то в процессе работы алгоритма выполняется n(n-1)/2 операций сложения (шаг 2), и вдвое больше число операций сравнения (шаг 2 и шаг 3). Таким образом, общее число операций пропорционально . Случай общей матрицы весов. Если матрица весов дуг является произвольной матрицей, то дуги, «приносящие доход», должны иметь отрицательные «стоимости». В этом случае можно воспользоваться эффективным алгоритмом Форда - Беллмана. В этом алгоритме никакая из меток не является окончательной. В конце k-й итерации пометки равны длинам тех кратчайших путей (от s ко всем остальным вершинам), которые содержат не более k+1 дуг. Пометка вершины в этом алгоритме имеет смысл длины пути и имеет структуру: , где i - индекс вершины, l - численная величина пути в конце k+1 - й итерации. Описание алгоритма. Присвоение начальных значений. Шаг 1. Полагаем для всех и для . Обновление пометок. Шаг 2. Для изменить пометку следующим образом: (2), где . S содержит теперь все вершины, для которых кратчайшие пути из s состоят из k дуг, - содержит те вершины, для которых текущие кратчайшие пути из s состоят из k дуг и для которых существуют дуги к вершине . Если , то кратчайший путь от s к не может состоять из k+1 дуг, и поэтому изменять пометку не нужно. Для вершин положить . Проверка на окончание. Шаг 3. а) Если и для , то получим оптимальный ответ, и пометки равны длинам кратчайших путей. Останов. б) Если , то перейти к шагу 4. в) Если , то в графе существует цикл отрицательного веса и задача не имеет решения. Останов. Подготовка к следующей итерации. Шаг 4. Обновить множество S следующим образом: . Шаг 5. Положить k=k+1 и перейти к шагу 2. Как только получено решение исходной задачи, сами веса (длины) кратчайшего пути получаются из соотношения (2). Пути можно получить, если в дополнение к пометке для каждой вершины хранить и другую пометку . Пометка указывает вершину, непосредственно предшествующую вершине в кратчайшем пути от s к на k-й итерации. Начать можно так . Пометки ищем в соответствии с выражением (2): (3). Если – вектор, составленный из пометок q при завершении работы алгоритма, то кратчайший путь от s к получается в обратном порядке, при прохождении последовательно от до предшествующей, содержащейся в метке q, и так далее до s. Описанный алгоритм можно применять и в случае неотрицательной матрицы весов. Нужно учесть, что для алгоритма Дейкcтры требуется операций, а для приведенного . Если требуется найти кратчайшие пути между всеми парами вершин графа, то можно воспользоваться n-кратным повторением одного из рассмотренных алгоритмов в зависимости от значений весов матрицы. Для положительно взвешенных графов алгоритм Дейкстры даст затраты, пропорциональные , а для произвольных весов дуг (ребер) алгоритм Форда-Беллмана – . Более эффективным в поставленной задаче является алгоритм Флойда, вычислительные затраты которого для отыскивания кратчайших путей между всеми парами вершин составляет величину, пропорциональную , и на положительно взвешенных графах более эффективнее алгоритма Дейкстры. Исходными данными для алгоритма является матрица весов , в которой и , если в графе . Алгоритм Флойда. Шаг 1. Формирование начальных установок. Создадим рабочую матрицу кратчайших путей T=C, т.е. . Покажем k=0. Шаг 2. Рабочая итерация. Полагаем k=k+1. Для всех i=k, таких что , и для всех , таких, что , выполним операцию . Шаг 3. а) Если , то в графе G существует цикл отрицательного веса, содержащий вершину , и решения нет. Останов. б) Если и k=n, то получено решение задачи и значение кратчайших путей. Останов. в) Если , но , то перейти к шагу 2.

Задача№1

Задача №2

1. Оценка уравнения регрессии.

Определим вектор оценок коэффициентов регрессии. Согласно методу наименьших квадратов, вектор s получается из выражения:

s = (X^TX)^-1X^TY

Матрица X

	3.1	0.8
	3.5	0.5
	3.5	0.8
	4.4	0.8
	4.9	0.8
	6.1	2.2
	6.8	1.4
	10.4	2.3
	18.4	6.4
	19.6	5.3

Матрица Y

Матрица X^T

3.1	3.5	3.5	4.4	4.9	6.1	6.8	10.4	18.4	19.6
0.8	0.5	0.8	0.8	0.8	2.2	1.4	2.3	6.4	5.3

Умножаем матрицы, (X^TX)

В матрице, (X^TX) число 10, лежащее на пересечении 1-й строки и 1-го столбца, получено как сумма произведений элементов 1-й строки матрицы X^T и 1-го столбца матрицы X

Умножаем матрицы, (X^TY)

Находим обратную матрицу (X^TX)^-1

0.4	-0.0934	0.21
-0.0934	0.0482	-0.14
0.21	-0.14	0.43

Вектор оценок коэффициентов регрессии равен

s = (X^TX)^-1X^TY =

Уравнение регрессии (оценка уравнения регрессии)

Y = -3.9558 + 8.2279X₁ + 2.8434X₂