А В Стёпкин - Алгоритм распознавания графов тремя агентами - страница 2

Страницы:
1  2  3  4 

10. if K Ф 0 then go to 2 данной процедуры;

11. else Агент A выполняет процедуру ОВН_А(у);

12. if Z Ф 1 then do

13. ifв O(v) есть ребро, у которого (/u(Zy,u),v) = r)and(ju(y,u)= b)and(^i^,u\u) = r)then do

14. Агент A выполняет процедуру ВПЕРЕД_уШ_М^);

15. go to 13 данной процедуры;

16. end do;

17. else if в O(v) есть ребро, у которого (/(v,u) = r)and(/Li(u) = r)and(u((v,u),u) = r) then do

18. Агент A выполняет процедуру ВПЕРЕД_ AR(v);

19. go to 17 данной процедуры;

20. end do;

21. else go to 2 алгоритма обхода;

22. end do;

23. else go to 17 данной процедуры;

24. end do;

При выполнении процедуры НАЗАД_A(v), агент A выбирает из окрестности O(v) ребро, для ко­торого выполняется условие (K(v,u) = r)md(/u((v,u),v) = r)and(/u(v) = r), и переходит по нему в вер­шину u . При этом, производит окрашивание /и(у):= b,(v,u):= b,((v,u),v):= b , выполняет присвоение

v := u и записывает в список M сообщение: НАЗАД_А;

РАСП_А(у):

1. Агент A выбирает из окрестности O(v) ребро (v,u) , у которого ((/(v)=u(u)=r)and(и(v,u)=w)) и переходит по нему в вершину u ;

2. Агент A красит u(v,u) = b ;

3. Агент A записывает в список M сообщение: ОВРАТНОЕ_РЕВРО_А;

4. while в O(u) существует ребро (u,l) у которого (u(u,l) = r) and(/u/(u,l),l) = r)and(ju(l) = r) do

5. Агент A переходит по ребру (u, l) в вершину l;

6. u := l ;

7. Агент A записывает в список M сообщение: ОТСТУПИЛ А;

8. end do;

9.   Агент A записывает в списокМсообщение: РЕВРО РАСПОЗНАНО_А;

Выполняя процедуру РАСПАВВ(у), агент A выбирает из окрестности O(v) ребро (v, u), для ко­торого выполняется условие u(v,u) = y и переходит по нему в вершину u, производя окрашивание u(v,u):= r, и(у,u),u):= b . Выполняет присвоение v := u и записывает в список M сообщение: ВПЕ­РЕД jABB. После чего агент A выбирает из окрестности O(v) ребро, для которого выполняется условие

u) = rr)and(u((v, u), v) = b)), и переходит по нему в вершину u, окрашивая u((v,u),v):= r, u(v,u):= b,u((v,u),u):= r , выполняет присвоение v := u и записывает в список M со­общение: НAЗAД_ABB.

Процедура РАСП_АВВЪ(у) аналогична процедуре РАСП_АВВ(у), с отличием лишь в том, что вы­полняя возврат по перешейку в свою область, агент A окрашивает ребро и дальний инцидентор сле­дующим образом и (v,u) := b, ((v, u), u) := b .

При выполнении процедуры ВПЕРЕД_AR_N(v), агент A выбирает из окрестности O(v) ребро, удовлетворяющее условию ((v,u),v) = r~)and(/(v,u) = b)and(u((v,u),u) = r), переходит по нему в вер­шину u, производя окрашивание u),v):= b, /u((v,u),u):= b . После чего выполняет присвоение v := u и записывает в список M сообщение: ВПЕРЕД_AR_N.

Выполняя процедуру СТОП_А(у), агент A окрашивает /и(у):= b и завершает работу.

Алгоритм работы агента B :

Вход: граф G неизвестный АИ и АЭ, все элементы графа G окрашены краской w, агент B по­мещен в произвольную вершину s .

Выход: все элементы графа G, которые попадут в область работы агента B, окрашены краской b , агент B находится в исходной вершине s ; пошагово выданы команды АЭ. Данные: s - рабочая вершина графа G, в которой находится агент.

