/Materials Пн, 14.10.2024, 06:04

Сайт методики довузовского обучения программированию
и проектной деятельности в информатике


Главная страница, Контакты, RSS
 
> Меню сайта

> Разделы новостей
Семинар [36]
Семинар по системному и прикладному программированию
Etc [15]
Разное
Конференция [16]
Открытая конференция исследовательских и проектных работ

> Архив новостей

> Партнеры

> Поиск

> Статистика

Главная » 2013 » Июнь » 5 » Применение автоматного метода в задаче поиска выхода из лабиринта
Применение автоматного метода в задаче поиска выхода из лабиринта
Артем Пимкин
10 класс

Задача поиска выхода из лабиринта имеет множество известных алгоритмических решений. Одно из них - «правило левой руки». Оно заключается в том, что на каждом повороте следует поворачивать налево. Если возможность повернуть налево отсутствует, то нужно идти прямо. Если и туда нельзя, то направо. Если впереди тупик, то надо развернуться. Такой алгоритм поведения находит выход только из односвязных (не содержащих замкнутых маршрутов) лабиринтов, а также легко описывается описывается как с помощью любого алгоритмического языка, так и с помощью конечного автомата [1]. Целью работы является сравнение этих двух способов описания алгоритма при разработке программы.

Программа Maze – это симулятор произвольного односвязного лабиринта с исполнителем-роботом, который проходит лабиринт. Во время разработки программы был проведен эксперимент, связанный с ее разработкой. Было разработано две версии программы, идентичных по функциональности и интерфейсу, но отличающихся реализацией алгоритма поиска выхода. В первой версии алгоритм был написан вручную, а во второй применен сгенерированный из схемы конечный автомат [2]. Для генерации автомата была использована программа Visio2Auto Л. Столярова [3]. Этот эксперимент был проведен для выяснения того, действительно ли автоматное программирование упрощает разработку.

Как оказалось, представление алгоритма в виде автоматной схемы действительно сильно снижает сложность разработки программы. Для простоты понимания алгоритма работы программы, рано или поздно придется рисовать схему в Microsoft Visio или аналогичных редакторах и заботиться о ее соответствии фактическому коду программы, а в случае автоматного подхода изначально нарисованная схема легко транслируется в код без участия человека. А это значит, что, по сути, нарисованная схема являет собой уже большую часть сделанной работы. Кроме того, автоматическая трансляция исключает человеческий фактор при кодировании логической части алгоритма, являющийся источником ошибок.

Помимо самого лабиринта и робота, его проходящего, в программе Maze была реализована максимально понятная визуализация работы конечного автомата. Каждый шаг робота одновременно показывается в окне с лабиринтом и в окне со схемой автомата, в котором видно, какие состояния при этом сменились и почему. Также немаловажную часть в понятности и функциональности программы играет консоль, в которой ведется подробная распечатка всех состояний и переходов конечного автомата. Также из консоли возможен вызов всех основных команд, работающих с лабиринтом, роботом, распечаткой, схемой и прочих. Подробный список команд с их описанием доступен по введению команды "help” в консоли. Кроме того, для простоты сопоставления распечаток переходов и состояний в консоли с реальными перемещениями робота, пройденный путь подсвечивается.

Программу Maze также можно использовать как небольшое учебное пособие по конечным автоматам на примере данного конечного автомата в данной задаче, благодаря реализованной системе простых сценариев (скриптов) для консоли. Это значит, что написав небольшой сценарий, вы можете оставить пользователя наедине с программой, и она сама объяснит ему, как работают конечные автоматы в данной задаче.

Из недостатков проекта можно упомянуть неуниверсальность подхода, примененного в модуле визуализации, который был жестко оптимизирован под данную задачу для сокращения сроков разработки.

Программа разработана на языке С++ в средах Microsoft Visual Studio, KDevelop и Qt Creator в операционных системах Microsoft Windows и Linux с использованием кроссплатформенной библиотеки Qt [4].

ЛИТЕРАТУРА

1. Дж. Хопкрофт. Введение в теорию автоматов, языков и вычислений. М.: Вильямс, 2002.
2. Н. И. Поликарпова, А. А. Шалыто. Автоматное программирование. СПб.: Питер. 2009.
3. Л.Н. Столяров. Трансляция описаний автоматов, представленных в формате Microsoft Visio, в исходный код на языке Си. СПб.: Компьютерные инструменты в образовании, № 5, 2009, с. 35-44.
4. М. Шлее. Qt 4.5: Профессиональное программирование на С++. СПб.: БХВ-Петербург, 2010.

Материалы доклада
Репозиторий проекта

Категория: Семинар | Просмотров: 5990 | Добавил: ded32
> Инструменты

Orphus


О рекламе на сайте ↑

Сайт рас­по­ло­жен на бес­плат­ном хос­тин­ге, пра­ви­ла ко­то­ро­го за­пре­ща­ют вы­ре­зать ре­к­ла­му, встав­ляе­мую авто­ма­ти­чес­ки, в том чис­ле в ви­де авто­ма­ти­чес­ко­го от­кры­тия стра­ниц дру­гих сай­тов. Ав­тор это­го сай­та не име­ет ни­ка­ко­го отно­ше­ния к этой ре­кла­ме.


> Загрузить

> Основные материалы

> Примеры проектов



Copyright (c) И.Р. Дединский, 2006-2024
Никакая часть материалов данного сайта или его подразделов не может быть прямо или косвенно процитирована или упомянута без действующей активной ссылки на данный сайт
...

Хостинг от uCoz

MasterHost Orphus