ОБОСНОВАНИЕ  ВЫБОРА  АЛГОРИТМА  ПОИСКА  ОПТИМАЛЬНОГО  ПУТИ  С  РАСЧЕТОМ  ПОКАЗАТЕЛЕЙ  СВЕТОФОРА  В  ГОРОДСКОЙ  СЕТИ

Сундетов  Рустем  Нурланович

сениор-лектор  кафедры  вычислительной  техники,  программного  обеспечения  и  телекоммуникаций  Международного  университета  информационных  технологий,  Республика  Казахстан,  г.  Алматы

E-mail: 

Есламгалиев  Тимур  Нурланулы

магистрант  Международного  университета  информационных  технологий,

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

E-mail:  timuryes@gmail.com

JUSTIFICATION  OF  ALGORITHM  FOR  FINDING  THE  OPTIMAL  PATH  ACCORDING  TO  TRAFFIC  LIGHTS  IN  THE  CITY  NETWORK

Sundetov  Rustem

senior-Lecturer,  Department  of  Computer  Science,  Software  Engineering  and  Telecommunications,  International  Information  Technologies  University,  Republic  of  Kazakhstan,  Almaty

Yeslamgaliyev  Timur

master  student,  Department  of  Computer  Science,  Software  Engineering  and  Telecommunications,  International  Information  Technologies  University,  Republic  of  Kazakhstan,  Almaty

АННОТАЦИЯ

В  статье  ставится  задача  анализа  различных  алгоритмов,  связанных  с  графами,  и  нахождения  решения  поиска  оптимального  пути,  учитывая  показатели  светофора  в  городской  сети.  Рассматриваются  алгоритмы  Дейкстры,  Флойда–Уоршелла,  Беллмана–Форда,  а  также  бэктрекинга.  В  результате  анализа  на  основе  сложности  алгоритма,  его  реализации,  бэктрекинг  является  самым  подходящим  решением  в  поставленной  задаче.

ABSTRACT

The  purpose  of  this  article  is  to  analyze  different  algorithms  related  to  graph  theory  and  identifying  the  most  suitable  one  for  finding  the  optimal  path  according  to  traffic  lights  in  the  city  network.  Algorithms  of  Dijkstra,  Floyd–Warshall,  Bellman–Ford  and  backtracking  are  being  considered.  Results  show  that  backtracking  algorithm  is  the  most  appropriate  solution  for  the  task  according  to  algorithm’s  time  complexity  and  implementation.

Ключевые  слова:  теория  графов;  бэктрекинг;  алгоритм  в  ширину;  алгоритм  Дейкстры;  алгоритм  Флойда–Уоршелла;  алгоритм  Беллман–Форда. 

Keywords:  graph  theory;  backtracking;  depth-first  search;  Dijktra’s  algorithm;  Floyd–Warshall  algorithm;  Bellman–Ford  algorithm.

Одной  из  основных  целей  автомобильного  транспорта  в  городской  сети  дорог  является  нахождение  оптимального  пути  из  точки  А  в  точку  Б.  Под  «оптимальностью  пути»  понимается  не  минимальное  расстояние,  а  минимальная  затрата  времени  на  прохождение  пути.  Городская  сеть  дорог  может  быть  представлена  в  виде  графа  с  нижеперечисленными  параметрами:

·     граф  является  ориентированным  графом;

·     в  графе  нет  ребер  с  отрицательным  весом;

·     в  графе  большое  количество  вершин;

·     граф  находится  в  одном  компоненте  связности;

·     светофор  находится  на  каждой  вершине  графа;

·     каждое  ребро  графа  имеет  различную  длину.

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

Для  анализа  и  сравнения  алгоритмов,  удобно  начать  с  алгоритмов,  связанные  с  поиском  кратчайшего  пути.  На  данный  момент  известно  множество  различных  алгоритмов,  которые  реализованы  на  языках  программирования.  Выберем  самые  основные  алгоритмы,  такие  как  алгоритм  Дейкстры,  алгоритм  Флойда–Уоршелла,  алгоритм  Беллман–Форда,  а  также  добавим  алгоритм  бэктрекинга,  который  не  находит  кратчайшего  пути,  но  алгоритм  важен  в  поиске  пути  оптимального. 