Алгоритм:

1. Агент B красит (/j(s):= y);

2. Запрос BN;

3. if BN ф 1 then do

4. Запрос AN;

5. if /(s) = ry then do

6. Агент B выполняет процедуру ВOЗВРAТ_B(s);

7. Агент B выполняет процедуру МЕТИМПЕР_B(s);

8. end do;

9. else if AN = 0 then МЕТИМ ПЕР_B(s);

10. else ВЫБОР_ХОДА_B(s);

11. end do;

12. else РAСП_ПЕР_B{s)■;

Все процедуры агента B, которые не рассмотрены ниже, аналогичны процедурам агента A . Выполняя процедуру МЕТИМ_ПЕР_B(s), агент B проверяет наличие в окрестности O(s) ребра

(s,z), для которого выполняется условие (u(s,z)= w)and((u(z)= r)or(u(z)= ry)) (1).

Если такое ребро обнаружено и в вершине z находится агент A, то агент B выполняет процеду­ру СТОИТ_ B(z) и возвращается в строку 7 АО. Если же в вершине z нет агента A, то агент B выпол­няет процедуру МЕТИМ_ BA(z) и возвращается в начало данной процедуры.

Если в окрестности O s) не обнаружено ребра, удовлетворяющего условию (1), то агент B за­прашивает значение переменной L. При этом: если L = 0, то агент B выполняет процедуру ВЫ-ВОРАСОДАДК^), иначе агент B выполняет процедуру ФИКСА(2) и возвращается в строку 2 АО.

ВЫБОР_ХОДА _B(s):

: u(s) = y) then do

■- w) then do

1. if в O(s) обнаружено ребро, у которого (/(s, z) = w)and (/(z) ~-

2. Агент B выполняет процедуру РAСП_B(s);

3. go to 2 алгоритма обхода;

4. end do;

5. else if в O(s) обнаружено ребро, у которого (p(s, z) = w)and(/(z) :

6. Агент B выполняет процедуру ВПЕРЕД_B(s);

7. go to 2 алгоритма обхода;

8. end do;

9. else if в O(s) есть ребро, у которого ((/(s, z) = w)and((/(z) = r)or(u(z) = ry))) then do

10. Агент B выполняет процедуру СТОИТ_B(s);

11. go to 2 алгоритма обхода;

12. end do;

13. else if в O(s) есть ребро, у которого (u(s, z) = r) then do

14. Агент B выполняет процедуру СТОИТ_B(s);

15. go to 2 алгоритма обхода;

16. end do;

17. else if в O(s) есть ребро, у которого ((/(s, z) = y)and((/(z) = r)or(/u(z) = ry))) then do

18. Агент B выполняет процедуру СТОИТ_B(s);

19. go to 4 алгоритма обхода;

20. end do;

21. else ifв O(s) есть ребро, у которого /s, z)= y)and(u{s)= y^and^/^, z), s) = y) then do

22. Агент B выполняет процедуру НAЗAД_B(s)■;

23. go to 2 алгоритма обхода;

24. end do;

25. else агент B выполняет процедуру СТОПІЗ;

Выполняя процедуру МЕТИМ_BA(s), агент B выбирает из окрестности O(s) произвольное ребро (s, z), для которого выполняется условие ((и (s, z) = w)and((и (z) = r)or (z) = ry))), переходит по нему в вершину z, окрашивая u(s, z) := y, и ((s, z), z):= y, выполняет присвоение s := z и записывает в список N сообщение: ВПЕРЕД_BA. Далее агент B выбирает из окрестности O(s) ребро (s, z), удовлетво­ряющее условию (/(s^)= y)and(((s) = r)or(/и(s) = ry))), переходит по нему в вершину z , выполняет присвоение s := z и записывает в список N сообщение: НАЗАД_BA.

Страницы:
1  2  3  4 


Похожие статьи

А В Стёпкин - Алгоритм распознавания графов тремя агентами

А В Стёпкин - Распознавание конечного графа коллективом агентов