RUS  ENG
Полная версия
ЖУРНАЛЫ // Математическое образование // Архив

Матем. обр., 2016, выпуск 1(77), страницы 23–43 (Mi mo540)

Студентам и преподавателям математических специальностей

Обход конечным автоматом с четырьмя камнями $k$-мерного пространства за полиномиальное время

Д. В. Гусев

Московский инженерно-физический институт (государственный университет)

Аннотация: В работе описана система “лабиринт-робот”, действующая на основе некоторого конечного автомата. Предложен алгоритм обхода пространства $\mathbb{Z}^k$ для любого $k$ роботом с четырьмя камнями, причем время посещения точки полиномиально по координатам этой точки. Обсуждаются оценки оптимального числа камней.

Ключевые слова: Конечный автомат, камень, обход $k$-мерного пространства, полиномиальное время посещения точки.

УДК: 519.712.5



© МИАН, 2024