Главная Случайная страница


Полезное:

Как сделать разговор полезным и приятным Как сделать объемную звезду своими руками Как сделать то, что делать не хочется? Как сделать погремушку Как сделать так чтобы женщины сами знакомились с вами Как сделать идею коммерческой Как сделать хорошую растяжку ног? Как сделать наш разум здоровым? Как сделать, чтобы люди обманывали меньше Вопрос 4. Как сделать так, чтобы вас уважали и ценили? Как сделать лучше себе и другим людям Как сделать свидание интересным?


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






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





Алгоритм обхода для произвольных связных графов был дан Тарри. Алгоритм основан на следующих двух правилах.

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

2. Не-инициатор передает маркер своему предшественнику (соседу, от которого он впервые получил маркер), только если невозможна передача по другим каналам, в соответствии с правилом 1.

 

В следующем тексте используются локальные переменные сайтов:

pre – сайт, предшествующий тому, который выполняет текущий процесс, т.е. сайт, с которого пришел маркер;

used[q] – признак того, отправлен ли был маркер на сайт u.

 

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

pre: site init udef;

 

Для инициатора (выполняется один раз):

begin pre:= this; выбор u Î Out(this);

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

End

 

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

begin if pre = udef then pre:= s;

if " u Î Out(this): used[u]

then return(OK)

else if $ u Î Out(this): (u ¹ pre & Øused[u])

then begin выбор u Î Out(this) \ {pre} с Øused[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.


Date: 2015-09-18; view: 620; Нарушение авторских прав; Помощь в написании работы --> СЮДА...



mydocx.ru - 2015-2024 year. (0.006 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию