Институт прикладной математики и механики Национальной академии наук Украины, Донецк, Украина

А.В. Степкин

Алгоритм распознавания конечных графов тремя агентами

Аннотация

В работе рассматривается задача распознавания конечных графов тремя агента­ми. Два агента-исследователя передвигаются по графу, считывают и изменяют метки элементов графа, передают информацию агенту-экспериментатору, который и строит представление исследуемого графа. Предложен алгоритм квадратических (от числа вер­шин графа) временной и емкостной сложностей, который распознает любой конечный неориентированный граф. Для распознавания графа каждому агенту требуется по 2 кра­ски (всего 3 краски). Метод основан на методе обхода графа в глубину.

Введение

В настоящее время одной из центральных проблем математической кибернетики яв­ляется проблема взаимодействия управляющей и управляемой систем. Взаимодействие таких систем зачастую представляется как процесс перемещения агента по помечен­ному графу. Один из подходов к решению этой проблемы рассмотрен в [1], в пред­положении, что интересующее нас взаимодействие представлено передвижением одно­го агента-исследователя (АИ) по неизвестному графу и обменом данными с агентом-экспериментатором (АЭ), который и производит восстановление графа по данным, по­лученным от АИ.

Постановка задачи

Работа посвящена исследованию проблемы, в предположении, что взаимодействие управляющей и управляемой систем представляется процессом перемещения двух АИ d и  по неизвестному конечному графу (АИ могут окрашивать вершины, ребра и инциден-торы графа, воспринимать эти отметки и на их основании осуществлять перемещение), и обменом данными с АЭ (восстанавливает граф, по данным полученным от АИ, а та­кже передает АИ информацию, необходимую для их дальнейшего функционирования). В работе рассмотрен алгоритм построения маршрутов АИ, позволяющих АЭ точно вос­становить граф. Для этого у каждого АИ есть две краски: у f это f и f, у f – f и f. В отличие от [2] оптимизированы процедуры распознавания обратных ребер и перешейков, что позволило улучшить временную сложность алгоритма до f (f2), где f – число вершин графа. Полученный алгоритм использует результаты и обозначения из [2], [3].

Алгоритмы обхода и восстановления.

1. АИ красит вершину f, в которой находится f(f1) := f;

2. запрос AN;

3. if р= 1 then do запрос BN;

5. else ВЫБОР_ХОДА_А(); end do;

6. else РАСП_ПЕР_А(f); РАСП_ПЕР_А(f):

1. if в а (п) не обнаружено ребра, у которого р(р,р) = р then do

2. if в f (f) есть ребро, у которого а n do 3. агент f выполняет процедуру ОТСТУП_А(f);

4.go to 1 данной процедуры; end do; else do

5.агент f выполняет процедуру НАЗАД_А(f);

6.go to 1 данной процедуры; end do; end do; else do

7.запрос ;

8.if then РАСП_АВВ(f); else РАСП_АВВb(f);

9. запрос ;

10. if р= 0 then go to 1 данной процедуры; else do

11.агент f выполняет процедуру ОБН_А(f);

12.if в f (f) есть ребро, у которого р then do

13.агент f выполняет процедуру ВПЕРЕД_AR_N(f);

14.go to 12 данной процедуры; end do;

15.if в f (f) есть ребро, у которого р then do

16.агент f выполняет процедуру ВПЕРЕД_ AR(f);

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

18. else go to 2 алгоритма обхода; end do; end do. РАСП_А(f):

1. Агент записывает в список f: ОБРАТНОЕ_РЕБРО_А;

2. while в е (е) есть ребро (е,е), т.ч. а do

3. агент а красит ;

4. агент р записывает в р: МЕТКА_OР_А; end do;

5. агент а выбирает из в (p) ребро, у которого и переходит по нему в вершину ;

6. а :=р;

7. агент р записывает в р: ОТСТУПИЛ_А;

8. if в с (с) нет ребра, у которого с then go to 5 данной процедуры; else do

9. запрос а;

10. if а = 0 then go to 1 данной процедуры; else do

11. агент n выполняет процедуру ОБН_А(a);

12. if в n (a) есть ребро, у которого then do

13. агент a выполняет процедуру ВПЕРЕД_AR_N(v);

14. go to 12 данной процедуры; end do;

15. if в b (b) есть ребро, у которого then do

16. агент a выполняет процедуру ВПЕРЕД_ AR(b);

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

18. else go to 2 алгоритма обхода; end do; end do. РАСП_А(a):

1. Агент v записывает в список v: ОБРАТНОЕ_РЕБРО_А;

2. while в jh (v) есть ребро (e,v), т.ч. a do

3. агент a красит s;

4. агент a записывает в d: МЕТКА_OР_А; end do;

5. агент f выбирает из d (g) ребро, у которого f и переходит по нему в вершину j;

6. h :=d;

7. агент a записывает в d: ОТСТУПИЛ_А;

8. if в a (a) нет ребра, у которого then go to 5 данной процедуры; else do

9. агент j переходит по ребру ,g красит ;

10. k:=f

11. агент f записывает в список h: ВПЕРЕД_OР_А; end do;

12. запрос k;

13. if d then do

14. агент s выбирает из s ребро g,s, у которого f;

15. агент h красит g;

16. агент j записывает в y: РЕБРА_РАСПОЗНАНЫ_А;end do;else do

