Домашняя страница Undo Do New Save Карта сайта Обратная связь Поиск по форуму
МИР MS EXCEL - Гость.xls

Вход

Регистрация

Напомнить пароль

 

= Мир MS Excel/Нахождение кратчайших путей из одной точки в другую (Графы) - Мир MS Excel

Старая форма входа
  • Страница 1 из 1
  • 1
Модератор форума: _Boroda_, китин  
Мир MS Excel » Вопросы и решения » Готовые решения » Нахождение кратчайших путей из одной точки в другую (Графы) (Excel)
Нахождение кратчайших путей из одной точки в другую (Графы)
MCH Дата: Четверг, 10.10.2013, 13:52 | Сообщение № 1
Группа: Админы
Ранг: Старожил
Сообщений: 2002
Репутация: 751 ±
Замечаний: ±

Реализация на VBA алгоритма Форда-Беллмана, алгоритма Дейкстры и алгоритма Левита, по нахождению кратчайших путей
Исходная тема с решением находится здесь: http://www.planetaexcel.ru/forum....lt=edit

Постарался детально прокомментировать код, чтобы было понятно
Описание алгоритмов, по которым делал решение, взял здесь: http://e-maxx.ru/algo/

Решение сделал с помощью UDF, т.к. UDF возвращает массив, то невсегда будет удобно использовать ее в таком виде, но это легко исправляется макросом, который выводит результат в нужное место и в нужном виде.

Решение Дейкстрой и Левитом находятся в одном файле, т.к. исходные данные (описание графа) одинаковое, и подход к решению очень похожий
Граф в решении Форда-Беллмана хранит не матрицу смежности вершин, а описание ребер графа.
К сообщению приложен файл: DijkstraLevitFo.rar (43.8 Kb)
 
Ответить
СообщениеРеализация на VBA алгоритма Форда-Беллмана, алгоритма Дейкстры и алгоритма Левита, по нахождению кратчайших путей
Исходная тема с решением находится здесь: http://www.planetaexcel.ru/forum....lt=edit

Постарался детально прокомментировать код, чтобы было понятно
Описание алгоритмов, по которым делал решение, взял здесь: http://e-maxx.ru/algo/

Решение сделал с помощью UDF, т.к. UDF возвращает массив, то невсегда будет удобно использовать ее в таком виде, но это легко исправляется макросом, который выводит результат в нужное место и в нужном виде.

Решение Дейкстрой и Левитом находятся в одном файле, т.к. исходные данные (описание графа) одинаковое, и подход к решению очень похожий
Граф в решении Форда-Беллмана хранит не матрицу смежности вершин, а описание ребер графа.

Автор - MCH
Дата добавления - 10.10.2013 в 13:52
MCH Дата: Суббота, 12.10.2013, 11:22 | Сообщение № 2
Группа: Админы
Ранг: Старожил
Сообщений: 2002
Репутация: 751 ±
Замечаний: ±

Сделал еще одну реализацию - алгоритм Дейкстры для разреженного графа
Протестировал на реальных данных, данные взял здесь (New York City)
Количество точек - 264346
Количество ребер - 733846

Стандартный алгоритм Дейкстры "вешается", не дождался расчтов, оно и понятно асимптотика алгоритма O(n2 + m)

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

Файл находится здесь (внимание, размер 10 МБ)

ЗЫ: В данной рализации изменил формат хранния графа на листе, не в виде матрицы смежности, а описанием ребер: окуда, куда, расстояние
ЗЗЫ: У кого-нибуть есть реальные данные по описанию расстояний по карте России? хотелось бы потестировать


Сообщение отредактировал MCH - Суббота, 12.10.2013, 11:30
 
Ответить
СообщениеСделал еще одну реализацию - алгоритм Дейкстры для разреженного графа
Протестировал на реальных данных, данные взял здесь (New York City)
Количество точек - 264346
Количество ребер - 733846

Стандартный алгоритм Дейкстры "вешается", не дождался расчтов, оно и понятно асимптотика алгоритма O(n2 + m)

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

Файл находится здесь (внимание, размер 10 МБ)

ЗЫ: В данной рализации изменил формат хранния графа на листе, не в виде матрицы смежности, а описанием ребер: окуда, куда, расстояние
ЗЗЫ: У кого-нибуть есть реальные данные по описанию расстояний по карте России? хотелось бы потестировать

Автор - MCH
Дата добавления - 12.10.2013 в 11:22
Мир MS Excel » Вопросы и решения » Готовые решения » Нахождение кратчайших путей из одной точки в другую (Графы) (Excel)
  • Страница 1 из 1
  • 1
Поиск:

Яндекс.Метрика Яндекс цитирования
© 2010-2024 · Дизайн: MichaelCH · Хостинг от uCoz · При использовании материалов сайта, ссылка на www.excelworld.ru обязательна!