Автор: Татаринов Е.А., Грунский И.С.
Источник: Грунский И.С. Распознавание лабиринтов при помощи конечных автоматов. / И.С. Грунский, Е.А. Татаринов // Труды 4 междунар. конф. «Параллельные вычисления и задачи управления», РАСО’2008, 27‐29 октября 2008 г., Москва. – М: ИПУ РАН им. В.А. Трапезникова, 2008. – С. 1483‐1498
Рассматриваются обыкновенные конечные связные графы, степени вершин которых ограничены константой D. Работа посвящена созданию алгоритма восстановления произвольного графа блуждающим по нему автоматом. В отличии от обычного подхода [1] в настоящей работе по графу блуждает конечный автомат – агент, который размечает вершины и инциденторы вершин графа, воспринимает эти отметки и передает сообщения второму автомату – экспериментатору, который по этим сообщениям восстанавливает граф. Экспериментатор обладает растущей памятью и не передает сообщения агенту.
В работе представлены два алгоритма: «Обход графа» и «Восстановление графа». Первый реализуется агентом, второй – экспериментатором. Агент обладает двумя красками в неограниченном количестве и D экземплярами съемных камней. Алгоритм «Обход графа» основан на методе обхода графа в глубину. Агент двигается по ребрам в глубину графа, до тех пор, пока не попадет в вершину, из которой он может попасть только в уже пройденные вершины, и восстанавливает ее 1 – окрестность. Для этого он метит инциденторы вершин из 1 – окрестности камнем ‘1’ совершает отход по пройденным вершинам, с целью найти все камни ‘1’ и передает сообщения экспериментатору. Таких сообщений, указываемых агентом экспериментатору на движение и отметки вершин и инциденторов, семь.
Теорема. Временная сложность алгоритма «Обход графа» 0(n2), где n – число вершин исследуемого графа, а алгоритма «Восстановление графа» 0(n).
Операция º на множестве Х+ определяется следующим образом: для всех w1, w2 ∈ X , всех х,у ∈ X w1x º yw2=w1xw2, если х=у; w1x º yw2 – не определено, если х≠у.
Следует отметить, что эта оценка лучше [1], где сложность восстановления равна 0(n3).
Найдены случаи графов (деревья, циклы, кактусы и др.), для которых сложность предложенных алгоритмов равна 0(n).
1. Dudek G. Robotic explorations graph construction / G. Dudek, M. Jenkin, E. Milos, D. Wilkes // IEEE Trans. On Robotics and Automation.
1991. – v.7 – p. 859 – 864.