Перевод: Зайцев А. А. Кратчайший путь icon

Перевод: Зайцев А. А. Кратчайший путь




НазваПеревод: Зайцев А. А. Кратчайший путь
Дата21.06.2012
Розмір95.3 Kb.
ТипДокументи

Перевод: Зайцев А.А.


Кратчайший путь


Основная проблема: найти «лучший» путь из s в t, где s и t вершины в графе. Мы измеряем «лучший» просто как суму длин ребер пути. Для примера граф должен быть картой представляющей пересечения как вершины, сегменты дороги в виде ребер, вы хотите найти каждый кратчайший путь от вашего дома к ICS. Несмотря на то, что обе эти проблемы имеют разное решение, обе они являются проблемами кратчайшего пути; в одном случае длина ребра представляет реальное расстояние в милях сегмента дороги, тогда как в другом случае это представляет время необходимое для того чтобы добраться, но в обоих случаях важным фактом является то, что общая длина пути измеряется добавлением длин отдельных ребер. Для другого примера, который я упоминал в моей первой лекции алгоритмов на графах, граф может иметь вершины представляющие собой аэропорты, с ребрами представляющими возможные полеты, и длиной ребра измеряющегося в стоимости полета; вашей проблемой является найти самый дешевый полет из SNA в JFK. Помните, что эти графы могут быть ориентированными; т.е. могут быть односторонние дороги, или полеты в одном направлении могут иметь различные стоимости чем тот же полет только в другом направлении.


Мы собираемся сделать предположение, что все ребра имеют длины с положительным значениями. Это бывает часто но не всегда так; это имеет смысл в примерах выше, но это мыслимо что авиалиния должна платить людям за определенный маршрут, длины таких ребер в графе аэропорта могут быть негативными. Мы будем полагать что этого никогда не случится. Это делает алгоритм намного проще. Позже мы увидим некоторве специальные случаи где мы сможем обработать негативные веса.

Скорее просчитается одна дистанция d(s,t), на нужно просчитать d(s,x) для всех вершин x. Это известно как проблема кратчайшего пути с одним источником (s это источник). Оказывается просчет этой экстра информации делает процедуру проще, потому что потом мы можем объединить информацию о пути с малым числом ребер чтобы получить путь со многими ребрами.

Предположим мы уже знаем расстояния d(s,x) из вершины s ко всем другим вершинам. Это не является решением проблемы кратчайшего пути, потому что мы хотим знать реальные пути обладающие такими расстояниями. Как мы можем найти такие пути? Существует два вида кратчайших путей: те которые сформированы одним ребром (s,t), и те маршрут которых следует из s в t через некоторые другие вершины; пусть x это последняя вершина на пути к вершине t. Тогда во втором случае, полный путь должен быть сформирован конкатенацией пути из s в x с ребром (x,t). Далее, путь из s в x должен быть кратчайшим путем (в противном случае конкатенация кратчайшего пути с (x,t) уменьшит длину общего пути). Следующим замечанием будет то, что d(s,x) должно быть меньше чем d(s,t), поскольку d(s,x)=d(s,t)+длина(x,t) и мы предполагаем что все ребра имеют положительные длины.


Следовательно, если мы знаем только правильное значение x, то мы можем найти кратчайший путь.

Алгоритм 1:

for each vertex y in sorted order by d(s,y)

let (x,y) be an edge with d(s,x)+length(x,y)=d(s,y)

path(s,y) = path(s,x) + edge (x,y)

Мы захотим использовать что-либо похожее на эту идею чтобы рассчитать кратчайшие пути без уже известных их длин. Когда мы добираемся к вершине y в цикле, должно оставаться в порядке чтобы использовать условия как d(s,x) если это меньше чем d(s,y), потому что у нас уже есть обработанный x в предыдущих итерациях. Но псевдокод выше используется d(s,y) дважды, и это не будет работать как хотелось бы.


Чтобы избавиться от второго использования d(s,y), в котором мы проверяем чтобы определить какое ребро использовать, мы можем пометить (потому что мы рассчитываем кратчайший путь), что d(s,x)+длина(x,y) должна быть меньше чем похожее выражение, так вместо проверки этого на равенство с d(s,y) мы можем прост найти минимум:


