RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB
Общая информация
Последний выпуск
Архив

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS



Чебышевский сб.:
Год:
Том:
Выпуск:
Страница:
Найти






Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация


Чебышевский сб., 2019, том 20, выпуск 3, страницы 165–192 (Mi cheb806)  

Поведение конечных автоматов в лабиринтах

Д. В. Гусев

Московский физико-технический институт (г. Москва)

Аннотация: Работа посвящена исследованию задач о поведении конечных автоматов в лабиринтах. Для любого $n$ строится лабиринт, который можно обойти с помощью $2n$ камней но нельзя обойти с помощью $n$ камней.
Спектр задач обхода обширен и затрагивает ключевые аспекты теоретической Computer Science. Конечно, решение таких задач не означает автоматическое решение сложных проблем теории сложности, тем не менее рассмотрение данных вопросов может положительно сказаться на понимании сути теоретической Computer Science. Есть надежда, что поведение автоматов в лабиринтах является хорошей моделью для нетривиальных теоретико-информационных задач, и отработка методов и подходов к исследованию поведения роботов даст более серьезные результаты с будущем.
Задачи связанные c автоматным анализом геометрических сред имеют довольно богатую историю изучения. Первой работой, давшей начало подобного рода задачам, стоит признать работу Шеннона [24]. В ней рассматривается модель мыши в виде автомата, которая должна найти определенную цель в лабиринте. Другая ранняя работа, так или иначе затрагивающая нашу проблематику, это работа Фишера [9] о вычислительных системах с внешней памятью в виде дискретной плоскости.
Серьёзным толчком к исследование поведения автоматов в лабиринтах послужила работы Деппа [7, 8], в которых предложена следующая модель: имеется некоторая конфигурация клеток из $\mathbb{Z}^2$ (шахматный лабиринт), в которой конечные автоматы, обозревая некоторую окрестность клетки, в которой они находятся, могут перемещаться в соседнюю клетку в одном из четырёх направлений.
Основной вопрос, который ставится в подобной модели, существует ли автомат обходящий все подобные лабиринты.
В [20] Мюллер построил для заданного автомата плоскую ловушку (лабиринт который обходится не полностью) в виде $3$-графа. Будах [5] построил шахматную ловушку для любого заданного конечного автомата. Отметим, что решение Будаха было довольно сложным (первые варианты содержали 175 страниц). Более наглядные решения данного вопроса представлены здесь [29, 31, 33, 34]. Антельман [2] оценил сложность подобной ловушки по числу клеток, а в [1] Антельман, Будах и Роллик сделали конечную ловушку для любой конечной системы автоматов.
В постановке с шахматным лабиринтом и одним автоматом есть ещё ряд результатов, связанных с проблемами обходимости лабиринтов с различными числом дыр, с расслоениями лабиринтов по количеству состояний автомата и другими вопросами. Обзор подобных проблем можно найти например здесь [35].
Невозможность обхода всех плоских шахматных лабиринтов одним автоматом выдвинула вопрос об изучении возможных усилений модели автомата, которая решит задачу обхода. Основным способом усиления может являться рассмотрение коллектива автоматов, вместо одного автомата, взаимодействующих между собой. Частным и широко используемым случаем является рассмотрение системы из одного полноценного автомата и некоторого количества автоматов камней, которые не имеют внутреннего состояние и могут передвигаться только совместно с главным автоматом. Взаимодействие между автоматами является ключевой особенностью данного усиления, оно позволяется иметь коллективу (или одному автомату с камнями) внешнюю память, тем самым существенно разнообразит его поведение. Если от взаимодействия автоматов избавиться, то полученная независимая система будет немногим лучше одного автомата.
Далее обсудим известные результаты связанные с коллективом автоматов.

Ключевые слова: обход лабиринта, конечный автомат.

Финансовая поддержка Номер гранта
Российский научный фонд 17-11-01377
Работа была поддержана Российским научным фондом (грант № 17-11-01377).


DOI: https://doi.org/10.22405/2226-8383-2018-20-3-165-192

Полный текст: PDF файл (951 kB)

Тип публикации: Статья
УДК: 517+519.713
Поступила в редакцию: 05.10.2019
Принята в печать:12.11.2019

Образец цитирования: Д. В. Гусев, “Поведение конечных автоматов в лабиринтах”, Чебышевский сб., 20:3 (2019), 165–192

Цитирование в формате AMSBIB
\RBibitem{Gus19}
\by Д.~В.~Гусев
\paper Поведение конечных автоматов в лабиринтах
\jour Чебышевский сб.
\yr 2019
\vol 20
\issue 3
\pages 165--192
\mathnet{http://mi.mathnet.ru/cheb806}
\crossref{https://doi.org/10.22405/2226-8383-2018-20-3-165-192}


Образцы ссылок на эту страницу:
  • http://mi.mathnet.ru/cheb806
  • http://mi.mathnet.ru/rus/cheb/v20/i3/p165

    ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    Citing articles on Google Scholar: Russian citations, English citations
    Related articles on Google Scholar: Russian articles, English articles
  • Просмотров:
    Эта страница:63
    Полный текст:16
     
    Обратная связь:
     Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2020