Разработка алгоритма автоматической трассировки кратчайшего пути

в задачах социально-образовательной сферы

Е.И. Артамонов,

д.т.н., зав. лаб., проф.,

С.В. Смирнов,

аспирант

ИПУ РАН, г. Москва

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

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

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

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

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

Алгоритм функционирования системы трассировки (СТС) содержит следующие основные операции (рис. 1.0):

Ввод описания геометрической модели трассируемого поля (ОМ). Для выяснения способов представления в систему трассировки информации о

трассируемом поле проводится анализ сложности построения структур (ТО, ТВО, ПТФ, ТФ) программного обеспечения для решения оптимизационных задач в ГИС.

1. Ввод описания геометрической модели трассируемого поля (дорожная сеть) при помощи способа ТО. ТО - параметрическая таблица описаний входной информации.

Рис.1.0. Структурная схема основных операций разработки алгоритма функционирования системы трассировки

1. Редактирование описания модели трассируемого поля, запись и чтение из базы данных.

2. Ввод описания путей (ОП), соединяющих между собой объекты дорожной сети.

3. Редактирование описания цепей, запись и чтение из базы данных.

5. Ввод описания геометрической модели трассируемого поля (ОМ). Для выяснения способов представления в систему трассировки информации о трассируемом поле проводится анализ сложности построения структур (ТО, ТВО, ПТФ, ТФ) программного обеспечения для решения оптимизационных задач в ГИС. Ввод описания геометрической модели трассируемого поля (дорожная сеть) при помощи способа ТО. .

6. Редактирование описания модели трассируемого поля, запись и чтение из базы данных.

7. Ввод описания путей (ОП), соединяющих между собой объекты дорожной сети.

8. Редактирование описания цепей, запись и чтение из базы данных.

9. Преобразование списка путей.

10. Размещение элементов на плоскости.

11. Подготовка модели трассируемого поля.

12. Сортировка списка путей.

13. Запись и чтение списка путей из базы данных.

14. Трассировка соединений между объектами трассы. Общая задача трассировки формулируется следующим образом: по входному описанию ОП, содержащему n координат точек начала и конца трасс, определить дополнительные m координат промежуточных точек перегиба трасс таким образом, чтобы ни одна точка трассы не проходила через ранее занятую ячейку модели трассируемого поля.

15. Редактирование, запись и чтение из базы данных PTF.

16. Вывод результатов трассировки на дисплей или графопостроитель.

Алгоритм трассировки соединений содержит следующие операции:

1). Импорт информации о дорожной сети в прикладную программу.

2). Начальные присваивания.

3). Начальные присваивания для длинной цепи.

4). Начальные присваивания для короткой цепи:

а) анализ номеров тупиков в точках начала и конца трассы. Если на модели трассируемого поля оказываются тупиковые области, то эти области помечаются соответствующими номерами и при последующих трассировках производится проверка равенства:

б) проверка интегральной загруженности областей вокруг точек начала и конца трассы.

5). Восстановление длинной цепи при трассировке без пересечений.

6). Восстановление длинной цепи при трассировке с пересечениями.

7). Определение кратчайшего пути:

а) Кратчайший путь определяется в матрице смежности графа (дискретной модели трассируемого поля).

б) Использование различных соотношений коэффициентов

позволяет получить требуемое качество трассировки.

8). Фиксация кратчайшего пути.

9). Пометка кратчайшего пути определённым цветом и экспорт этой

информации в программу MapInfo.

Рассмотрим подробнее определение кратчайшего пути:

Из ГИС, разработанной в инструментальной программе MapInfo (рис.1.1), производим экспорт таблиц с графическим наполнением: «Школы» (таблица объектов социально-образовательной сферы), «Дороги» (таблица дорожной сети округа).

Рис.1.1.

Таблицу с фоновым наполнением экспортировать нет необходимости. Экспорт таблиц должен происходить в формате DXF с обязательным переносом атрибутов объектов и ASCII DXF-файлов, для того чтобы можно было работать с ними в среде программы «Графика-01-Т».

После того как было произведено преобразование файлов «Школы» и «Дороги» из формата Tab в формат DXF приступаем к работе с прикладной программой «Графика-01-Т». В прикладной программе открываем вышеуказанные файлы и производим необходимые нам вычисления: поиск кратчайшего пути между объектами.

Рис.1.2.

1)рядом со школой, от которой ищем путь, на линии дорожной сети проставляется точка (например, школа №17);

2)другая точка проставляется также на линии дороги рядом со школой (№20) до которой необходимо найти кратчайший путь;

3) после того как была проставлена последняя точка возле объекта (школа №20) автоматически производится трассировка пути с указанием оптимального маршрута, помеченного чёрным цветом;

4) если необходимо найти расстояние между несколькими объектами, то проводится аналогичная операция с проставлением нескольких точек, но последовательно, т.е. после проведения пути между двумя точками ставится третья, затем автоматически проводится путь и т.д.

Рис.1.3.

После того как все операции по определению кратчайшего пути завершены, производится операция по сохранению полученного результата трассировки пути в файле «Дороги» формата DXF и конвертации (при помощи формата Tab) его в программу MapInfo. Файл «Школы» формата DXF обратно в MapInfo преобразовывать не нужно, так как данное покрытие в течение операции поиска оставалось без изменения и служило лишь в качестве ориентира.

Конвертация файла «Дороги» в программу MapInfo необходимо, потому что в среде прикладной программы «Графика-01-Т» невозможно представить файл «Тх» (текстовое наполнение карты) и вследствии этого не будет объективной информации о маршруте. Для сравнения два рисунка 1.2 и 1.3, где в на первом представлена информация о маршруте в «Графика-01-Т», а на втором та же информация, но с текстовым наполнением в MapInfo.

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

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