Только последнее использование d(s,y) в этом алгоритме для определения в каком порядке обрабатывать вершины. Алгоритм Дейкстры для кратчайшего пути делает это так же как и алгоритм Прима. Помните, что в алгоритме Прима, мы добавляем вершины и ребра к дереву, на каждом шагу выбирая кратчайшее возможное ребро чтобы добавить. Алгоритм Дейкстры делает тоже самое, только выбирая ребро чтобы добавить на каждом шагу для минимизации d(s,x)+длина(x,y).

Алгоритм 3: (Dijkstra, basic outline)


let T be a single vertex s

while (T has fewer than n vertices)

{

find edge (x,y)

with x in T and y not in T

minimizing d(s,x)+length(x,y)

add (x,y) to T

d(s,y)=d(s,x)+length(x,y)

}

Реальный кратчайшие пути могут быть найдены следуя пути в T из вершины s в вершину t. Это определяет структуру известную как «дерево кратчайшего пути». На практике может быть быстрее построить два дерева, одно из s, а другое из t, и остановиться когда они «забегут» друг в друга.

Алгоритм 4: (Дейкстра с кучами)


make a heap of values (vertex,edge,distance)

initially (v,-,infinity) for each vertex

let tree T be empty

while (T has fewer than n vertices)

{

let (v,e,d(v)) have the smallest weight in the heap

remove (v,e,d(v)) from the heap

add v and e to T

set distance(s,v) to d(v)

for each edge f=(v,u)

if u is not already in T

find value (u,g,d(u)) in heap

if d(v)+length(f) < d(g)

replace (u,g,d(g)) with (u,f,d(v)+length(f))

}

Как и алгоритм Прима, он имеет сложность O(m log n) если вы используете бинарные кучи, или O(m + n log n) если вы используете кучи Фибоначчи.
^

Дейкстра и негативные веса


Алгоритм Дейкстры не работает с ребрами, у которых веса имеют негативное значение. Для примера, рассмотрим следующий граф (предположим что все ребра направлены слева направо)


2

A-----B

\ /

3 \ / -2

C

Если начать обход их вершины А, алгоритм Дейкстры выберет ребро (A,x) минимизируя d(A,A)+длина(ребро), а именно (А,В). Будет установлено d(A,B)=2 и выберет другое ребро (y,C) минимизация d(A,y)+d(y,C); только выбор (A,C) и будет установлено d(A,C)=3. Но он никогда не найдет кратчайший путь из А в В, используя С, с общей длиной в 1.
^

Топологический порядок и кратчайший путь


Это важный класс графов, в которых кратчайшие пути могут быть рассчитаны быстрее, в линейном времени. Идея состоит в том чтобы вернуться к алгоритмам 1 и 2, которые требуют посетить вершины в некотором порядке. В таких алгоритмах мы определили порядок сортировки по расстоянию от вершины s, который, как мы видим, работает для положительных весов ребер, но не работает если имеются негативные веса. Здесь другая сортировка, которая всегда работает: определим топологический порядок направленного графа, в котором, всякий раз когда у нас было ребро из x в y, посещали x перед y. Если мы можем определить такую сортировку, тогда мы можем сделать что-то похожее на алгоритм 2, и быть уверенными, что предшественник вершины x будет обработан перед вершиной x.

Algorithm 5: (shortest paths from topological order)


for each vertex y in a topological ordering of G

choose edge (x,y) minimizing d(s,x)+length(x,y)

path(s,y) = path(s,x) + edge (x,y)

d(s,y) = d(s,x) + length(x,y)

Это занимает линейное время (с возможным исключением поиска порядка), и работает всегда когда имеет негативные длины ребер. Вы можете всегда использовать его чтобы найти самый длинный путь: просто проотрицайте длины путей всех ребер.
^

Топологический порядок и ациклические графы


Определите направленный ацикличный граф (чаще известный как DAG), который не содержит циклов (цикл это набор ребер формирующих цикл, и все указывают на одинаковый путь вокруг цикла)

Теорема: граф имеет топологический порядок тогда и только тогда когда является направленным ацикличным графом

