Preview

Чебышевский сборник

Расширенный поиск

Вероятностные методы обхода лабиринта с использованием камней и датчика случайных чисел

https://doi.org/10.22405/2226-8383-2019-20-3-296-315

Полный текст:

Аннотация

Существует широкий спектр задач посвященных возможности обхода лабиринта конечными автоматами. Они могут отличаться как типом лабиринта(это может быть любой граф, даже бесконечный), так и самими автоматами или их количеством. В частности у конечного автомата может быть память(магазин) или генератор случайных битов. В дальнейшем будем считать, что робот — это конечный автомат с генератором случайных битов, если не сказано иное. Кроме того в этой системе могут быть камни-объект, который конечный автомат может переносить по графу, и флажки- объект, наличие которого конечный автомат может только "наблюдать". Эта тема представляет интерес в связи с тем, что некоторые из этих задач тесно связаны с задачами из теории вероятности и сложности вычислений.

В данной работе продолжают решаться некоторые открытые вопросы, поставленные в диссертации Аджанса: обход роботом с генератором случайных битов целочисленных пространств при наличии камня и подпространства флажков [4]. Подобные задачи помогают развить математический аппарат в данной области, кроме того в этой работе мы исследуем практически не изученное поведение робота с генератором случайных чисел. Представляется чрезвычайно важным перенос комбинаторных методов, разработанных А. М. Райгородским в задачах этой тематики.

Данная работа посвящена обходу лабиринта конечным автоматом с генератором случайных битов. Эта задача является частью активно развивающейся темы обхода лабиринта различными конечными автоматами или их коллективами, которая тесно связана с задачами из теории сложности вычислений и теории вероятности. В данной работе показано, при каких размерностях робот с генератором случайных битов и камнем может обойти целочисленное пространство с подпостранством флажков. В данной работе будет изучено поведение конечного автомата с генератором случайных битов на целочисленных пространствах. В частности доказано, что робот обходит Z2 и не может обойти Z3; робот c камнем обходит Z4 и не может обойти Z5; робот c камнем и флажком обходит Z6 и не может обойти Z7; робот c камнем и плоскостью флажков обходит Z8 и не может обойти Z9.

Список литературы

1. Килибарда Г., Кудрявцев В. Б., Ушчумлич Ш. М. Независимые системы автоматов в лабиринтах // Дискрет. матем. 1987.

2. Килибарда Г. О сложности автоматного обхода лабиринтов // Дискрет. матем. 1993.

3. Килибарда Г., Кудрявцев В. Б., Ушчумлич Ш. М. Независимые системы автоматов в лабиринтах // Дискрет. матем. 2003.

4. Анджанс А. В. Поведение детерминированных и вероятностных автоматов в лабиринтах: Дис. ... канд. физ.-мат. наук. Рига, 1987.

5. Килибарда Г., Кудрявцев В. Б., Ушчумлич Ш. М. Коллективы автоматов в лабиринтах // Дискрет. матем. 2003.

6. Килибарда Г., Ушчумлич Ш. М. О лабиринтах-ловушках для коллективов автоматов // Дискрет. матем. 1993.

7. Килибарда Г., Кудрявцев В. Б., Ушчумлич Ш. М. Системы автоматов в лабиринтах // Дискрет. матем. 2006.

8. Spitzer F. Principles of Random Walks. Van Nostrand, 1964.

9. Ширяев А. Н. Вероятность: В 2 кн. Вероятность-1, Вероятность-2. М.: МЦНМО, 2004.

10. Дынкин Е. Б., Юшкевич А. А. Теоремы и задачи о процессах Маркова. М.: Наука, 1967.


Для цитирования:


Кондакова Е.Г., Канель-Белов А.Я. Вероятностные методы обхода лабиринта с использованием камней и датчика случайных чисел. Чебышевский сборник. 2019;20(3):296-315. https://doi.org/10.22405/2226-8383-2019-20-3-296-315

For citation:


Kondakova E.G., Kanel-Belov A.Y. Probabilistic methods of bypass of the labyrinth using stones and random number generator. Chebyshevskii Sbornik. 2019;20(3):296-315. (In Russ.) https://doi.org/10.22405/2226-8383-2019-20-3-296-315

Просмотров: 36


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2226-8383 (Print)