17. агент j выбирает из g ребро, у которого y и переходит по нему в f;

18. агент o красит i;

19. f=f;

20. агент h записывает в список r: НАЗАД_ОР_А;

21. агент a выполняет go to 5 данной процедуры; end do.

Неописанные процедуры агента a, представлены в [3].

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

1. АИ красит вершинуf, в которой находится s;

2. запрос BN;

3. if s = 1 then do запрос AN;

4. if s then do

5. агент В выполняет процедуру B03BPAT_5(s);

6. агент В выполняет процедуру МЕТИМ_77ЕР_В'(s); end do;

7. else if AN=0 then METHM_IIEP_B(s);

8. else ВЫБОР_XOflA_B(s)\ end do;

9. else PACn_nEP_B(s).

Выполняя ВОЗВРАТ_B{s), агент В выбирает из О (s) ребро, у которого (fi (s, z) = у) and (fi ((s, z) , s) = у) и переходит по нему в z, выполняет s:=z и записывает в N: ВОЗВРАТ_В. Процедуры PACTI_B(s) и PACn_TIEP_B(s) агента В аналогичны процедурам РАСП_А(у) и РАСП_ПЕР_А(у) (с учетом того, что “чужой” вершиной пе­решейка может быть красно-желтая вершина) агента А. Неописанные процедуры агента В, представлены в [3].

Алгоритм “Восстановление”, и процедуры, не рассмотренные ниже, приведены в [3]. ОБР_СП_А():

1. if Ме5=”ВПЕРЕД_А” then ВПЕРЕД_А();

2. if Ме5=”ВПЕРЕД_АВ” then ВПЕРЕД_АВ();

3. if Ме5=”ВПЕРЕД_АВВ" then ВПЕРЕД_АВВ();

4. if Ме5=”НАЗАД_А” then НАЗАД_А();

5. if Ме5=”НАЗАД_АВ" then НАЗАД_АВ();

6. if Ме5=”НАЗАД_АВВ” then НАЗАД_АВВ();

7. if Mes="OHKC_A" then ФИКС_А();

8. if Mes="OBH_A" then ОБН_А();

9. г/Ме5=”ОТСТУПИЛ_А” then ОТСТУПИЛ_А();

10. г/Mes="PEBPA_PACiI03HAHbI_A" then РЕБРА_РАСПОЗНАНЫ_А();

11. г/Mes="OTCTyn_A" then ОТСТУП_А();

12. г/Mes="OBPATHOE_PEBPO_A" then ОБРАТНОЕ_РЕБРО_А();

13. г/Mes="METKA_OP_A" then METKA_OP_A();

14. г/Ме5=”ВПЕРЕД_ОР_А” then ВПЕРЕД_ОР_А().

ОТСТУП_А(): г := г + 1.

ВПЕРЕД_АВВ(): Ец '¦= Ец U {N _B, r (t – г)}.

ОТСТУПИЛ_А(): г := г + 1.

РЕБРА_РАСПОЗНАНЫ_А(): г := 0.

ОБРАТНОЕ_РЕБРО_А(): KOBR_A := 0. МЕТКА_

ОР_А(): KOBR_A := KOBR_A + 1. ВПЕРЕД_ОР_А():

KOBR_A := KOBR_A – 1;

UDOBR_A := (KOBR_A = 0); f# := -Е-я U {r (f) , r (t – г)}.

ФИКС_А(): N_A :=Сч_А; BN := 1; E := 0] Q := F;

UDP_A := (((F = Q) or (F = 1)) and (Q 7^ 1)). НАЗАД_АВВ(): К := К — 1; UDP_B:= (((К = Z) or (К = 1)) and (Z 7^ 1)).

Процедура ОБР_СП_В() аналогична процедуре ОБР_СП_А(), только добавлено условие: if Mes="B03BPAT_B" then B03BPAT_B().

ВОЗВРАТ_В(): L := 1; Сч_В :=Сч_В – 2;

Процедуры работы со списком команд от агента 5, которые не рассмотрены выше, аналогичны процедурам работы со списком команд от агента А.

Теорема 1. Выполняя алгоритм распознавания, агенты распознают любой конечный граф G с точностью до изоморфизма.

Теорема 2. Временная и емкостная сложности алгоритма равны О (n2), где n – число вершин графа, при этом алгоритм использует 3 краски.

Выводы

В работе предложен алгоритм распознавания графа среды временной и емкостной сложностей h (f2). АИ имеют конечную память, независимую от a, и используют по две краски каждый (всего три краски).

Список литературы

1. Грунский И. С., Татаринов Е. А. Распознавание конечного графа блуждающим по нему агентом. Вестник Донецкого университета. Серия А. Естественные науки –, 2009, вып. 1. – с. 492–497.

2. Грунский И.С., Стёпкин А.В. Распознавание конечного графа коллективом агентов. – Труды ИПММ НАН Украины. – 2009. – Т.19. – С. 43-52.

3. Стёпкин А.В. Распознавание графов коллективом агентов. // Мат. IV мiжнар. наук.-практ. конф. "Сучасна iнформацiйна Україна: iнформатика, економiка, фiло-софiя"2010, Донецьк, – т.1 – с. 139–143.

Андрей Викторович Стёпкин — соискатель ученой степени 1-го года обучения, Институт прикладной математики и механики Национальной академии наук Украины, Донецк, Украина.