Одно направление доказательства простое: предположим G не является DAG, итак он имеет цикл. В любой сортировке G, одна вершина цикла стала первой, но тогда одно из двух ребер цикла, в котором вершина указывает на неправильное направление для сортировки содержит цикл. В другом направлении, мы должны доказать, что каждый граф без топологического порядка содержит цикл. Мы должны доказать это через нахождение алгоритма для конструкции топологического порядка, если алгоритм всегда мы можем использовать эту информацию для нахождения цикла.

Алгоритм 6: (топологический порядок)


list L = empty

while (G is not empty)

find a vertex v with no incoming edges

delete v from G

add v to L

Если этот алгоритм завершиться, L является топологическим порядком, поскольку мы только добавляем вершину v когда все входящие ребра были удалены, в той точке мы знаем предыдущие уже в списке.

Мы можем сделать шаг назад всегда, но то только при конечном числе вершин в графе. Следовательно, мы должны окончательно пройти вершину, которую мы раньше видели u->w->v->u->t->s. В этом случае , u->w->v->u является направленным циклом. Эта процедура всегда находит направленный цикл всякий раз когда алгоритм 6 «ошибается», завершая доказательство теоремы, что граф имеет топологический порядок тогда и только тогда он является DAG. Между прочим это также доказывает что алгоритм 6 находит топологический порядок всякий раз когда он существует, и что мы можем использовать алгоритм 6 чтобы проверить является ли граф DAG. Используя алгоритм 6 вместе с обратными шагами процедура предлагает быстрый метод посика циклов в графе, которые не являются DAG.

Наконец, давайте проанализируем алгоритм топологической сортировки. Ключевой шаг (поиск вершины без входящих ребер) кажется требует сканирования графа целиком, но мы можем это ускорить с помощью действительно очень простой структуры данных: I[v] количество ребр входящих в v, и список К ребер без входящих ребер.

Алгоритм 7: (topological ordering, detailed implementation)


list K = empty

list L = empty

for each vertex v in G

let I[v] = number of incoming edges to v

if (I[v] = 0) add v to K

while (G is not empty)

remove a vertex v from K

for each outgoing edge (v,w)

decrement I[w]

if (I[w] = 0) add w to K

add v to L


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

Схожі:

Перевод: Зайцев А. А. Кратчайший путь iconХронотоп и перевод: взаимопомощь и помехи елена Ивановна Панченко
Все эти и другие особенности затрудняют перевод подобного текста на другой язык и, как следствие, его понимание иностранцами
Перевод: Зайцев А. А. Кратчайший путь iconМетодические рекомендации для проведения кураторских часов на тему: «Пришла пора подорожить народным языком»
Даль смысл и цель жизни своей… «Мы зашли в трущебу и надо выбраться из нее подобру поздорову и продолжить себе иной путь. Русской...
Перевод: Зайцев А. А. Кратчайший путь iconМетодические рекомендации для проведения кураторских часов на тему: «Пришла пора подорожить народным языком»
Даль смысл и цель жизни своей… «Мы зашли в трущебу и надо выбраться из нее подобру поздорову и продолжить себе иной путь. Русской...
Перевод: Зайцев А. А. Кратчайший путь iconГликолиз – специфический путь катаболизма глюкозы

Перевод: Зайцев А. А. Кратчайший путь iconПеревод Годовой доклад
move to 595-56339
Перевод: Зайцев А. А. Кратчайший путь iconПеревод Централизованное теплоснабжение в Мосс
move to 595-56340
Перевод: Зайцев А. А. Кратчайший путь iconПеревод чисел из десятичной системы счисления в двоичную Метод подбора

Перевод: Зайцев А. А. Кратчайший путь iconПеревод Энергоэффективность самая важная «высадка на Луну»
move to 595-56341
Перевод: Зайцев А. А. Кратчайший путь iconЗайцев С. В., к э. н., доц. Астраханский государственный технический университет Зайцева О. В
Инвестиционную привлекательность Астраханского региона определяет комплекс геополитических и природных ресурсов
Перевод: Зайцев А. А. Кратчайший путь iconКукес В., Сычев Д., Ших Е
Изучение биотрансформации лекарственных средств ― путь к повышению эффективности и безопасности фармакотерапии
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи