Предлагаю - Проект: Использование квантовых вычислений для поиска кратчайшего пути (Q-ROUTE)
В данной работе предложен новый подход нахождения кратчайшего маршрута на графе дорог.
Цель решения проблемы:Одной из самых сложных задач, встающей перед автомобилистами, является построение оптимального маршрута по карте дорог. На сегодняшний день данная задача решается не полностью при помощи существующих устройств, т.к. они не учитывают различные метрики, влияющие на время прохождения маршрута. Цель разработки – ускорение вычисления кратчайшего пути за счет использования квантовых вычислений.
Конкурентные преимущества:Вся карта на требуемом промежутке представляется в виде ориентированного графа дорог. Граф дорог представляет собой набор метрически и топологически связанных вершин и дуг, которые точно передают направление движения, расстояние и связи между перекрестками и развязками. Направление дуг означает направленность движения потока, вершины графа или узлы – перекрестки и развязки. Каждой дуге присваивается вес, рассчитанный на основе метрик. Метрики выбираются на этапе построения графа, например минимальное количество левых поворотов, лучшее качество дороги, наивысшая возможная скорость, минимальное количество светофоров и т.п.
Повышается актуальность информации о маршрутах за счет обновления графа дорог при каждом запросе оптимального пути. К примеру, изменить дорожную ситуацию могут ремонтные работы, аварии, блокирование движения во время массовых мероприятий и др. Постоянное обновление графа дорог для запрашиваемого участка позволит генерировать оптимальный маршрут в данный момент времени и этот маршрут не потеряет актуальность до следующего обновления графа дорог.
Под обновлением графа дорог понимается пересчет весов дуг графа. Перестраивать граф полностью при каждом запросе не имеет смысла, т. к. положение дорог на карте, их направление и связи на перекрестках и развязках остаются неизменными на протяжении достаточно длительного промежутка времени. Обновление весов графа позволяет проследить все нюансы изменения дорожной сети и позволяет использовать постоянный граф дорог.
Этот подход основан на теории графов и использует основные принципы квантовых вычислений. Одним из многочисленных преимуществ квантовых вычислений является высокое быстродействие при выполнении параллельных операций. Предложенный подход позволяет находить несколько возможных путей одновременно и выбирать оптимальный маршрут на основе специальных метрик и параметров.