Алгоритм  Дейкстры  придуман  нидерландским  ученым  Эдсгером  Дейкстрой  в  1959  году.  Способ  алгоритма  таков:  для  каждой  вершины  присваивается  расстояние  (так  называемый  вес),  равное  бесконечности,  кроме  вершины,  с  которой  начинается  сам  путь,  вершина  будет  равняется  нолю.  На  каждой  итерации  алгоритма  будет  прибавляться  вес  самой  вершины  плюс  вес  ребра  соседней  вершины,  если  вес  вершины  и  ребра  меньше,  чем  вес  соседней  вершины,  тогда  вес  соседней  вершины  становится  суммой  веса  ребра  и  вершина,  с  котором  соединено  ребро.  Когда  проходит  полностью  итерация  вершины  А  со  всеми  ее  соседними  вершинами  и  вычислен  новый  вес  до  соседних  вершин,  на  вершине  А  ставится  метка,  что  вершина  проверена  и  к  ней  можно  не  возвращаться  повторно.  Далее  программа  находит  вершину  с  наименьшим  весом  и  на  которой  нет  метки,  и  повторяет  все  то  же  самое.  Реализация  программы  останавливается,  когда  на  всех  вершинах  поставлены  метки.  Можно  с  легкостью  определить  расстояние  от  вершины  А  до  вершины  Б,  посмотрев,  какой  вес  стоит  у  вершины  Б.  Это  будет  ответ  для  нахождения  кратчайшего  пути  между  вершинами  А  и  Б.  Сложность  алгоритма  составляет

О(n²+m),  где  n  —  количество  вершин  и  m  —  количество  ребер.  Слабость  алгоритма  состоит  в  том,  что  он  не  всегда  работает  с  ребрами  при  отрицательном  весе  ребер,  но  в  данной  задаче  отрицательный  вес  ребер  отсутствует

Алгоритм  Беллмана–Форда  был  разработан  Ричардом  Беллманом  и  Лестером  Фордом.  Как  и  в  алгоритме  Дейкстры,  изначальные  данные  весов  всех  вершин  являются  бесконечными,  кроме  вершины,  с  которой  начинается  сам  путь.  Далее  на  каждой  итерации  проверяется  накопленный  вес  самой  вершины  плюс  вес  всех  соседних  вершин,  если  вес  ребра  и  вершины  меньше  соседней  вершины,  то  вес  заменяется  на  минимальную  из  них.  Ставится  также  метка,  что  вершина  рассчитана,  чтобы  в  дальнейшем  программа  повторно  не  возвращалась  к  ней.  Алгоритм  пробегает  по  всем  вершинам  и  находит  все  возможные  веса  с  ее  соседями.  Алгоритм  Беллмана–Форда  достаточно  похож  на  алгоритм  Дейкстры.  Отличия  проявляются  в  том,  что  Беллман–Форд  может  работать  с  ребрами  отрицательного  веса,  а  Дейкстра  нет.  Самое  же  главное  отличие,  которое  дает  преимущество  Беллман–Форду  —  это  сложность  алгоритма.  Она  составляет  О(n*m),  где  n  —  количество  вершин  и  m  —  количество  ребер.  Причина  быстроты  алгоритма  по  сравнению  с  алгоритмом  Дейсктры  в  том,  что  вершины  рассматриваются  только  раз,  тогда  как  в  Дейкстре  они  рассматриваются  при  каждой  итерации  для  нахождения  минимальной  вершины,  что  дает  дополнительное  время  на  обработку  алгоритма

