Публикации по теме 'traveling-salesman'
Задача коммивояжера (TSP) — это классическая задача оптимизации, в которой требуется найти кратчайший возможный маршрут, проходящий через множество…
Вот код вышеупомянутого алгоритма.
Вот результат.
def SA(initial_path, problem, Tm = 1000, iter_max = 10000,cooling_factor=0.999):
path = initial_path.copy()
cost = tour_cost(path,problem=problem)
global intermediate_costs
intermediate_costs.append(cost)
global intermediate_tempr
intermediate_tempr.append(Tm)
n = len(initial_path)
for i in range(1,iter_max):
two_indices = random.sample(range(1,n),2)
next_path = path.copy()
#..
Вопросы по теме 'traveling-salesman'
Какой подход обеспечивает более короткий путь к проблеме TSP: ближайший сосед или генетические алгоритмы?
За последние несколько дней я заметил несколько Интернета сайты , демонстрирующие решение TS с использованием генетических алгоритмов.
Какой подход обеспечивает более короткий путь к проблеме TSP: ближайший сосед или генетические алгоритмы?
1709 просмотров
schedule
18.12.2022
Пример коммивояжера с известным глобальным оптимумом
Я создал меметический алгоритм на Python для задачи коммивояжера . Однако во всех тестовых данных (список расстояний между городами), с которыми я столкнулся, отсутствует информация о лучшем решении, поэтому я не могу знать, насколько близок мой...
4707 просмотров
schedule
29.12.2023
Является ли эта задача NP-сложной?
Я пытаюсь придумать разумный алгоритм для этой проблемы:
Допустим, у вас есть куча мячей. Каждый шар имеет как минимум один цвет, но может быть и разноцветным. На каждом шаре также есть номер. Есть также куча коробок, каждая из которых только...
1605 просмотров
schedule
10.09.2023
Определение оптимальной стоимости решения для коммивояжера
Я работаю над этой проблемой:
TSP:
Input: A matrix of distances; a budget b
Output: A tour which passes through all the cities and has length <= b,
if such a tour exists.
TSP-OPT
Input: A matrix of distances
Output: The shortest tour which...
4598 просмотров
schedule
06.05.2023
Библиотека коммивояжера с использованием алгоритма аппроксимации
В настоящее время я делаю проект, который требует быстрого решения TSP (около 50-100 узлов за 2 секунды). Существует множество алгоритмов аппроксимации, но у меня нет ни времени, ни желания анализировать их и кодировать самостоятельно.
Существуют...
3117 просмотров
schedule
13.01.2023
Выбор между подходом грубой силы и параллельными потоками
У меня вопрос по графикам. Рассмотрим граф с узлами и ребрами, каждое ребро имеет свою стоимость. Задача состоит в том, чтобы посетить все узлы так, чтобы сумма затрат на пройденные ребра была наименьшей (думаю, задача коммивояжера).
Какой подход...
741 просмотров
schedule
27.06.2022
Реализация ветвей и привязок для TSP в Java
Интересно, есть ли полезная Java-реализация алгоритма ветвей и границ для TSP или вообще инфраструктура OR, которая включает BnB для TSP.
Спасибо за вашу помощь!
Марко
5585 просмотров
schedule
01.07.2022
Использование очереди для решения TSP (Branch and Bound)
Я работаю над алгоритмом ветвей и границ для задачи коммивояжера и столкнулся с небольшой заминкой. Я использую довольно стандартную очередь с узлами, представляющими подмножества вершин (путей). Я почти уверен, что у меня все получилось, но на...
2112 просмотров
schedule
22.07.2022
Проблема коммивояжера с дополнительным частичным заказом
Я ищу название этой проблемы или какие-либо сведения о алгоритме или исходном коде :
Пример: вы хотите найти лучший маршрут для посещения 100 крупнейших городов США (классический TSP), но прежде чем вы сможете посетить какой-либо конкретный...
1607 просмотров
schedule
25.12.2021
Упрощенный коммивояжер на Прологе
Я просмотрел похожие вопросы, но не могу найти ничего, что имело бы отношение к моей проблеме. Я изо всех сил пытаюсь найти алгоритм или набор «циклов», которые найдут путь от CityA до CityB , используя базу данных...
7944 просмотров
schedule
30.05.2023
Matlab: удаление избыточных сдвинутых записей матрицы
У меня есть проблема, которую мне нужно решить, но я не могу придумать более легкого и более важного: быстрого решения. Это немного похоже на часть задачи о нескольких коммивояжёрах.
Сначала у меня есть матрица с X строками и N столбцами, N...
217 просмотров
schedule
23.04.2022
Фитнес-функция в генетическом алгоритме для коммивояжера
Я пытаюсь написать генетический алгоритм для задачи коммивояжера (TSP). Для выбора я использую функцию выбора колеса рулетки: http://www.edc.ncl.ac.uk/highlight/rhjanuary2007g02.php/
По сути, это означает, что вероятность быть выбранным для...
8010 просмотров
schedule
01.07.2022
Алгоритм Палмера для гамильтоновых циклов
В «плотном» графе я пытаюсь построить гамильтонов цикл, используя алгоритм Палмера . Однако мне нужно больше пояснений по этому алгоритму, потому что он не работает со мной, когда я его реализую. Кажется, что в объяснении Википедии есть неясная...
972 просмотров
schedule
05.08.2023
неориентированный граф коммивояжера python tsp
В других сообщениях Networkx предлагался как «мой друг». Но, похоже, нет готовой к использованию функции для определенного решения проблемы TSP. т.е. Создание неориентированных графиков в Python
У меня есть неориентированный граф, все...
3452 просмотров
schedule
07.12.2022
Получение фитнеса в TSP
Я использую генетический алгоритм (GA) для оптимизации задачи коммивояжера (TSP). Моя проблема в том, как я рассчитываю физическую форму человека. Очевидно, что решения с более короткими маршрутами подходят лучше, но как именно мне назначить...
2622 просмотров
schedule
19.12.2022
A * поиск Java - TSP
Возможный дубликат: реализация A Алгоритм Star (A*) в Java
Для задания мне нужно реализовать некоторые алгоритмы поиска, чтобы решить задачу коммивояжера, я понимаю проблему и понимаю, как работает алгоритм, я просто не знаю, как это...
1939 просмотров
schedule
05.08.2022
Алгоритм перечисления гамильтоновых циклов полного графа (перестановки, в которых не учитываются циклы, реверсы, переходы или повторы)
Я хочу сгенерировать все гамильтоновы циклы полного неориентированного графа (перестановки набора, в которых петли и реверсы считаются дубликатами и не учитываются).
Например, перестановки {1,2,3}
Стандартные перестановки:
1,2,3
1,3,2
2,1,3...
1495 просмотров
schedule
16.02.2023
Коммивояжер с ограничением по времени
Я пытаюсь сделать приложение для расчета ежедневного маршрута для посещения моих клиентов. Пока я могу решить полностью с помощью генетических алгоритмов. Но мне нужно ограничить решение расстоянием. Когда я просто «обрезаю» путь решения в...
1428 просмотров
schedule
31.07.2022
Алгоритм минимизации времени в пути
Я ищу руководство по созданию алгоритма для минимизации общего времени в пути для группы путешественников, чтобы добраться до группы фиксированных пунктов назначения. Не все путешественники начинают в одном и том же месте, но каждый пункт назначения...
2249 просмотров
schedule
14.05.2022
Является ли этот MSP экземпляром TSP?
В своей книге Руководство по проектированию алгоритмов Стивен С. Скиена ставит следующую проблему:
Теперь рассмотрим следующую задачу планирования. Представьте, что вы востребованный актер, которому поступили предложения сняться в n...
394 просмотров
schedule
05.06.2023
