Головна

алгоритм Тарра

  1.  алгоритм
  2.  алгоритм Blowfish
  3.  алгоритм MD4
  4.  алгоритм WaveCluster
  5.  Алгоритм автоматичного вибору кроку
  6.  Алгоритм ШПФ з основою 2.
  7.  Алгоритм ШПФ з проріджуванням по частоті.

Алгоритм обходу для довільних зв'язкових графів був дан Тарра. Алгоритм заснований на наступних двох правилах.

1. Процес ніколи не передає маркер двічі по одному і тому ж каналу.

2. Не-ініціатор передає маркер своєму попереднику (Сусідові, від якого він вперше отримав маркер), тільки якщо неможлива передача по інших каналах, відповідно до правила 1.

У наступному тексті використовуються локальні змінні сайтів:

pre - сайт, що передує тому, який виконує поточний процес, тобто сайт, з якого прийшов маркер;

used [q] - ознака того, відправлений чи був маркер на сайт u.

var used [q]: boolean init false для всіх u I Out (this);

pre: site init udef ;

Для ініціатора (виконується один раз):

begin pre: = this; вибір u I Out (this);

used [u]: = true; out token to u;

End

Для кожного процесу при отриманні token від s:

begin ifpre = udef then pre: = s;

if "U I Out (this): used [u]

then return (OK)

else if$ U I Out (this): (u ? pre & Oused [u])

then begin вибір u I Out (this) \ {pre} з Oused [u];

used [u]: = true ; out token to u

End

else begin used [pre]: = true ;

out token to pre

End

End

Так як процес кожного сайту передає маркер через кожен канал не більше одного разу, то кожен процес отримує маркер через кожен канал не більше одного разу. Кожен раз, коли маркер захоплювати не-ініціатором u, Виходить, що процес u отримав маркер на один раз більше, ніж послав його. Звідси випливає, що кількість каналів, інцидентних u, Перевищує кількість каналів, використаних u, По крайней мере, на 1. Таким чином, u завершує процес, а передає маркер далі. Отже, завершення процесу проводиться в сайті-ініціатора.

Нижче показується, що коли алгоритм завершується, кожен процес передав маркер.

(1) Всі канали, інцідентние ініціатору, були пройдені один раз в обох напрямках. Ініціатором маркер був посланий по всіх каналах, інакше алгоритм не завершився б. Ініціатор отримав маркер рівно стільки ж раз, скільки відправив його; так як ініціатор отримував маркер кожен раз через інший канал, то маркер пересилався через кожен канал по одному разу.

(2) Для кожного відвідуваного процесу u всі канали, інцідентние u були пройдені один раз в кожному напрямку. Припустивши, що це не так, виберемо в якості u перший зустрівся процес, для якого це не виконується, і зауважимо, що з пункту (1) u не є ініціатором. з вибору u, Всі канали, інцідентние pre (u) Були пройдені один раз в обох напрямках, звідки випливає, що u переслав маркер своєму попереднику. отже, u використовував всі інцидентні канали, щоб переслати маркер; але, так як маркер в кінці залишається в ініціатора, u отримав маркер рівно стільки ж раз, скільки відправив його, тобто u отримав маркер по одному разу через кожен Інцидентне канал. Ми прийшли до протиріччя.

(3) Всі процеси були відвідані і кожен канал був пройдений по одному разу в обох напрямках. Якщо є невідвідані процеси, то існують сусіди u и s такі, що u було відвідано, а s не був. Це суперечить тому, що всі канали u були пройдені в обох напрямках. Отже, з пункту (2), всі процеси були відвідані і всі канали пройдені один раз в обох напрямках.

Кожне обчислення алгоритму Тарра визначає кістяк графа. У корені дерева знаходиться ініціатор, а кожний не-ініціатор u в кінці обчислення заніс свого попередника в дереві в змінну pre.





 Initial |  Алгоритм для структури - дерева |  алгоритм голосування |  Initial |  фазовий алгоритм |  Поширення інформації зі зворотним зв'язком |  Обчислення нижньої межі |  Лекція 13. Алгоритми обходу сайтів |  Алгоритм обходу тора |  алгоритм зміщення |

© um.co.ua - учбові матеріали та реферати