Вопросы по теме 'traveling-salesman'
задача коммивояжера, 2-опционный алгоритм реализация c #
Может ли кто-нибудь дать мне образец кода алгоритма 2-opt для задачи коммивояжера. На данный момент я использую ближайшего соседа, чтобы найти путь, но этот метод далек от совершенства, и после некоторых исследований я нашел алгоритм с двумя...
30746 просмотров
schedule
18.05.2023
Справка по алгоритму проблемы с самовывозом и доставкой
Предположим, доставка еды для нескольких ресторанов (скажем, 20). Доступно (скажем, 10) драйверов. Далее, допустим, мы получаем 100 заказов за 4 часа на доставку еды из этих ресторанов на дом.
Таким образом, водители должны координировать свои...
3137 просмотров
schedule
27.04.2022
Как реализовать шаг сокращения в алгоритме Christofides?
Я реализую алгоритм Кристофидеса для получения 3/2-аппроксимации TSP в графах, которые подчиняются неравенство треугольника. У меня уже есть код для вычисления минимального остовного дерева с использованием алгоритма Крускала и матрицы смежности....
1624 просмотров
schedule
08.03.2023
Разрешимо ли это за полиномиальное (или псевдополиномиальное) время?
Я пытаюсь придумать разумный алгоритм для этой проблемы:
Допустим, у вас есть куча мячей. Каждый шар имеет как минимум один цвет, но может быть и разноцветным. Каждый шар имеет вес и связанную с ним ценность. Есть также куча коробок, каждая из...
782 просмотров
schedule
20.03.2023
Эквивалент триангуляции Делоне для неориентированного графа
Я работаю над алгоритмом планирования пути, который эквивалентен задаче коммивояжера. Я не знаю, сколько узлов у меня может быть, поэтому я готов пожертвовать точностью ради скорости. Моя проблема может быть смоделирована как полностью связанный...
263 просмотров
schedule
06.07.2023
Алгоритм грубой силы для задачи коммивояжера в Java
Я работаю над проектом для математического класса в школе и решил заняться проблемой коммивояжера, которую я всегда хотел исследовать подробнее. Однако у меня проблемы с алгоритмом решения методом грубой силы.
* Перейдите к обновлению внизу,...
41336 просмотров
schedule
21.08.2022
2-оптовая реализация локального поиска
Я пытаюсь реализовать локальный поиск (с двумя опциями), чтобы решить проблему коммивояжера. Однако у меня возникли проблемы с правильным воссозданием полной схемы (тур по узлам). Я думаю, что мой алгоритм может быть ошибочным. Это моя реализация...
6410 просмотров
schedule
30.04.2023
Несовершенная реализация поиска с 2 вариантами ответов?
Я пытаюсь разработать эвристику локального поиска с двумя вариантами для TSP на Java, но мой алгоритм кажется ошибочным. Учитывая схему ближайшего соседа, как на входе, это каким-то образом ухудшает схему. Ближайший сосед: http://goo.gl/uI5X6 ;...
2322 просмотров
schedule
12.05.2022
Решение простой TSP с использованием Z3
Я новичок в решателях SMT. Я хотел бы знать, как я могу закодировать простую задачу TSP с 4/6 узлами? Я не понимаю, как установить свои ограничения с помощью Z3pay APA. Любой намек или помощь будут высоко оценены.
559 просмотров
schedule
29.01.2023
TSPTW с генетическим алгоритмом
Я реализую TSPTW (коммивояжер с временным окном) с генетическим алгоритмом с 81 городом, я применил следующие шаги:
mutation prob=0.03
population size=100
-Generate random population according to the value of population size intialized
-Sort the...
794 просмотров
schedule
03.05.2024
Ищем алгоритм поиска кратчайшего пути
В основном у меня есть граф с 12 узлами (представляющими города) и 13 ребрами (представляющими маршруты).
Теперь предположим, что (случайным образом) у меня есть план посещения n узлов, отклоняясь от определенного (A). Итак ( having N <=...
1038 просмотров
schedule
15.09.2023
Каково решение для TSP с несколькими продавцами и без возврата, но с известными вершинами и конечными точками?
Я не знаю, правильно ли я это сформулировал, и я не уверен, что это проблема TSP, но вот сценарий.
Я разрабатываю и пытаюсь оптимизировать планировщик маршрутов для службы доставки. У меня есть несколько водителей (продавцов), которые забирают...
2214 просмотров
schedule
25.02.2024
Как работает линейный поиск с 2,5 оптами для TSP?
Я понимаю логику выполнения попарного обмена с двумя вариантами, чтобы два ребра не пересекались:
Просто выньте два края и замените их двумя другими. Если у вас есть список городов:
A, B, C, D, E, A , и AB и DE выбраны... тогда просто...
1023 просмотров
schedule
13.04.2022
Минимальное расстояние между началом и концом при прохождении обязательных точек в лабиринте
Итак, предположим, у меня есть лабиринт, у которого есть начальная и конечная точки, отмеченные оранжевым и красным соответственно, и моя цель — найти минимальное расстояние между ними. Заблокированный путь представлен черным цветом, а открытый путь...
2099 просмотров
schedule
28.12.2022
Neo4J - Коммивояжер
Я пытаюсь решить проблему с расширенным TSP с помощью графической базы данных, но у меня возникают трудности. Я отлично разбираюсь в SQL, но я полный новичок в шифровании. Я создал простой граф с городами (узлами) и рейсами (отношениями)....
1786 просмотров
schedule
12.07.2022
Коммивояжер по Java
Основываясь на этом псевдокоде, я пытаюсь реализовать функцию пригодности java для проблемы коммивояжера, но я не уверен, что делаю это правильно, может кто-нибудь помочь мне.
N The number of cities to visit
T A tour (list of integers of size...
1258 просмотров
schedule
07.07.2022
Алгоритм поиска гармонии, адаптированный для коммивояжера
Я ищу адаптацию алгоритма поиска гармонии, который решил проблему коммивояжера. Я должен реализовать это и описать результаты. Я нашел несколько решений, таких как:
http://www.jtacs.org/archive/2013/1/4/JTACS_2013_01_04.pdf
но эти решения не...
941 просмотров
schedule
14.08.2022
Tile Trial NP-сложная сложность
В игре Final Fantasy XIII-3 игроку предлагается пара головоломок. Первая представленная головоломка называется Tile Trial . Она представляет игроку сетку плиток, на некоторых из которых есть кристаллы. Цель состоит в том, чтобы собрать все...
99 просмотров
schedule
06.05.2022
Алгоритм запроса — несколько водителей, несколько местоположений
Честно говоря, я не знаю, где/что разместить это как, но я буду очень признателен всем за любые советы, которые вы можете предоставить.
Я хочу создать алгоритм, который рассчитает наиболее оптимальное расписание для компании такси (междугородный...
72 просмотров
schedule
08.05.2022
TSP, где вершины можно посещать несколько раз
Я ищу решение проблемы, когда у меня есть взвешенный ориентированный граф, и я должен начать с начала координат, посетить все вершины хотя бы один раз и вернуться в начало координат по кратчайшему пути. По сути, это будет классический пример TSP, за...
1226 просмотров
schedule
27.10.2022