Алгоритм  Флойда–Уоршелла  был  опубликован  Робертом  Флойдом  и  Стивеном  Уоршеллом  в  1962  году.  Самый  легкий  по  реализации  программы  по  сравнению  с  алгоритмом  Дейкстры  и  Беллмана–Форда.  Цель  алгоритма  —  нахождение  кратчайшего  пути  между  всеми  вершинами  графа.  Дана  матрица,  которая  заполняется  весами  ребер  для  каждой  из  вершин.  Затем  проходит  итерация  каждой  вершины,  сравнивая  вес  ребра  между  вершинами  А  и  Б,  и  сравнивается  вес  ребер  между  А  и  Б  через  вершину  В.  Минимальное  из  этих  вариантов  является  ответом,  то  есть  кратчайшим  путем  между  А  и  Б.  Преимущество  алгоритма  в  простоте  его  реализации,  слабость  —  в  сложности  алгоритма.  Она  равняется  О(n³),  где  n  —  количество  вершин  графа.  Безусловно,  это  медленнее,  чем  у  Дейсктры  и  Беллмана–Форда.

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

Сложность  алгоритма  О(n*m),  где  n  —  количество  вершин  графа.  Алгоритм  эффективен  тем,  что  все  возможные  варианты  могут  быть  сохранены  в  структурах  данных  и  легко  могут  быть  использованы  в  дальнейших  расчетах  в  программе.

При  нахождение  оптимального  пути  между  вершинами  А  и  Б,  помимо  расстояния  (веса)  дорог  (ребер)  будет  использована  база  с  данными  светофора,  а  именно  —  время  для  зеленого,  желтого  и  красного  цвета.  Также  будет  учитываться  средняя  скорость  автомобиля.  В  нашей  задаче  в  поиске  оптимального  пути,  вес  графа  станет  не  расстояние,  а  время  затраченное  на  путь.  Если  попытаться  решить,  используя  алгоритмы  Дейкстры,  то  теряем  эффективность  по  обоим  параметрам:  сложности  алгоритма  и  его  реализации.  Сложность  алгоритма  Дейкстры  является  O(n²  +  m),  что  уже  проигрывает  всем  другим  алгоритмам,  кроме  Флойда-Уоршелла  и  реализация  затрудняется  тем,  что  нужно  отдельно  создавать  структуру  данных  и  контролировать  минимальное  время  на  прохождение  пути,  это  расчет  самого  пути,  время  стояние  на  светофорах  и  в  возможных  пробках.  Алгоритм  Флойда–Уоршелла  проигрывает  по  своей  сложности  алгоритма  и,  соответственно,  является  неэффективным  решением  в  данной  задаче.  Алгоритм  Беллмана-Форда  может  составить  конкуренцию  алгоритму  бэктрекинга,  так  как  сложность  алгоритма  равна,  но  проигрывает  по  своей  реализации,  так  как  нужно  будет  создавать  дополнительные  структуры  данных  и  контролировать  весь  поток  данных,  как  и  в  случае  с  Дейкстрой.  Алгоритм  бэктрекинга  решает  эту  задачу  в  эффективном  формате,  сохраняя  все  возможные  пути  в  структуре  данных,  и  с  легкостью  находит  самый  оптимальный  путь  с  учетом  данных  светофора,  сохраняя  весь  путь  в  массиве,  и  реализация  программы  несложна.

Исходя  из  результатов  анализа,  алгоритм  бэктрекинга  является  лучшим 

решением  в  поиске  оптимального  пути,  учитывая  показания  светофора  и  нагруженность  городской  сети,  по  сравнению  с  алгоритмами  Дейкстры,  Беллманна–Форда  и  Флойда–Уоршелла.

Список  литературы:

1. Коробицын  В.В.,  Фролова  Ю.В.  Моделирование  автомобильного  потока  на  перекрестке  и  определение  оптимальных  параметров  управления  сигналами  светофора:  журнал.  Выпуск  №2(14),  журнал  «Математические  структуры  и  моделирование»  —  2004  г.,  —  вып.  14,  —  с.  34—36 
2. Седжвик  Р.  Алгоритмы  на  Java:  учеб.  пособие.  Вильямс,  2012.  —  575  с.