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

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

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2011
Автор:	Стёпкин, А.В.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут проблем штучного інтелекту МОН України та НАН України 2011
Назва видання:	Штучний інтелект
Теми:	Системы и методы искусственного интеллекта
Онлайн доступ:	http://dspace.nbuv.gov.ua/handle/123456789/58846
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Распознавание конечных графов тремя агентами / А.В. Стёпкин // Штучний інтелект. — 2011. — № 2. — С. 84-93. — Бібліогр.: 8 назв. — рос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-58846
record_format	dspace
spelling	irk-123456789-588462014-04-01T03:01:34Z Распознавание конечных графов тремя агентами Стёпкин, А.В. Системы и методы искусственного интеллекта В статье рассматривается проблема распознавания конечных графов тремя агентами. Два агента-исследователя передвигаются по графу, считывают, анализируют и изменяют метки элементов графа, передают информацию о своих передвижениях агенту-экспериментатору, который и распознает исследуемый граф. Предложен алгоритм временной сложности О(n³) и емкостной – О(n²), который распознает любой конечный неориентированный граф. При распознавании каждый агент использует две различные краски (всего три краски). Метод основан на методе обхода графа в глубину. У статті розглядається проблема розпізнавання скінченних графів трьома агентами. Два агенти-дослідники рухаються графом, зчитують, аналізують та змінюють помітки елементів графа, передають інформацію про свої переміщення агенту-експериментатору, який розпізнає досліджуваний граф. Запропоновано алгоритм часової складності О(n³) та ємнісної – О(n²), який розпізнає будь-який скінченний неорієнтований граф. Для розпізнавання кожному агенту необхідно дві різні фарби (усього три фарби). Метод базується на методі обходу графа в глибину. The Problem of finite graphs exploration by three agents is considered in this work. Two agents-researchers move on graph, they read, analyze and change marks of graph elements, transfer the information about their movements and colorings to the agent-experimenter. It builds explored graph representation. The algorithm with О(n³) time (n is amount of nodes of graph) and О(n²) space complexities is proposed. It recognizes any finite non-oriented graph. For graph exploration each agent needs two different marks (three colors in total). The method is based on the depth-first traversal method. 2011 Article Распознавание конечных графов тремя агентами / А.В. Стёпкин // Штучний інтелект. — 2011. — № 2. — С. 84-93. — Бібліогр.: 8 назв. — рос. 1561-5359 http://dspace.nbuv.gov.ua/handle/123456789/58846 519.7 ru Штучний інтелект Інститут проблем штучного інтелекту МОН України та НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Системы и методы искусственного интеллекта Системы и методы искусственного интеллекта
spellingShingle	Системы и методы искусственного интеллекта Системы и методы искусственного интеллекта Стёпкин, А.В. Распознавание конечных графов тремя агентами Штучний інтелект
description	В статье рассматривается проблема распознавания конечных графов тремя агентами. Два агента-исследователя передвигаются по графу, считывают, анализируют и изменяют метки элементов графа, передают информацию о своих передвижениях агенту-экспериментатору, который и распознает исследуемый граф. Предложен алгоритм временной сложности О(n³) и емкостной – О(n²), который распознает любой конечный неориентированный граф. При распознавании каждый агент использует две различные краски (всего три краски). Метод основан на методе обхода графа в глубину.
format	Article
author	Стёпкин, А.В.
author_facet	Стёпкин, А.В.
author_sort	Стёпкин, А.В.
title	Распознавание конечных графов тремя агентами
title_short	Распознавание конечных графов тремя агентами
title_full	Распознавание конечных графов тремя агентами
title_fullStr	Распознавание конечных графов тремя агентами
title_full_unstemmed	Распознавание конечных графов тремя агентами
title_sort	распознавание конечных графов тремя агентами
publisher	Інститут проблем штучного інтелекту МОН України та НАН України
publishDate	2011
topic_facet	Системы и методы искусственного интеллекта
url	http://dspace.nbuv.gov.ua/handle/123456789/58846
citation_txt	Распознавание конечных графов тремя агентами / А.В. Стёпкин // Штучний інтелект. — 2011. — № 2. — С. 84-93. — Бібліогр.: 8 назв. — рос.
series	Штучний інтелект
work_keys_str_mv	AT stëpkinav raspoznavaniekonečnyhgrafovtremâagentami
first_indexed	2025-07-05T10:04:07Z
last_indexed	2025-07-05T10:04:07Z
_version_	1836800905358344192
fulltext	«Искусственный интеллект» 2’2011 84 1С УДК 519.7 А.В. Стёпкин Славянский государственный педагогический университет, Украина stepkin.andrey@rambler.ru Распознавание конечных графов тремя агентами В статье рассматривается проблема распознавания конечных графов тремя агентами. Два агента-исследо- вателя передвигаются по графу, считывают, анализируют и изменяют метки элементов графа, передают информацию о своих передвижениях агенту-экспериментатору, который и распознает исследуемый граф. Предложен алгоритм временной сложности  3nO и емкостной –  2nO , который распознает любой конечный неориентированный граф. При распознавании каждый агент использует две различные краски (всего три краски). Метод основан на методе обхода графа в глубину. Введение Проблема распознавания среды широко рассматривается в литературе в различных контекстах [1]. Например, в [2] данная проблема решается с помощью двух агентов. Один агент-исследователь передвигается по неизвестному графу, считывает, анализирует и из- меняет метки на элементах графа, а также обменивается данными с агентом-экспериме- нтатором, который, используя полученную информацию, и восстанавливает исследуемый граф. Данная статья посвящена исследованию возможности и сложности решения нашей проблемы с помощью трёх одновременно работающих агентов. Два агента-исследователя (АИ) A и B одновременно передвигаются по неизвестной среде, заданной конечным графом [3], и обмениваются данными с агентом-экспериментатором (АЭ), который и производит восстановление графа, используя информацию, полученную от АИ, а также передает АИ данные, необходимые для их дальнейшей работы. Целью данной работы является создание алгоритма одновременной работы трёх агентов, в котором два АИ, будучи размещены в произвольных, несовпадающих верши- нах рассматриваемого графа G , окрашенных цветом w , через конечное число шагов обойдут этот граф, пошагово обмениваясь необходимыми данными с АЭ. Агент-экспе- риментатор, в свою очередь, восстановит граф ,H изоморфный G , то есть распознает граф G , используя данные, полученные от АИ. Стратегия решения задачи В работе рассматриваются конечные, неориентированные графы без петель и крат- ных ребер. Все неопределяемые понятия общеизвестны, с ними можно ознакомиться, например, в [4-7]. Работа алгоритма, рассматриваемого в данной статье, основана на методе поиска в глубину. Принцип работы этого метода можно описать следующим образом: агенты идут «в глубину», пока это возможно, возвращаются назад, ищут другой путь с еще не посещенными вершинами и не пройденными ребрами. В случае обнаружения смежной Распознавание конечных графов тремя агентами «Штучний інтелект» 2’2011 85 1С вершины окрашенной в «чужой» цвет, агент метит все перешейки из текущей вершины в «чужую» область и сообщает второму АИ, через АЭ, о необходимости распознавания помеченных перешейков. Пока второй АИ выполняет процедуру распознавания пере- шейков, первый АИ не может метить новые перешейки. В случае отсутствия других воз- можных вариантов перемещения, кроме как пометить новый перешеек, первый АИ оста- навливается до того момента, пока второй АИ не распознает все помеченные перешейки. Выполняя обход графа, агенты-исследователи A и B образуют соответственно красный и желтый пути. Принцип построения пути каждым из агентов можно описать следующим образом: – при движении в новую вершину красный (желтый) путь удлиняется, при движе- нии назад по «своему» пути – укорачивается; – при движении назад для распознавания обратного ребра или перешейков длина пути не изменяется; – вершина, из которой возможен лишь возврат по «своему» пути, либо вовсе от- сутствуют варианты перемещения, окрашивается в черный цвет. Алгоритм заканчивает работу, когда красный и желтый пути становятся пустыми, а все вершины черными. При обходе графа G , агентами создается неявная нумерация посещенных вер- шин: при первом посещении вершины она окрашивается агентом A в красный цвет (в желтый цвет в случае агента B ), и ей фактически ставится в соответствие номер, равный значению переменной АСч _ ( BСч _ для агента B ). Обратим внимание, что АСч _ и BСч _ принимают соответственно нечетные и четные значения. На основе нумерации и происходит восстановление графа G путем построения графа ,H изоморфного G . В работе АИ можно выделить 5 режимов функционирования: 1. Работая в обычном режиме, АИ продвигается вперед по белым вершинам, окрашивая эти вершины, соединяющие их ребра и дальние инциденторы в «свой» цвет. При отсутствии возможных путей перемещения АИ возвращается назад, окрашивая пройденные вершины, соединяющие их ребра и ближние инциденторы в черный цвет. АИ завершает работу тогда, когда его исходная вершина, вследствие отсутствия воз- можных путей перемещения, окрашивается в черный цвет. 2. Если при работе в обычном режиме было обнаружено обратное ребро, то АИ прекращает работу в этом режиме и переключается в режим распознавания обратных ребер. АИ переходит по обратному ребру, окрашивая его в черный цвет, и по «своему» пути возвращается в вершину, в которой был изменен режим работы АИ. Достигнув этой вершины, агент переключается в обычный режим работы. 3. Если при работе в обычном режиме АИ обнаружил перешеек, то при условии, что все ранее помеченные данным агентом перешейки были распознаны, АИ пере- ключается в режим пометки перешейков. В этом режиме АИ переходит по перешейку в «чужую» область, окрашивая ребро и дальний инцидентор в «свой» цвет. Далее АИ возвращается по этому перешейку, ничего не окрашивая, и ищет другие перешейки из этой вершины. Пометив все перешейки из данной вершины в «чужую» область, АИ сообщает об этом АЭ, который в свою очередь дает команду второму АИ о необхо- димости распознавания помеченных перешейков. По завершению режима пометки перешейков АЭ содержит информацию о количестве помеченных перешейков. 4. Получив от АЭ команду о необходимости распознавания перешейков, АИ за- вершает работу в обычном режиме и переключается в режим распознавания пере- шейков. Если в этот момент агент работает в режиме распознавания обратных ребер, то Степкин А.В. «Искусственный интеллект» 2’2011 86 1С переключение в режим распознавания перешейков будет совершено по завершении работы агента в текущем режиме. В режиме распознавания перешейков АИ возвращается назад по «своему» пути до обнаружения ближайшей вершины, инцидентной помеченному перешей- ку. Под помеченным перешейком понимается ребро, у которого ближний инцидентор, ребро и дальняя вершина этого ребра окрашены в «чужой» цвет. Далее возможны два случая: 4.1. Помечен один перешеек. АИ переходит по перешейку в «чужую» область, окрашивая его в «свой» цвет, а дальний инцидентор – в черный. На следующем шаге АИ возвращается по этому перешейку в «свою» область, окрашивая дальний инциден- тор и перешеек в черный цвет. 4.2. Помечено не менее двух перешейков. АИ переходит по первому найденному помеченному перешейку в «чужую» область, окрашивая его в «свой» цвет, а дальний инцидентор – в черный. На следующем шаге АИ возвращается по этому перешейку в «свою» область, окрашивая его в черный, а оба инцидентора – в «свой» цвет. Далее АИ движется назад по «своему» пути, пока не будет найден следующий помеченный перешеек. Далее возможны два варианта: 4.2.1. Следующий помеченный перешеек не последний. АИ переходит по найденному перешейку, окрашивая его в «свой» цвет, а дальний инцидентор – в черный. На сле- дующем шаге АИ возвращается по этому перешейку в «свою» область, окрашивая его и оба инцидентора в черный цвет. И снова возвращается назад по «своему» пути до следующего помеченного перешейка. 4.2.2. Следующий помеченный перешеек последний. АИ переходит по найденному перешейку, окрашивая его в «свой» цвет, а дальний инцидентор – в черный. На сле- дующем шаге АИ возвращается по этому перешейку в «свою» область, окрашивая его в черный, а оба инцидентора – в «свой» цвет. АИ переходит по последнему перешейку в «чужую» область, окрашивая инци- денторы в черный цвет. На следующем шаге АИ переходит по первому распознанному перешейку в «свою» область, окрашивая пройденные инциденторы в черный цвет. Далее АИ движется вперед по «своему» пути, пока не вернется в вершину, в которой он переключился в режим распознавания перешейков. 5. При одновременном попадании двух АИ в одну белую вершину, каждый АИ окрашивает вершину наполовину, и она становится красно-желтой. Агент B на следую- щем шаге отступает назад по своему пути и переходит в режим пометки перешейков (при этом ребро, по которому он вернулся, уже посчитано как первый перешеек, длина желтого пути уменьшена на одну вершину, а из списков ребер и вершин удалены ребро и вершина, записанные туда агентом B на предыдущем шаге). Агент A видит разно- цветную вершину как «свою», но при распознавании окрашивает в черный цвет обе половинки. Алгоритмы обхода и восстановления Рассмотрим непосредственно алгоритмы работы агентов, реализующие описан- ную выше стратегию. Процесс распознавания состоит из двух принципиально разных типов алгоритмов: «Обход» и «Восстановление». Первый тип алгоритма описывает обход графа G агентами-исследователями с целью проведения элементарных экспери- ментов и передачи необходимой информации АЭ. Второй тип алгоритма представляет собой анализ результатов элементарных экспериментов, в результате которого будет построен граф H, изоморфный распознаваемому графу G. Распознавание конечных графов тремя агентами «Штучний інтелект» 2’2011 87 1С Алгоритм работы агента A : 1. Агент A красит   rv : ; 2. запрос AN ; 3. if 1AN then do 4. запрос BN ; 5. if 0BN then МЕТИМ_ПЕР_А(v); 6. else ВЫБОР_ХОДА_А(v); 7. end do; 8. else РАСП_ПЕР_А(v); Все процедуры, которые не описаны ниже, представлены в [8]. РАСП_ПЕР_А(v): 1. KZ : ; 2. if в окрестности  vO нет ребра, у которого   yuv , then do 3. агент A выполняет ОТСТУП_А(v); 4. go to 2 данной процедуры; 5. end do; 6. else do 7. if        11  ZandKorZK then агент A выполняет РАСП_АВВ(v); 8. else агент A выполняет процедуру РАСП_АВВb(v); 9. агент A запрашивает у АЭ значение переменной K ; 10. if 0K then go to 2 данной процедуры; 11. else агент A выполняет процедуру ОБН_А(v); 12. if 1Z then do 13. if в  vO есть ребро, у которого           ruuvandbuvandrvuv  ,,,,,  then do 14. агент A выполняет процедуру ВПЕРЕД_AR_N(v); 15. go to 13 данной процедуры; 16. end do; 17. else if в  vO есть ребро, у которого          ruuvandruandruv  ,,,  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 выбирает из окрестности  vO ребро, для которого выполняется условие           rvandrvuvandruv   ,,, , и переходит по нему в вершину u . При этом, окрашивает        bvuvbuvbv  :,,,:,,:  , выполняет присвоение uv : и записывает в список M сообщение: НАЗАД_А. РАСП_А(v): 1. Агент A выбирает из окрестности  vO ребро  uv, , у которого        wuvandruv  , и переходит по нему в вершину u ; 2. агент A красит   buv , ; 3. агент A записывает в список M сообщение: ОБРАТНОЕ_РЕБРО_А; 4. while в  uO есть ребро  lu, , у которого          rlandrlluandrlu   ,,, do Степкин А.В. «Искусственный интеллект» 2’2011 88 1С 5. агент A переходит по ребру  lu, в вершину l ; 6. lu : ; 7. агент A записывает в список M сообщение: ОТСТУПИЛ_А; 8. end do; 9. агент A записывает в список M сообщение: РЕБРО_РАСПОЗНАНО_А; При выполнении процедуры РАСП_АВВ(v), агент A выбирает из окрестности  vO ребро  uv, , для которого выполняется условие   ,, yuv  и переходит по нему в вершину u , производя окрашивание      buuvruv  :,,,:,  . Выполняет присвоение uv : и записывает в список M сообщение: ВПЕРЕД_ABB. После чего агент A выбирает из окрестности  vO ребро  uv, , для которого выполняется условие   uv ,     bvuvandr  ,, , и переходит по нему в вершину u , окрашивая    rvuv :,,      ruuvbuvr  :,,,:,,  , выполняет присвоение uv : и записывает в список M сообщение: НАЗАД_ABB. Процедура РАСП_АВВb(v) аналогична процедуре РАСП_АВВ(v), с отличием в том, что, выполняя возврат по перешейку в «свою» область, агент A окрашивает ребро и дальний инцидентор следующим образом      buuvbuv  :,,,:,  . Выполняя процедуру ВПЕРЕД_АR_N(v), агент A выбирает из окрестности  vO ребро  uv, , удовлетворяющее условию       uvandrvuv  ,,,      uuvandb ,, = r , переходит по нему в вершину u , окрашивая       buuvbvuv  :,,,:,,  . После чего выполняет присвоение uv : и записывает в список M сообщение: ВПЕРЕД_AR_N. Выполняя процедуру СТОП_А(v), агент A красит   bv : и завершает работу. Алгоритм работы агента B : 1. Агент B красит   ys : ; 2. запрос BN ; 3. if 1BN then do 4. запрос AN ; 5. if rys )( then do 6. агент B выполняет процедуру ВОЗВРАТ_B(s); 7. агент B выполняет процедуру МЕТИМ_ПЕР_B(s); 8. end do; 9. else if 0AN then МЕТИМ_ПЕР_B(s); 10. else ВЫБОР_ХОДА_B(s); 11. end do; 12. else РАСП_ПЕР_B(s); Все процедуры агента B , которые не рассмотрены ниже, аналогичны процедурам агента A . При выполнении процедуры МЕТИМ_ПЕР_B(s), агент B проверяет наличие в ок- рестности  sO ребра  zs, , у которого          ryzorrzandws   z, . Если такое ребро обнаружено и в вершине z находится агент A , то агент B выполняет про- цедуру СТОИТ_ B(s) и возвращается в начало данной процедуры. Если же в вершине z нет агента A , то агент B выполняет процедуру МЕТИМ_BA(s) и возвращается в на- чало данной процедуры. Распознавание конечных графов тремя агентами «Штучний інтелект» 2’2011 89 1С Если в окрестности  sO не обнаружено ребра, которое удовлетворяет условию          ryzorrzandws   z, , то агент B запрашивает значение перемен- ной L . При этом если 0L , то агент B выполняет процедуру ВЫБОР_ХОДА_B(s), иначе агент B выполняет процедуру ФИКС_B(s) и возвращается в строку 2 АО. ВЫБОР_ХОДА_B(s): 1. if в  sO обнаружено ребро, у которого        yszandwzs   , then do 2. агент B выполняет процедуру РАСП_B(s); 3. go to 2 алгоритма обхода; 4. end do; 5. else if в  sO обнаружено ребро, у которого      wzandwzs   , then do 6. агент B выполняет процедуру ВПЕРЕД_B(s); 7. go to 2 алгоритма обхода; 8. end do; 9. else if в  sO есть ребро, у которого          ryzorrzandwzs   , then do 10. агент B выполняет процедуру СТОИТ_B(s); 11. go to 2 алгоритма обхода; 12. end do; 13. else if в  sO есть ребро, у которого   rzs , then do 14. агент B выполняет процедуру СТОИТ_B(s); 15. go to 2 алгоритма обхода; 16. end do; 17. else if в  sO есть ребро, у которого          ryzorrzandyzs   , then do 18. агент B выполняет процедуру СТОИТ_B(s); 19. go to 4 алгоритма обхода; 20. end do; 21. else if в  sO есть ребро, у которого          yszsandysandyzs  ,,,  then do 22. агент B выполняет процедуру НАЗАД_B(s); 23. go to 2 алгоритма обхода; 24. end do; 25. else агент B выполняет процедуру СТОП_B; При выполнении процедуры МЕТИМ_BA(s), агент B выбирает из окрестности  sO произвольное ребро  zs, , для которого выполняется условие      zandwzs   ,    ryzorr   , переходит по нему в вершину z , окрашивая      yzzsyzs  :,,,:,  , выполняет присвоение zs : и записывает в список N сообщение: ВПЕРЕД_BA. Далее агент B выбирает из окрестности  sO ребро  zs, , у которого     sandys  )(z,  ry , переходит по нему в вершину z , выполняет присвоение zs : и записывает в список N сообщение: НАЗАД_BА. Выполняя процедуру ВОЗВРАТ_B(s), агент B выбирает из окрестности  sO ребро  zs, , у которого       yszsandyzs  ,,,  , переходит по нему в вершину z , выполняет присвоение zs : и записывает в список N сообщение: ВОЗВРАТ_B. Алгоритм «Восстановление» и процедуры, которые не рассмотрены ниже, изложены в [8] с поправкой, что, при использовании цикла с предусловием, условие имеет вид:     NorM . Степкин А.В. «Искусственный интеллект» 2’2011 90 1С ОБР_СП_А(): 1. if "" = ВПЕРЕД_АMes then ВПЕРЕД_А(); 2. if "" = ВПЕРЕД_АВMes then ВПЕРЕД_AB(); 3. if "" = ВПЕРЕД_АBBMes then ВПЕРЕД_ABB(); 4. if "" = НАЗАД_АMes then НАЗАД_А(); 5. if "" = НАЗАД_АВMes then НАЗАД_АВ(); 6. if "" = НАЗАД_АВВMes then НАЗАД_АВВ(); 7. if "" = ФИКС_АMes then ФИКС_А(); 8. if "" = ОБН_АMes then ОБН_А(); 9. if "" = ОТСТУПИЛ_АMes then ОТСТУПИЛ_А(); 10. if "" = ОЗНАНО_АРЕБРО_РАСПMes then РЕБРО_РАСПОЗНАНО_А(); 11. if "" = ОТСТУП_АMes then ОТСТУП_А(); ОТСТУП_А(): 1:  ii ; ВПЕРЕД_ABB():    itrBNEE HH  ,_:  ; ОТСТУПИЛ_А(): 1:  ii ; РЕБРО_РАСПОЗНАНО_А():      itrtrEE HH  ,:  ; 0:i ; Процедуры работы со списком команд от агента B , которые не рассмотрены ниже, аналогичны процедурам работы со списком команд от агента A . ОБР_СП_B(): 1. if "" = ВПЕРЕД_BMes then ВПЕРЕД_B(); 2. if "" = ВПЕРЕД_ВАMes then ВПЕРЕД_BA(); 3. if "" = ВПЕРЕД_BААMes then ВПЕРЕД_BAA(); 4. if "" = НАЗАД_BMes then НАЗАД_B (); 5. if "" = НАЗАД_ВАMes then НАЗАД_ВА(); 6. if "" = НАЗАД_ВААMes then НАЗАД_ВАА(); 7. if "" = ФИКС_BMes then ФИКС_B(); 8. if "" = ОБН_BMes then ОБН_B(); 9. if "" = ОТСТУПИЛ_BMes then ОТСТУПИЛ_B(); 10. if "" = ОЗНАНО_BРЕБРО_РАСПMes then РЕБРО_РАСПОЗНАНО_B(); 11. if "" = ОТСТУП_BMes then ОТСТУП_B(); 12. if "="ВОЗВРАТ_BMes then ВОЗВРАТ_B(). ВОЗВРАТ_B():      pypyEE HH ,1\:  ; }_{\: BСчVV HH  ; 2_:_  BСчBСч ; 1:  pp ;   BСчpy _: ; 1:L ; 1:  KK . Свойства алгоритма распознавания В начале алгоритма, при 3n , как минимум, по одному разу выполняются про- цедуры: ВПЕРЕД_А(v), ВПЕРЕД_А() и ВПЕРЕД_В(s), ВПЕРЕД_B(). Выполняя про- цедуры ВПЕРЕД_А(v) и ВПЕРЕД_В(s), АИ посещают новые вершины исследуемого графа G . Процедурами агента АЭ ВПЕРЕД_А() и ВПЕРЕД_B() создаются две новые вершины (по одной вершине для каждой из процедур) графа H . При одновременном попадании двух АИ в одну белую вершину процедурами ВПЕРЕД_А() и ВПЕРЕД_B() будет создано две новые вершины графа H . Одна из этих Распознавание конечных графов тремя агентами «Штучний інтелект» 2’2011 91 1С двух вершин (вершина, созданная агентом B ) будет удалена командой ВОЗВРАТ_B(), так как она дублирует вершину, созданную агентом A . Таким образом, процесс выпол- нения описанного алгоритма индуцирует отображение HG VV : вершин графа G в вершины графа H . Причем   tv  (когда вершина v окрашена в красный цвет) и АСчt _ ) и   ps  (когда вершина s окрашена в желтый цвет и BСчp _ ). Ука- занное отображение естественным образом устанавливает неявную нумерацию вершин графа G . Более того, отображение  является биекцией, поскольку в связном графе G все вершины достижимы из начальных вершин. Поэтому все вершины посещаются агентами, то есть окрашиваются в красный и желтый цвета. Из описания алгоритма следует, что АИ проходят все ребра графа G , поскольку при окончании алгоритма все ребра становятся черными. При выполнении процедуры ВПЕРЕД_А() или ВПЕРЕД_B() АЭ распознает древесное ребро  uv, и так нумерует вер- шину u , что ребру  uv, однозначно соответствует ребро     uv  , графа H . При вы- полнении процедур РЕБРО_РАСПОЗНАНО_A() или РЕБРО_РАСПОЗНАНО_B() АЭ распознает обратное ребро  uv, графа G и ставит ему в однозначное соответствие ребро     uv  , графа H . При выполнении процедур ФИКС_А(), ВПЕРЕД_АВВ() или ФИКС_В(), ВПЕРЕД_ВАА() АЭ распознает перешеек  uv, графа G и ставит ему в однозначное соответствие ребро     uv  , графа H . Следовательно,  является изо- морфизмом графа G на граф H . Теорема 1. Выполняя алгоритм распознавания, агенты распознают любой граф G с точностью до изоморфизма. Подсчитаем временную и емкостную сложность в равномерной шкале [5]. Для этого рассмотрим свойства красного и желтого путей. Из описания алгоритма следует, что на каждом шаге алгоритма красный (желтый) путь – это простой путь, соеди- няющий начальную вершину v ( s - в случае агента B ) с номером 1)( v  2)( s с вершиной u  z с номером AСчu _)(   BСчz _)(  . Следовательно, общая длина красного и желтого пути не превосходит n . При выполнении процедур ВПЕРЕД_A(v), ВПЕРЕД_B(s) и НАЗАД_A(v), НАЗАД_B(s) АИ проходят одно ребро. При выполнении процедур РАСП_А(v), РАСП_B(s) АИ проходят одно обратное ребро и не более 2n (изначально одна вершина уже окрашена в «чужой» цвет) ребер красного и желтого путей. При выпол- нении процедур РАСП_А(v), РАСП_B(s) АИ проходят фактически цикл, состоящий из обратного ребра и некоторого конечного отрезка красного (желтого) пути, соеди- няющего вершины, инцидентные обратному ребру. При выполнении процедур МЕТИМ_АВ(v), МЕТИМ_ВА(s) и РАСП_АВВ(v), РАСП_АВВb(v), РАСП_ВАА(s), РАСП_ВААb(s) оба АИ проходят один и тот же перешеек, сначала в одном направ- лении, потом в обратном. Выполняя процедуры ВПЕРЕД_AR(v), ВПЕРЕД_BR(s) и ОТСТУП_A(v), ОТСТУП_B(s), АИ проходят одно красное (желтое) ребро. При вы- полнении процедур ВПЕРЕД_AR_N(v), ВПЕРЕД_BR_N(s) АИ проходят одно черное ребро. При выполнении процедур ФИКС_А(v), ФИКС_B(s) и ОБН_А(v), ОБН_В(s) АИ не передвигаются, а только делают записи в свой список команд для АЭ, на что так же уходит один ход. При подсчете временной сложности алгоритма будем считать, что инициализация алгоритма, анализ окрестности  vO рабочей вершины и выбор одной из возможных процедур занимают некоторое постоянное число единиц времени. Также будем считать, Степкин А.В. «Искусственный интеллект» 2’2011 92 1С что выбор ребер, проход по ним АИ и обработка команд АЭ, полученных на данном этапе от АИ, осуществляется за 1 единицу времени. Тогда временная сложность алго- ритма определяется следующими соотношениями: 1. Процедуры ВПЕРЕД_А(v), ВПЕРЕД_B(s), НАЗАД_А(v) и НАЗАД_B(s) вы- полняются не более чем  12  n раз, общее время их выполнения оценивается как  nO . 2. На выполнение процедур МЕТИМ_АВ(v), МЕТИМ_BA(s), РАСП_АВВ(v), РАСП_АВВb(v), РАСП_ВАА(s) и РАСП_ВААb(s) уходит время, которое оценивается как nnO  )(4 , то есть как  2nO . 3. Каждая из пар процедур ВПЕРЕД_AR(v), ВПЕРЕД_BR(s) и ОТСТУП_А(v), ОТСТУП_B(s) выполняются за время, оцениваемое как nnO )( , то есть как  2nO . 4. На выполнение процедур ВПЕРЕД_AR_N(v), ВПЕРЕД_BR_N(s), ФИКС_А(v), ФИКС_B(s), ОБН_А(v) и ОБН_B(s) уходит время, оцениваемое как )(3 nO , т.е. как  nO . 5. Время, затрачиваемое на выполнение процедур РАСП_А(v) и РАСП_B(s), оценивается как mnO )( , то есть как  3nO . 6. Время выполнения процедур СТОИТ_А(v) и СТОИТ_В(s) в общей сложности для всех четырёх возможных случаев оценивается как      22 nOnOnO  . Следовательно, суммарная временная сложность )(nT алгоритма удовлетворяет со- отношению:    3nOnT  . Емкостная сложность )(nS алгоритма определяется сложностью списков ,,EV HH )()...1(),()...1( pyytrr , сложность которых соответственно определяется величинами        nOnOnOnO ,,, 2 . Следовательно,    2nOnS  . Теорема 2. Временная сложность алгоритма распознавания равна  3nO , а ем- костная –  2nO . При этом алгоритм использует 3 краски. Выводы Основными результатами исследования являются: создание алгоритма работы трёх агентов, при условии, что АИ передвигаются по графу одновременно, а также решение проблемы окраски вершины, которая возникала при одновременном попа- дании двух АИ в одну белую вершину. Предложен алгоритм точного распознавания графа среды временной сложности  3nO и емкостной –  2nO . АИ имеют память, ограниченную числом n , и используют по две краски каждый (всего три краски). На основе полученного алгоритма автор надеется создать новые более эффектив- ные алгоритмы, которые позволят улучшить результаты, полученные в [4]. Литература 1. Albers S. Exploring unknown environments / S. Albers and M.R. Henzinger // SIAM Journal on Computing. – 2000. – № 29 (4). – Р. 1164-1188. 2. Грунский И.С. Распознавание конечного графа блуждающим по нему агентом / И.С. Грунский, Е.А. Татаринов // Вестник Донецкого университета. Серия А. Естественные науки. – 2009. – Вып. 1. – С. 492-497. 3. Кудрявцев В.Б. Введение в теорию автоматов / Кудрявцев В.Б., Алешин С.В., Подкозлин А.С. – М. : Наука, 1985. – 320 с. Распознавание конечных графов тремя агентами «Штучний інтелект» 2’2011 93 1С 4. Грунский И.С. Распознавание конечного графа коллективом агентов / И.С. Грунский, А.В. Стёпкин // Труды ИПММ НАН Украины. – 2009. – Т. 19. – С. 43-52. 5. Ахо А. Построение и анализ вычислительных алгоритмов / Ахо А., Хопкрофт Дж., Ульман Дж. – М. : Мир, 1979. – 536 с. 6. Кормен Т. Алгоритмы: построение и анализ / Кормен Т., Лейзерсон Ч., Ривест Р. – М. : МЦНМО, 2001. – 960 с. 7. Касьянов В.Н. Графы в программировании: обработка, визуализация и применение / В.Н. Касьянов, В.А. Евстигнеев. – СПб. : БХВ – Петербург, 2003. – 1104 с. 8. Стёпкин А.В. Распознавание конечного графа коллективом агентов / А.В. Стёпкин // Інформатика та комп’ютерні технології-2009 : матеріали V міжнар. наук.-техн. конф. студентів, аспірантів та молодих вчених (Донецьк, 24 – 26 лист. 2009 р.). − Донецьк, 2009. – Т. 2. – С. 126-131. Literatura 1. Albers S. SIAM Journal on Computing. № 29 (4). 2000 P. 1164-1188. 2. Grunsky I.S. Newsletter of Donetsk University. Series A. Natural Sciences.2009.Vol.1. P. 492-497. 3. Kudryavtsev V.B. Moscow: Nauka. 1985. 320 p. 4. Grunsky I.S. Studies of IAMM NASU. 2009. Vol.19. P. 43-52. 5. Aho A. Moscow: Mir. 1979. 536 p. 6. Kormen T. Moscow: MCCME. 2001. 960 p. 7. Kasyanov V.N. S-Ptb.: BHV. 2003. 1104 p. 8. Stepkin A.V. Informatics and computer tehnologies.2009. Materials of the V-th science conference for postgraduates and young scientists. Donetsk. 2009. Vol. 2. P. 126-131. А.В. Стьопкін Розпізнавання скінченних графів трьома агентами У статті розглядається проблема розпізнавання скінченних графів трьома агентами. Два агенти-дослідники рухаються графом, зчитують, аналізують та змінюють помітки елементів графа, передають інформацію про свої переміщення агенту-експериментатору, який розпізнає досліджуваний граф. Запропоновано алгоритм часової складності  3nO та ємнісної –  2nO , який розпізнає будь-який скінченний неорієнтований граф. Для розпізнавання кожному агенту необхідно дві різні фарби (усього три фарби). Метод базується на методі обходу графа в глибину. A.V. Stepkin Finite Graphs Exploration by Three Agents The Problem of finite graphs exploration by three agents is considered in this work. Two agents-researchers move on graph, they read, analyze and change marks of graph elements, transfer the information about their movements and colorings to the agent-experimenter. It builds explored graph representation. The algorithm with  3nO time ( n is amount of nodes of graph) and  2nO space complexities is proposed. It recognizes any finite non-oriented graph. For graph exploration each agent needs two different marks (three colors in total). The method is based on the depth-first traversal method. Статья поступила в редакцию 16.05.2011.

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

Репозитарії

Схожі ресурси