MCH, Спасибо огромное! Вы очень помогли. Подскажите, пожалуйста, какой метод используется в данном файле? Он решил задачу лучше стандартного "Поиска решения".
MCH, Спасибо огромное! Вы очень помогли. Подскажите, пожалуйста, какой метод используется в данном файле? Он решил задачу лучше стандартного "Поиска решения".AK
Подскажите, пожалуйста, какой метод используется в данном файле?
Метод описан в первом сообщении данной темы под пунктом 1. (Графическим способом) В качестве последующей оптимизации и улучшения найденного решения используется динамическое программирование (вынесено в отдельную dll)
Он решил задачу лучше стандартного "Поиска решения".
Через "Поиск решения" трудно составить линейную модель для решения задачи коммивояжера, если применять генетический метод решения, то не гарантировано будет найдено оптимальное решение, может быть найден локальный оптимум
Подскажите, пожалуйста, какой метод используется в данном файле?
Метод описан в первом сообщении данной темы под пунктом 1. (Графическим способом) В качестве последующей оптимизации и улучшения найденного решения используется динамическое программирование (вынесено в отдельную dll)
Он решил задачу лучше стандартного "Поиска решения".
Через "Поиск решения" трудно составить линейную модель для решения задачи коммивояжера, если применять генетический метод решения, то не гарантировано будет найдено оптимальное решение, может быть найден локальный оптимумMCH
MCH, спасибо за разъяснение! Мне было интересно какой результат даст расчет методом ветвей и графов, вы не сталкивались с реализацией в Excel задачи коммивояжера этим методом?
MCH, спасибо за разъяснение! Мне было интересно какой результат даст расчет методом ветвей и графов, вы не сталкивались с реализацией в Excel задачи коммивояжера этим методом?AK
в 18 сообщении я выкладывал ссылку на решение задачи коммивояжера методом ветвей и границ (МВиГ) Но на текущий момент алгоритм нуждается в оптимизации и, скорее всего, 48 городов для указанной реализации будет непосильной задачей.
в 18 сообщении я выкладывал ссылку на решение задачи коммивояжера методом ветвей и границ (МВиГ) Но на текущий момент алгоритм нуждается в оптимизации и, скорее всего, 48 городов для указанной реализации будет непосильной задачей.MCH
Для того, чтобы из замкнутого круга сделать незамкнутый, можно изменить описание графа. Путь из конечной точки в первую занулить во все остальные сделать условной бесконечностью (большим числом) В примере реализован вариант когда нужно попасть из первой точки во вторую, пройдя все остальные Код решения не менял, изменил только составленный граф.
PS: файлы для решения с помощью DLL и EXE есть по ссылке из 18го сообщения
Для того, чтобы из замкнутого круга сделать незамкнутый, можно изменить описание графа. Путь из конечной точки в первую занулить во все остальные сделать условной бесконечностью (большим числом) В примере реализован вариант когда нужно попасть из первой точки во вторую, пройдя все остальные Код решения не менял, изменил только составленный граф.
PS: файлы для решения с помощью DLL и EXE есть по ссылке из 18го сообщенияMCH
Если я все правильно понял, то данное решение подходит для "летающего" коммивояжера живущего на "плоской" планете. Т.Е. путь строится прямыми линиями а не по дорогам (которые всегда извилисты и не могут рассчитываться геометрически). А расстояния рассчитаны на плоскости по Пифагору, игнорируя тот факт, что земля круглая, а длина 1 градуса параллели на разных широтах разная.
А существует ли решение, работающее в реальных условиях? по дорогам на круглой планете? Приблизительное расстояние между точками А и Б можно рассчитать по формуле: =ACOS(SIN(РАДИАНЫ(<ШиротаА>))*SIN(РАДИАНЫ(<ШиротаБ>))+COS(РАДИАНЫ(<ШиротаА>))*COS(РАДИАНЫ(<ШиротаБ>))*COS(РАДИАНЫ(<ДолготаА>)-РАДИАНЫ(<ДолготаА>)))*6371 Где широта и долгота точек А и Б задана в градусах, а 6371 км. - это средний радиус нашей планеты. Результат - расстояние между точками в километрах.
Если говорить про коммивояжера, который перемещается по дорогам, (прикрепил образец входящих данных) есть ли у Вас алгоритм, который сможет обработать матрицу "расстояний по дорогам"?
То есть там где геометрия не работает, Где расстояние между двумя точками "туда" и "обратно" может различаться (одностороннее движение, запреты маневров...) Где между двумя рядом стоящими точками (на разных берегах реки), расстояние по дороге может составлять десятки километров... Такое возможно? И каким способом? С каким максимальным количеством точек?
Если я все правильно понял, то данное решение подходит для "летающего" коммивояжера живущего на "плоской" планете. Т.Е. путь строится прямыми линиями а не по дорогам (которые всегда извилисты и не могут рассчитываться геометрически). А расстояния рассчитаны на плоскости по Пифагору, игнорируя тот факт, что земля круглая, а длина 1 градуса параллели на разных широтах разная.
А существует ли решение, работающее в реальных условиях? по дорогам на круглой планете? Приблизительное расстояние между точками А и Б можно рассчитать по формуле: =ACOS(SIN(РАДИАНЫ(<ШиротаА>))*SIN(РАДИАНЫ(<ШиротаБ>))+COS(РАДИАНЫ(<ШиротаА>))*COS(РАДИАНЫ(<ШиротаБ>))*COS(РАДИАНЫ(<ДолготаА>)-РАДИАНЫ(<ДолготаА>)))*6371 Где широта и долгота точек А и Б задана в градусах, а 6371 км. - это средний радиус нашей планеты. Результат - расстояние между точками в километрах.
Если говорить про коммивояжера, который перемещается по дорогам, (прикрепил образец входящих данных) есть ли у Вас алгоритм, который сможет обработать матрицу "расстояний по дорогам"?
То есть там где геометрия не работает, Где расстояние между двумя точками "туда" и "обратно" может различаться (одностороннее движение, запреты маневров...) Где между двумя рядом стоящими точками (на разных берегах реки), расстояние по дороге может составлять десятки километров... Такое возможно? И каким способом? С каким максимальным количеством точек?Eger
А расстояния рассчитаны на плоскости по Пифагору, игнорируя тот факт, что земля круглая, а длина 1 градуса параллели на разных широтах разная.
Прочтите тему сначала внимательно, и смотрите вложения. Тут есть решения как геометрически, так и по справочнику расстояний. Например в моем посте №16 - подредактированный код Михаила из 14-го поста. Там как раз сделано по матрице расстояний (кстати в Вашем вложении этот же файл)- подставьте реальные расстояния в матрицу смежности - получите реальные цифры Добавлено: График нужен только для наглядности - и строится как раз линейно по координатам.
А расстояния рассчитаны на плоскости по Пифагору, игнорируя тот факт, что земля круглая, а длина 1 градуса параллели на разных широтах разная.
Прочтите тему сначала внимательно, и смотрите вложения. Тут есть решения как геометрически, так и по справочнику расстояний. Например в моем посте №16 - подредактированный код Михаила из 14-го поста. Там как раз сделано по матрице расстояний (кстати в Вашем вложении этот же файл)- подставьте реальные расстояния в матрицу смежности - получите реальные цифры Добавлено: График нужен только для наглядности - и строится как раз линейно по координатам.SLAVICK
Реализовал алгоритм решения задачи коммивояжера для задач больше чем 20-25 городов Отказался от графического метода. В основе алгоритма, построение нескольких разных маршрутов и их оптимизация, с выбором лучшего решения К реализации подтолкнула данная статья: https://habr.com/ru/post/335016/ В качестве оптимизации используется 2-opt оптимизация и 3-opt оптимизация (с моей их интерпретацией), плюс дополнительные методы. Алгоритм реализованный на чистом VBA для задачи не более 100 городов отрабатывает за секунды, находит или оптимальный маршрут или очень близкий к нему для 200 городов - время исчисляется минутами 500 - 1000 городов - существенно дольше. Также перенес код в Freebasic, что дало ускорение в разы (пока еще не задействовал потоки, это еще ускорит расчет). Указанный метод можно применять как для замкнутого, так и не замкнутого маршрута. Т.к. не используется графический способ, то можно вместо координат подставлять матрицу расстояний между городами, задача должна быть симметричной.
Примеры задач и их решения во вложении, можно менять настройки от минимальных (решение находится очень быстро, но как правило не оптимальное), до более сложных.
Реализовал алгоритм решения задачи коммивояжера для задач больше чем 20-25 городов Отказался от графического метода. В основе алгоритма, построение нескольких разных маршрутов и их оптимизация, с выбором лучшего решения К реализации подтолкнула данная статья: https://habr.com/ru/post/335016/ В качестве оптимизации используется 2-opt оптимизация и 3-opt оптимизация (с моей их интерпретацией), плюс дополнительные методы. Алгоритм реализованный на чистом VBA для задачи не более 100 городов отрабатывает за секунды, находит или оптимальный маршрут или очень близкий к нему для 200 городов - время исчисляется минутами 500 - 1000 городов - существенно дольше. Также перенес код в Freebasic, что дало ускорение в разы (пока еще не задействовал потоки, это еще ускорит расчет). Указанный метод можно применять как для замкнутого, так и не замкнутого маршрута. Т.к. не используется графический способ, то можно вместо координат подставлять матрицу расстояний между городами, задача должна быть симметричной.
Примеры задач и их решения во вложении, можно менять настройки от минимальных (решение находится очень быстро, но как правило не оптимальное), до более сложных.MCH
Сделал решение для асимметричной задачи коммивояжера: https://disk.yandex.ru/d/KnuXjffBuq6xwA Результаты выдает приемлемые. На VBA считает не очень быстро, можно применять для задач до 100 городов
Сделал решение для асимметричной задачи коммивояжера: https://disk.yandex.ru/d/KnuXjffBuq6xwA Результаты выдает приемлемые. На VBA считает не очень быстро, можно применять для задач до 100 городовMCH
С обеда изучаю ваши фалы и пытаюсь сделать свое но никак не получается ввиду того что у меня двоичный массив примерно на 500x500 значении. У каждой точки координаты, и нужно вычислить расстояние между точками вот на этом застрял. Задача найти самые близкие точки. Файл с коммивояжерами не подходит, так как не показывает расстояние между точками. Помогите пжл решить данную задачу. Заранее спасибо!
С обеда изучаю ваши фалы и пытаюсь сделать свое но никак не получается ввиду того что у меня двоичный массив примерно на 500x500 значении. У каждой точки координаты, и нужно вычислить расстояние между точками вот на этом застрял. Задача найти самые близкие точки. Файл с коммивояжерами не подходит, так как не показывает расстояние между точками. Помогите пжл решить данную задачу. Заранее спасибо!dadade
MCH, О, отлично, супер!!! Да, у меня есть формула для подсчета расстояние, но только проблема в том что я никак не мог заполнить все ячейки. Это получается, когда тянешь направо, $ (доллары) надо ставить в одном месте, а когда тянешь вниз $ надо переставлять. Как это вы так быстро поменяли $ местами, вы же не меняли руками 500 столбцов?) Для этого есть шорткат клавиши? Следующий шаг, надо найти самые ближайшие к друг другу точки, между точками в верт. и гориз. столбцах. Как можно это быстро сделать, есть формула?
MCH, О, отлично, супер!!! Да, у меня есть формула для подсчета расстояние, но только проблема в том что я никак не мог заполнить все ячейки. Это получается, когда тянешь направо, $ (доллары) надо ставить в одном месте, а когда тянешь вниз $ надо переставлять. Как это вы так быстро поменяли $ местами, вы же не меняли руками 500 столбцов?) Для этого есть шорткат клавиши? Следующий шаг, надо найти самые ближайшие к друг другу точки, между точками в верт. и гориз. столбцах. Как можно это быстро сделать, есть формула?dadade
Следующий шаг, надо найти самые ближайшие к друг другу точки, между точками в верт. и гориз. столбцах.
Ваш вопрос не относится к задаче коммивояжера, поэтому лучше создать отдельную тему и там задать вопрос. На вскидку, задача решается функциями МИН() и ПОИСКПОЗ()
Следующий шаг, надо найти самые ближайшие к друг другу точки, между точками в верт. и гориз. столбцах.
Ваш вопрос не относится к задаче коммивояжера, поэтому лучше создать отдельную тему и там задать вопрос. На вскидку, задача решается функциями МИН() и ПОИСКПОЗ()MCH
MCH, что насчет вот этой части вопроса, можно узнать как было это сделано?
Да, у меня есть формула для подсчета расстояние, но только проблема в том что я никак не мог заполнить все ячейки. Это получается, когда тянешь направо, $ (доллары) надо ставить в одном месте, а когда тянешь вниз $ надо переставлять. Как это вы так быстро поменяли $ местами, вы же не меняли руками 500 столбцов?) Для этого есть шорткат клавиши?
MCH, что насчет вот этой части вопроса, можно узнать как было это сделано?
Да, у меня есть формула для подсчета расстояние, но только проблема в том что я никак не мог заполнить все ячейки. Это получается, когда тянешь направо, $ (доллары) надо ставить в одном месте, а когда тянешь вниз $ надо переставлять. Как это вы так быстро поменяли $ местами, вы же не меняли руками 500 столбцов?) Для этого есть шорткат клавиши?dadade
Прошу направить решение усложнённой задачи коммивояжера. Есть 80 точек на плоскости, из них 20 нужно посещать через день, остальные - раз в неделю. Время на каждой точке Х минут. Опорная точка одна - из нее выезжаем и возвращаемся каждый день. Список точек для примера в эксель. Как распределить точки по маршрутам по критерию а) минимального общего расстояния и б) минимального общего времени , не более Y часов в день?
Видится путь распределения точек по группам близости, где в каждой группе будут приоритетные точки и неприоритетные. Перебором не решить.
Прошу направить решение усложнённой задачи коммивояжера. Есть 80 точек на плоскости, из них 20 нужно посещать через день, остальные - раз в неделю. Время на каждой точке Х минут. Опорная точка одна - из нее выезжаем и возвращаемся каждый день. Список точек для примера в эксель. Как распределить точки по маршрутам по критерию а) минимального общего расстояния и б) минимального общего времени , не более Y часов в день?
Видится путь распределения точек по группам близости, где в каждой группе будут приоритетные точки и неприоритетные. Перебором не решить.analitolog
Вход
Регистрация
Напомнить пароль
Автосумма
Часто используемые
ВПР
ЕСЛИ
СУММЕСЛИ
Финансовые
Логические
Текстовые
Даты и времени 
Ссылки и массивы 
Математические
Другие функции
Проверка свойств и значений
Баз данных
Математические
Обработки массивов
Обработки строк
Преобразования типов данных 
Загрузки данных
Работы с файлами
Обработки системных параметров
Обработки цвета
Работы с датами и временем
Преобразования в системы счисления
Финансовые
