Вопросы по теме 'traveling-salesman'
Оптимальная маршрутизация карты с помощью Google Maps
Есть ли способ с помощью API Карт Google вернуть «оптимизированный» маршрут с заданным набором путевых точек (другими словами, «достаточно хорошее» решение проблемы коммивояжера), или он всегда возвращает маршрут с точки в указанном порядке?
28264 просмотров
schedule
29.05.2023
Сильносвязный орграф минимальной стоимости
У меня есть сильно связанный орграф (т. е. существует путь от i к j и от j к i для каждой пары узлов (i, j) в графе G). Я хочу найти из этого графа сильно связный граф, у которого сумма всех ребер наименьшая.
Другими словами, мне нужно избавиться...
5266 просмотров
schedule
25.02.2023
Нециклический путь ко всем узлам
Есть ли алгоритм или набор алгоритмов, которые позволили бы вам найти кратчайшее расстояние пешком от произвольного начального узла, чтобы каждый узел посещался в весовом неориентированном графе? Это не совсем Коммивояжер, потому что меня не волнует,...
1513 просмотров
schedule
02.04.2022
Существует ли алгоритм вычисления перестановки расстояний?
Это связано с проблемой коммивояжера. Сначала необходимо сгенерировать все перестановки, а затем прикрепить пункт назначения (такой же, как источник). То есть: 1) abcd abdc ....
2) абвда абдца ....а
У меня есть все расстояния, и мне нужен...
528 просмотров
schedule
19.07.2023
Как можно решить проблему коммивояжера с помощью Google Maps?
Как практическое решение проблемы коммивояжера с помощью Google Maps / геолокации / поиска маршрута?
Мне не нужно лучшее решение, в пределах 5% было бы нормально.
Например, у меня есть 20 мест в Великобритании, которые я могу посетить в любом...
5202 просмотров
schedule
05.04.2022
Алгоритм аппроксимации для варианта TSP, фиксированные начало и конец где угодно, кроме начальной точки + несколько посещений в каждой вершине РАЗРЕШЕНО
ПРИМЕЧАНИЕ: из-за того, что поездка не заканчивается в том же месте, в котором она началась, а также из-за того, что каждую точку можно посетить более одного раза, если я все еще посещаю их все, это на самом деле не вариант TSP, но Ставлю из-за...
1709 просмотров
schedule
16.10.2023
Эволюционный алгоритм - Коммивояжер
Я пытаюсь решить эту проблему с помощью генетического алгоритма, и мне сложно выбрать фитнес-функцию. Моя проблема немного отличается от исходной задачи коммивояжера, так как население и, возможно, также выигрышная единица не обязательно содержат все...
412 просмотров
schedule
26.03.2022
Велосипедный мессенджер / ЦППД с OptaPlanner
Уважаемые специалисты OptaPlanner!
Я хотел бы использовать OptaPlanner (или аналогичную платформу Java с открытым исходным кодом) для оптимизации маршрутов для службы обмена сообщениями на велосипеде. Предположим, что 5 курьеров должны забрать 30...
2336 просмотров
schedule
12.05.2024
Чтение данных для коммивояжера С++
Мне нужно выяснить, как читать этот файл в:
48
0 3023 1942
1 6734 1453
2 2233 10
3 5530 1424
4 401 841
5 3082 1644
6 7608 4458
7 7573 3716
8 7265 1268
9 6898 1885
10 1112 2049
11 5468 2606
12 5989 2873
13 4706 2674
14 4612 2035
15 6347 2683
16...
1484 просмотров
schedule
02.05.2024
3-Opt Локальный поиск для TSP?
Я понимаю, что эвристика 3-Opt включает в себя удаление трех ребер из графика и добавление еще трех для повторного завершения тура. Однако я видел много статей, в которых упоминается, что при удалении трех ребер остается только 2 возможных способа...
7328 просмотров
schedule
25.09.2022
Беспокоюсь, если моя оптимизация муравьиной колонии просто находит путь с использованием метода ближайшего соседа
Я пытаюсь решить проблему коммивояжера, используя алгоритм оптимизации муравьиной колонии. Я прикрепил свой код к этому. Сейчас это отлично работает для всех тестовых случаев (тех, которые я тестировал) и дает правильные ответы. Но все равно меня...
446 просмотров
schedule
05.10.2022
Эвристика коммивояжера (с предопределенными границами)?
Я ищу алгоритм, который быстрее, чем экспоненциальный, который найдет ЛЮБОЙ цикл в задаче коммивояжера. Неважно, насколько плохой цикл, он просто должен быть циклом. Что мне действительно нужно, так это алгоритм для гамильтоновой схемы. Что-то, что...
113 просмотров
schedule
06.09.2023
Кроссовер генетических алгоритмов дает худшие результаты
Текущий используемый алгоритм представляет собой генетический алгоритм с использованием мутации и упорядоченного кроссовера. Мы изменили исходный алгоритм упорядоченного кроссовера, удалив депо (конечные точки), а затем выполнив кроссовер и добавив...
345 просмотров
schedule
18.06.2022
Эвристика TSP — коэффициент наихудшего случая
У меня есть некоторые проблемы с попыткой суммировать соотношение этих эвристик для наихудшего случая для метрики (это означает, что она удовлетворяет неравенству треугольника) задачи коммивояжера:
Ближайший сосед
Ближайшая вставка
Самая...
593 просмотров
schedule
14.03.2022
OpenMP — std::next_permutation
Я пытаюсь распараллелить свою собственную реализацию задачи коммивояжёра на С++ с помощью OpenMP.
У меня есть функция для расчета стоимости дороги cost() и вектора [0,1,2,...,N], где N - количество узлов дороги.
В main() я пытаюсь найти...
820 просмотров
schedule
20.02.2024
Алгоритм создания маршрута от исходного узла до конечного узла с использованием каждого узла ровно один раз
Я пытаюсь создать маршрут с учетом начального и конечного узлов, который будет перемещаться к каждому узлу в графе и минимизировать затраты на это.
Граф неориентированный, и каждый узел напрямую связан друг с другом. Вес каждого ребра...
262 просмотров
schedule
11.12.2023
Перехитрить алгоритм коммивояжера
У меня возникают трудности с построением небольшого неориентированного графа G, у которого есть взвешенные ребра, которые превосходят данный алгоритм, а это означает, что алгоритм не выберет оптимальное решение независимо от начальной точки. Каждый...
131 просмотров
schedule
26.08.2022
Алгоритм вариации коммивояжера
Мне сложно найти противоречащий пример следующей вариации задачи TSP.
Входные данные: G = (V, E) неориентированный полный граф, удовлетворяющий неравенству треугольника, w: E- ›R + весовая функция и исходная вершина s.
Выход: простой цикл...
99 просмотров
schedule
03.11.2023
Решите Коммивояжера, как только вы узнаете расстояние кратчайшего возможного маршрута
Я пытаюсь решить TSP (Travelling Salesman Problem) , но не традиционным способом. Я следую этим шагам.
1) Сначала я меняю TSP на проблему true/false .
Постановка задачи теперь такая: "Существует ли маршрут по всем городам с общим...
608 просмотров
schedule
17.05.2023
Альтернатива для словаря, позволяющего дублировать
Мне нужен альтернативный словарь, потому что нужны дубликаты. Причина в том, что мне нужно найти лучший маршрут. Для этого я, например, создаю популяцию из 20 человек. У каждого человека есть свой маршрут, и для каждого маршрута рассчитывается...
1252 просмотров
schedule
12.03.2022
