Введение в распределённые алгоритмы. Ж. Тель (2009) (не распознанно) (1185664), страница 33
Текст из файла (страница 33)
Как следует из результатов этого параграфа, при выборе маршрута можно не принимать в расчет источник и тем неменее построить оптимальный путь. Эти результаты не зависят от того, какомукритерию оптимальности путей отдается предпочтение, при условии, что соблюдается следующее допущение. (Напомним, что путь называется простым, есликаждая вершина встречается в нем не более одного раза, и путь является циклом,если первая его вершина совпадает с последней.)1. Стоимость отправления пакета по пути P не зависит от того, как этот путьиспользуется, и, в частности, от того, используются ли ребра пути P для продвижения других сообщений. В свете этого допущения стоимость использованияпути P становится функцией, зависящей только от самого пути; в связи с этимусловимся обозначать записью C(P) стоимость пути P.2.
При последовательном соединении двух путей образуется новый путь, стоимость которого равна сумме стоимостей двух исходных путей, т. е. для всех i =4.1. Маршрутизация на основе узлов-адресатов119= 0, . . . , k имеет место равенствоC(hu0 , u1 , . . . , uk i) = C(hu0 , .
. . , ui i) + C(hui , . . . , uk i).Таким образом, стоимость пустого пути hu0 i (ведущего из вершины u0 в вершинуu0) удовлетворяет условию C(hu0 i) = 0.3. В графе отсутствуют циклы отрицательной стоимости.(Этим допущениям удовлетворяют критерии стоимости минимального числа звеньев и кратчайшего пути.) Путь из вершины u в вершину v называется оптимальным, если не существует пути меньшей стоимости из u в v. Заметим, чтооптимальный путь может быть не единственным; могут существовать различныепути, имеющие одну и ту же (минимальную) стоимость.Лемма 4.1. Пусть u и v — вершины из множества V. Если в графе Gесть путь P из u в v, то имеется также и простой путь из u в v, которыйявляется при этом оптимальным.Д о к а з а т е л ь с т в о.
Так как существует конечное число простых путей,существует простой путь S0 наименьшей стоимости из вершины u в вершину v;здесь мы имеем в виду, что для каждого простого пути P 0 из u в v выполняется неравенство C(S0) 6 C(P0). Остается показать, что C(S0) является нижнейгранью стоимостей всех (не обязательно простых) путей.Пусть V = {v1 , . . . , vN }. Последовательно удаляя из пути P циклы, содержащие вершины v1 , v2 , и т. д., можно прийти к заключению о том, что для каждого пути P из u в v существует простой путь P 0 , для которого выполняетсянеравенство C(P0) 6 C(P).
Пусть P0 = P. Построим для каждого i = 1, . . . , Nпуть Pi следующим образом. Если вершина vi встречается в пути Pi−1 не более одного раза, то положим Pi = Pi−1 . В противном случае рассмотрим путьPi−1 = hu0 , . . . , uk i, и пусть uj1 — это первое вхождение, а uj2 — это последнеевхождение вершины vi в последовательность Pi−1 . Тогда положимPi = hu0 , . . . , uj1 (= uj2 ), uj2 +1 , . . . , uk i.Согласно построению последовательность вершин P i является путем из u в v,и при этом каждая из вершин {v1 , . . . , vi } встречается в ней не более чем одинраз. Следовательно, PN — это простой путь из вершины u в вершину v.
Путь P i−1состоит из пути 1) Pi и цикла Q = uj1 , . . . , uj2 , и поэтому C(Pi−1) = C(Pi) + C(Q).Так как циклы отрицательного веса отсутствуют, отсюда следует, что C(P i) 6 C(Pi−1).Поэтому верно неравенство C(PN) 6 C(P).Принимая во внимание особенность выбора пути S 0 , заключаем, что C(S0) 6 C(PN);отсюда следует неравенство C(S0) 6 C(P).Если в графе G есть циклы отрицательного веса, то оптимального пути может и не найтись; стоимость каждого пути можно улучшить, стоит только пройтилишний раз по циклу отрицательной стоимости. В приведенной ниже теореме1) Точнее говоря, путь Pi−1 образован в результате последовательного соединения трех путей — путиPi0−1 = hu0 , .
. . , uj1 i, цикла Q = huj1 , . . . , uj2 i и пути Pi00−1 = huj2 , . . . , uk i. При этом соединениепутей Pi0−1 и Pi00−1 как раз и образует путь Pi . — Прим. перев.120Гл. 4. Алгоритмы маршрутизации4.1. Маршрутизация на основе узлов-адресатовподразумевается, что граф G является связным (в случае несвязного графа теорема применяется к каждой его компоненте связности по отдельности).Теорема 4.2. Для каждой вершины d ∈ V существует такое дерево Td == (V, Ed), Ed ⊆ E, в котором для любой вершины v ∈ V единственный путьиз v в d в дереве Td является оптимальным путем из v в d в графе G.Д о к а з а т е л ь с т в о.
Пусть V = {v1 , . . . , vN }. Мы построим индуктивноряд деревьев Ti = (Vi , Ei) (для i = 0, . . . , N), обладающих следующими свойствами.1. Каждое дерево Ti является подграфом графа G, т. е. Vi ⊆ V, Ei ⊆ E.2. Каждое дерево Ti (для i < N) является поддеревом дерева Ti+1 .3. Для каждого i > 0 выполняются включения vi ∈ Vi и d ∈ Vi .4. Для каждой вершины w ∈ Vi простой путь из вершины w в вершину dв дереве Ti является оптимальным путем из w в d в графе G.Эти свойства гарантируют, что дерево TN удовлетворяет тем требованиям, которые предъявляются к дереву Td .Чтобы построить последовательность деревьев, положим V 0 = {d} и E0 = ∅.Дерево Ti+1 строится следующим образом.
Выбирается оптимальный простойпуть P = hu0 , . . . , uk i из vi+1 в d; обозначим символом l такой наименьшийиндекс, для которого выполняется включение u l ∈ Ti (такой индекс l существует,поскольку uk = d ∈ Ti , при этом возможно l = 0). ПоложимVi+1 = Vi ∪ {uj : j < l} и Ei+1 = Ei ∪ { (uj , uj+1) : j < l}.(Эта конструкция изображена на Рис. 4.1.) Нетрудно убедиться в том, что T iявляется поддеревом графа Ti+1 и vi+1 ∈ Vi+1 . Граф Ti+1 является деревом, поскольку по построению Ti+1 является связным графом, и число вершин в немпревосходит число ребер в точности на единицу. (Граф T 0 обладает последним изупомянутых свойств, и на каждом этапе к графу добавляется столько же вершин,сколько и ребер.)vvvvi+1vvvH.v. H.
.H. . . . .v.HHv .... A .v..A ....A.v.v`AA..vd ` ```ul`!v!!v!!!Ti. . . .PTi+1Рис. 4.1. Построение дерева Ti+1 .Остается показать, что для всех вершин w ∈ Vi+1 единственный путь из wв d в дереве Ti+1 является оптимальным путем из w в d в графе G. Для вершин w ∈ Vi ⊂ Vi+1 это верно, ввиду того что Ti является поддеревом дерева Ti+1 ,121и поэтому путь из w в d в дереве Ti+1 тот же самый, что и путь в дереве Ti ,который по индуктивному предположению является оптимальным. Теперь рассмотрим вершину w = uj , j < l, принадлежащую множеству Vi+1 \ Vi .
Обозначимсимволом Q путь из вершины ul в вершину d в дереве Ti . Тогда в дереве Ti+1из вершины uj в вершину d ведет путь, полученный в результате последовательного соединения пути huj , . . . , ul i и пути Q. Остается показать, что этот путьявляется оптимальным в графе G. Прежде всего заметим, что суффикс P 0 == hul , . . . , uk i пути P сам по себе является оптимальным путем из вершины u lв вершину d, и поэтому C(P0) = C(Q). Это следует из того, что оптимальностьпути Q предполагает неравенство C(P 0) > C(Q), а в случае C(Q) < C(P0) мыполучаем (учитывая свойство аддитивности стоимости путей), что, присоединивк пути hu0 , . .
. , ul i путь Q, мы можем построить путь, имеющий меньшую стоимость, чем путь P, вопреки оптимальности пути P. Предположим теперь, чтонекоторый путь R из uj в d имеет меньшую стоимость, нежели путь, полученный присоединением к пути huj , . . . , ul i пути Q. Тогда, воспользовавшись ранеесделанным замечанием, мы можем прийти к заключению, что стоимость пути Rменьше, чем стоимость суффикса huj , . . .
, uk i пути P, а это означает (с учетомаддитивности стоимости путей), что путь, образованный присоединением к путиhu0 , . . . , uj i пути R, имеет меньшую стоимость, чем P, вопреки оптимальностипути P.Остовное дерево, корнем которого служит вершина d, называется входнымдеревом для d, а дерево, обладающее теми свойствами, которые указаны в теореме 4.2 называется оптимальным входным деревом. Существование оптимального входного дерева означает, что алгоритмы маршрутизации, в основу которыхположен механизм продвижения, описанный в алгоритме 4.2, не поступаютсяоптимальностью. В этом алгоритме ведущую роль играет локальная процедураtable_lookupu , имеющая один аргумент и выбирающая одного из соседей вершины u (после обращения к таблице маршрутизации).
Действительно, ввиду тогочто все пакеты, адресованные узлу d, можно оптимально направить по остовномудереву, корнем которого служит вершина d, продвижение пакета будет оптимальным, если для каждой вершины u 6= d процедура table_lookup u (d) будет выдавать в качестве значения родительскую вершину узла u в остовном дереве T d .Если механизм продвижения пакетов устроен именно так и топология сети непретерпевает (дальнейших) изменений, для доказательства корректности таблицмаршрутизации можно воспользоваться следующим результатом. Будем говорить, что таблицы маршрутизации (для узла-адресата d) содержат цикл, еслисуществуют такие вершины u1 , .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
