|
Вероятностные методы обхода лабиринта с использованием камней и датчика случайных чисел
Е. Г. Кондаковаa, А. Я. Канель-Беловbc a Московский физико-технический институт (г. Москва)
b Университет Бар-Илана (г. Рамат-Ган, Израиль)
c Колледж
математики и статистики, Шэньчжэньский университет, Шэньчжэнь, 518061, Китай
Аннотация:
Существует широкий спектр задач посвященных возможности обхода лабиринта конечными автоматами.
Они могут отличаться как типом лабиринта (это может быть любой граф, даже бесконечный), так и самими автоматами или их количеством.
В частности у конечного автомата может быть память (магазин) или генератор случайных битов.
В дальнейшем будем считать, что робот — это конечный автомат с генератором случайных битов, если не сказано иное.
Кроме того в этой системе могут быть камни-объект, который конечный автомат может переносить по графу, и флажки- объект, наличие которого конечный автомат может только "наблюдать".
Эта тема представляет интерес в связи с тем, что некоторые из этих задач тесно связаны с задачами из теории вероятности и сложности вычислений.
В данной работе продолжают решаться некоторые открытые вопросы, поставленные в диссертации Аджанса: обход роботом с генератором случайных битов целочисленных пространств при наличии камня и подпространства флажков [4].
Подобные задачи помогают развить математический аппарат в данной области, кроме того в этой работе мы исследуем практически не изученное поведение робота с генератором случайных чисел.
Представляется чрезвычайно важным перенос комбинаторных методов, разработанных А. М. Райгородским в задачах этой тематики.
Данная работа посвящена обходу лабиринта конечным автоматом с генератором случайных битов.
Эта задача является частью активно развивающейся темы обхода лабиринта различными конечными автоматами
или их коллективами, которая тесно связана с задачами из теории сложности вычислений и теории вероятности.
В данной работе показано, при каких размерностях робот с генератором случайных битов и камнем может обойти
целочисленное пространство с подпостранством флажков. В данной работе будет изучено поведение конечного автомата с генератором случайных битов на целочисленных пространствах.
В частности доказано, что
робот обходит $\mathbb{Z}^2$ и не может обойти $\mathbb{Z}^3$;
робот c камнем обходит $\mathbb{Z}^4$ и не может обойти $\mathbb{Z}^5$;
робот c камнем и флажком обходит $\mathbb{Z}^6$ и не может обойти $\mathbb{Z}^7$;
робот c камнем и плоскостью флажков обходит $\mathbb{Z}^8$ и не может обойти $\mathbb{Z}^9$.
Ключевые слова:
обход лабиринта, конечный автомат.
Поступила в редакцию: 05.10.2019 Принята в печать: 12.11.2019
Образец цитирования:
Е. Г. Кондакова, А. Я. Канель-Белов, “Вероятностные методы обхода лабиринта с использованием камней и датчика случайных чисел”, Чебышевский сб., 20:3 (2019), 296–315
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/cheb813 https://www.mathnet.ru/rus/cheb/v20/i3/p296
|
Статистика просмотров: |
Страница аннотации: | 324 | PDF полного текста: | 166 | Список литературы: | 46 |
|