Особенности проектирования приложения для поиска маршрута в корпусах университета

Вопрос поиска необходимого кабинета является довольно острой проблемой в университете, особенно для новых студентов или гостей. Не всегда понятно  где находится определённый кабинет.

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

Задачи:

• Сравнительный анализ средств навигации
• Обоснование и выбор алгоритма поиска кратчайшего пути
• Адаптация алгоритмов и методик навигации, расчёта длин путей

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

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

В части подхода к выбору алгоритма расчета проложения маршрута следует выделить следующие варианты: Дейкстры, Левита, Йена, Флойда - Уоршелла, Дейкстры – Грибова,  Форда-Беллмана, Джонсона. Из всех алгоритмов на практике проще реализовывается алгоритм Дейкстры. Также он имеет преимущество, так как нет необходимости работать с отрицательным весом дуг. Сложность алгоритма составляет O(n^2 + m), где  n – количество вершин графа, m - количество ребер графа. По сложности алгоритм Левита(O(n*m))  превосходит алгоритм Дейкстры, но уступает в том, что некоторые вершины обрабатываются повторно. Особенностью является многоэтапное применение алгоритма, а именно: на первом этапе производится поиск маршрута между корпусами, на следующих этапах – поиск маршрутов внутри корпуса.

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