Задача коммивояжера (англ. Travelling salesman problem, сокращённо TSP) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. Тем кто с ней не знаком, можете почитать в Wikipedia Можно решать различными алгоритмами.
Реализовал пока два варианта решения: 1. Графическим (геометрическим) методом https://yadi.sk/d/Gg1Qbv26XCnkR В основе решения геометрия - наносим координаты городов на плоскость, строим выпуклый многоугольник проходящий через указанные точки, так, чтобы все точки были внутри данного многоугольника. Затем пытаемся включить в данный многоугольник новые точки с наименьшими "затратами". Присутствует эвристика, поэтому маршрут не обязательно получается оптимальным, но близок к нему. Для исключения из маршрутов образование "петель", проходим перебором близко стоящие точки полученного маршрута, пытаясь улучшить решение. К достоинствам можно отнести довольно высокую скорость нахождения пути для большого количества точек. При этом маршрут получается близким к оптимальному. К недостаткам - нет гарантии, что маршрут оптимальный, необходимость задавать координаты точек и вычислять расстояния между точками геометрическим образом, а не использовать матрицу расстояний между точками (которая не обязательно должна быть симметричной)
2. Полным перебором (см. вложение) - можно применять не более чем для 12 городов (придется перебирать 11! вариантов маршрутов, это примерно 40 млн вариантов). Увеличение количество городов более 12 приводит к существенному увеличению времени расчетов и уже не оправдано.
Если получится, то в планах решить задачу коммивояжера методом Литтла (как частный случай метода ветвей и границ). Материала по описанию данного метода нашел много, но как то все в голове пока не укладывается.
Задача коммивояжера (англ. Travelling salesman problem, сокращённо TSP) — одна из самых известных задач комбинаторной оптимизации, заключающаяся в отыскании самого выгодного маршрута, проходящего через указанные города хотя бы по одному разу с последующим возвратом в исходный город. Тем кто с ней не знаком, можете почитать в Wikipedia Можно решать различными алгоритмами.
Реализовал пока два варианта решения: 1. Графическим (геометрическим) методом https://yadi.sk/d/Gg1Qbv26XCnkR В основе решения геометрия - наносим координаты городов на плоскость, строим выпуклый многоугольник проходящий через указанные точки, так, чтобы все точки были внутри данного многоугольника. Затем пытаемся включить в данный многоугольник новые точки с наименьшими "затратами". Присутствует эвристика, поэтому маршрут не обязательно получается оптимальным, но близок к нему. Для исключения из маршрутов образование "петель", проходим перебором близко стоящие точки полученного маршрута, пытаясь улучшить решение. К достоинствам можно отнести довольно высокую скорость нахождения пути для большого количества точек. При этом маршрут получается близким к оптимальному. К недостаткам - нет гарантии, что маршрут оптимальный, необходимость задавать координаты точек и вычислять расстояния между точками геометрическим образом, а не использовать матрицу расстояний между точками (которая не обязательно должна быть симметричной)
2. Полным перебором (см. вложение) - можно применять не более чем для 12 городов (придется перебирать 11! вариантов маршрутов, это примерно 40 млн вариантов). Увеличение количество городов более 12 приводит к существенному увеличению времени расчетов и уже не оправдано.
Если получится, то в планах решить задачу коммивояжера методом Литтла (как частный случай метода ветвей и границ). Материала по описанию данного метода нашел много, но как то все в голове пока не укладывается.MCH
Решение перебором обновил, избавился от генерации массива перестановок, генерирую их циклом, с помощью алгоритма Нарайаны. Это позволило избавиться от выделения памяти для хранения массива с перестановками, а также ускорить решение более чем в два раза.
Решение перебором обновил, избавился от генерации массива перестановок, генерирую их циклом, с помощью алгоритма Нарайаны. Это позволило избавиться от выделения памяти для хранения массива с перестановками, а также ускорить решение более чем в два раза.MCH
Посмотрел вложение, это какая-то легкая наркомания, автор как ты это вообще придумал?) Решал такое на *корпоративном тесте способностей персонала* в одной из компаний с годовой выручкой 1млрд+$, тут даже близко никто так не оптимизировал
Посмотрел вложение, это какая-то легкая наркомания, автор как ты это вообще придумал?) Решал такое на *корпоративном тесте способностей персонала* в одной из компаний с годовой выручкой 1млрд+$, тут даже близко никто так не оптимизировал Desmont
Дополнил решение задачи коммивояжера методом динамического программирования. Можно использовать до 20 городов. Решение находится относительно быстро.
Дополнил решение задачи коммивояжера методом динамического программирования. Можно использовать до 20 городов. Решение находится относительно быстро.MCH
Я просчитал для 24 городов - заменил MOD и типы на double. Просчет занял 25 мин. Много времени ушло на создание массивов. Комп "завис" на несколько минут. (ОС 64 бит)
А вот для 25 не хватило памяти : для 24 создается 2 Массива: 16 777 215 x 24. а для 25 нужны массивы : 33 554 431 х 25.
Может можно без них - с временными массивами? Или это невозможно?
Я просчитал для 24 городов - заменил MOD и типы на double. Просчет занял 25 мин. Много времени ушло на создание массивов. Комп "завис" на несколько минут. (ОС 64 бит)
А вот для 25 не хватило памяти : для 24 создается 2 Массива: 16 777 215 x 24. а для 25 нужны массивы : 33 554 431 х 25.
Может можно без них - с временными массивами? Или это невозможно?SLAVICK
Если маршруты целочисленные, то для экономии памяти можно объявлять первый массив как Long. Второй массив можно объявить как Byte, все равно там хранятся числа не более 255 (не более 25). От второго массива, наверное, можно избавиться и восстанавливать маршрут расчетным путем.
Если маршруты целочисленные, то для экономии памяти можно объявлять первый массив как Long. Второй массив можно объявить как Byte, все равно там хранятся числа не более 255 (не более 25). От второго массива, наверное, можно избавиться и восстанавливать маршрут расчетным путем.MCH
Пока я не совсем разобрался с алгоритмом. Времени сейчас не хватает Я думал создать одномерный массив 1...n(количество точек) и перезаписывать в него данные по маршруту. Если это возможно. Я наверное не учел что
второй массив, который запоминает оптимального предка для каждого состояния
пойду разбирать механизм дальше А может ссылку дадите на мат часть? Расчетным путем это формулами? как раньше в версии "brute"?. Может так и лучше. Выполнение немного замедлится, но можно просчитать больше.
Пока я не совсем разобрался с алгоритмом. Времени сейчас не хватает Я думал создать одномерный массив 1...n(количество точек) и перезаписывать в него данные по маршруту. Если это возможно. Я наверное не учел что
второй массив, который запоминает оптимального предка для каждого состояния
пойду разбирать механизм дальше А может ссылку дадите на мат часть? Расчетным путем это формулами? как раньше в версии "brute"?. Может так и лучше. Выполнение немного замедлится, но можно просчитать больше.SLAVICK
Иногда все проще чем кажется с первого взгляда.
Сообщение отредактировал SLAVICK - Понедельник, 06.10.2014, 13:18
Расчетным путем это формулами? как раньше в версии "brute"?.
Не совсем так. По завершению алгоритма мы вычисляем длину оптимальнго маршрута и знаем из какго последнего состояния в него попали, но при этом не знаем последовательность точек. Для того, чтобы определить всю цепочку нужно будет поочередно перепроверять каждый элемент и определять предка. В процессе вычисления предки запоминаются. Поэтому последовательно восстанавливается простым циклом. Если не запоминать предков, то с вычислением могут быть трудности, которые упираютя в стандарт вычислений с плавающей точкой (например, если a=0.1, b=a+4, c=b-4 то при этом a<>c)
Расчетным путем это формулами? как раньше в версии "brute"?.
Не совсем так. По завершению алгоритма мы вычисляем длину оптимальнго маршрута и знаем из какго последнего состояния в него попали, но при этом не знаем последовательность точек. Для того, чтобы определить всю цепочку нужно будет поочередно перепроверять каждый элемент и определять предка. В процессе вычисления предки запоминаются. Поэтому последовательно восстанавливается простым циклом. Если не запоминать предков, то с вычислением могут быть трудности, которые упираютя в стандарт вычислений с плавающей точкой (например, если a=0.1, b=a+4, c=b-4 то при этом a<>c)MCH
Реализовал другой метод решения задачи коммивояжера динамическим программированием. Описание метода взял здесь: https://revolution.allbest.ru/programming/00555478_0.html Реализовал самостоятельно, так как понял (возможно не совсем оптимально, будет над чем подумать, чтобы оптимизировать).
Отличия от предыдущей реализации: 1. Использован тип Long, для хранения данных и уменьшения размера объявляемых массивов, что позволило немного увеличить максимальное число городов. 2. Перенес алгоритм на FreeBasic (из VBA переносится в FB достаточно легко), реализовал все это в виде dll, которую можно подключить к Excel файлу, передавать в dll модель и решить ее, скорость решения значительно увеличилась, 20 городов у меня решается менее чем за 1 секунду 3. Отдельно скомпилировал решатель в виде exe файла, данные (матрицу) можно заносить в текстовый файл "problem.dat", решение сохраняется также в текстовый файл
Во вложении пример с исходными данными на 200 точек из предыдущего поста решаемый dll (проверено в Excel 32bit) а также exe файлы под win32 и win64
Реализовал другой метод решения задачи коммивояжера динамическим программированием. Описание метода взял здесь: https://revolution.allbest.ru/programming/00555478_0.html Реализовал самостоятельно, так как понял (возможно не совсем оптимально, будет над чем подумать, чтобы оптимизировать).
Отличия от предыдущей реализации: 1. Использован тип Long, для хранения данных и уменьшения размера объявляемых массивов, что позволило немного увеличить максимальное число городов. 2. Перенес алгоритм на FreeBasic (из VBA переносится в FB достаточно легко), реализовал все это в виде dll, которую можно подключить к Excel файлу, передавать в dll модель и решить ее, скорость решения значительно увеличилась, 20 городов у меня решается менее чем за 1 секунду 3. Отдельно скомпилировал решатель в виде exe файла, данные (матрицу) можно заносить в текстовый файл "problem.dat", решение сохраняется также в текстовый файл
Во вложении пример с исходными данными на 200 точек из предыдущего поста решаемый dll (проверено в Excel 32bit) а также exe файлы под win32 и win64MCH
Примеры решения задачи коммивояжера динамическим программированием: 1. Два варианта функции на VBA 2. Решение с помощью DLL 3. Решение внешней программой
Примеры решения задачи коммивояжера динамическим программированием: 1. Два варианта функции на VBA 2. Решение с помощью DLL 3. Решение внешней программойMCH
MCH, как всегда на высоте - понимаю, что мне есть еще чего учить. Есть несколько пожеланий, как для готового решения: - можно сделать проверку для подключения библиотек #if VBA7 then... - так будет работать у всех. https://msdn.microsoft.com/ru-ru....4).aspx И совсем не лишним(на мой взгляд) было бы добавить вывод в ячейку время выполнения кода, чтобы глаз радовался :).
MCH, как всегда на высоте - понимаю, что мне есть еще чего учить. Есть несколько пожеланий, как для готового решения: - можно сделать проверку для подключения библиотек #if VBA7 then... - так будет работать у всех. https://msdn.microsoft.com/ru-ru....4).aspx И совсем не лишним(на мой взгляд) было бы добавить вывод в ячейку время выполнения кода, чтобы глаз радовался :).SLAVICK
Если получится, то в планах решить задачу коммивояжера методом Литтла (как частный случай метода ветвей и границ).
Реализовал на VBA метод ветвей и границ (то как его понял). Код еще сырой и нуждается в оптимизации. Для сравнения сделал в одном файле решение динамикой и МВиГ: https://yadi.sk/d/Reg-KIOE3RurPe
Ограничение для динамического программирования - 23-24 города, для МВиГ количество городов может быть и больше, но расчет может занять продолжительное время, также может не хватить памяти при рекурсивном вызове функций.
Если получится, то в планах решить задачу коммивояжера методом Литтла (как частный случай метода ветвей и границ).
Реализовал на VBA метод ветвей и границ (то как его понял). Код еще сырой и нуждается в оптимизации. Для сравнения сделал в одном файле решение динамикой и МВиГ: https://yadi.sk/d/Reg-KIOE3RurPe
Ограничение для динамического программирования - 23-24 города, для МВиГ количество городов может быть и больше, но расчет может занять продолжительное время, также может не хватить памяти при рекурсивном вызове функций.MCH
Я воспользовался вашим файлом для своего примера - 48 городов. Почему то один из городов не посещается при построении маршрута и я не смог понять, где допустил ошибку. Буду очень благодарен, если вы посмотрите.
Я воспользовался вашим файлом для своего примера - 48 городов. Почему то один из городов не посещается при построении маршрута и я не смог понять, где допустил ошибку. Буду очень благодарен, если вы посмотрите.
Почему то один из городов не посещается при построении маршрута
В коде была небольшая ошибка, исправлено во вложении, также алгоритм решения убран в dll для ускорения расчетов (будет работать только в Excel 32bit)MCH
Вход
Регистрация
Напомнить пароль
Автосумма
Часто используемые
ВПР
ЕСЛИ
СУММЕСЛИ
Финансовые
Логические
Текстовые
Даты и времени 
Ссылки и массивы 
Математические
Другие функции
Проверка свойств и значений
Баз данных
Математические
Обработки массивов
Обработки строк
Преобразования типов данных 
Загрузки данных
Работы с файлами
Обработки системных параметров
Обработки цвета
Работы с датами и временем
Преобразования в системы счисления
Финансовые
: 
