Распознавание лабиринтов при помощи конечных автоматов
ВРассматриваются обыкновенные конечные связные графы, степени вершин которых ограничены константой 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.
Надійшла до редакції 2011 р.