Конференции ИВТ СО РАН

VIII Всероссийская конференция молодых ученых по математическому моделированию и информационным технологиям

27 - 29 ноября 2007 года, Новосибирск

Тезисы докладов

Информационные технологии

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

Несвитайло А.А.

Белгородский Государственный Университет (Белгород)

Существующие геоинформационные системы(ГИС) часто не отвечают запросам потребителей (они громоздки, недоступны для редактирования, дороги, и, как правило, решают большое количество задач, потребности в которых у большинства пользователей не возникает). Поэтому существует необходимость создания простой и удобной в эксплуатации узкоспециализированной ГИС, которая позволила бы решать задачу многопараметрического поиска оптимального маршрута на карте, при этом была бы открыта для редактирования пользователями.

Для решения поставленной задачи была спроектирована и реализована система поиска оптимальных маршрутов ”GISka 2007”, использующая специально разработанный эвристический алгоритм многопараметрического поиска, описанный на языке Prolog (логический подход), осуществляющий поиск необходимого маршрута.

Применение логического подхода обусловлено тем, что, во-первых, на языке логического программирования легко реализуем поиск по дереву с возвратом, что наиболее подходит для реализации тех алгоритмов, которые дают возможность многопараметрического поиска оптимальных путей передвижения. Во-вторых, использование именно логического подхода предполагает создание открытой базы знаний системы: отдельные компоненты системы (факты, правила, цели и т.п.) могут быть дополнены или изменены независимо друг от друга, что делает редактирование базы знаний системы более удобным. В-третьих, логический подход делает простой и интуитивно понятной разработку экспертных систем, основанных на знаниях, систем поддержки принятия решений, планирующих программ, развитых систем управления базами данных и других.

Поиск в графах, как правило, невозможен без решения проблемы комбинаторной сложности, возникающей из-за быстрого роста числа альтернатив. Эффективным средством борьбы с этим служит эвристический поиск.

Один из путей использования эвристической информации о задаче − это получение численных эвристических оценок для вершин пространства состояний. При разработке алгоритма поиска в качестве эвристической оценки был использован параметр “угол обзора”. Наиболее приоритетными дугами при анализе оптимальности выбираются дуги, попадающие в угол обзора, угол, биссектриса которого соединяет стартовую и целевую вершины.

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

Примечание. Тезисы докладов публикуются в авторской редакции

Ваши комментарии
Обратная связь

[Головная страница]
[Конференции]