Вопросы по теме 'traveling-salesman'
Тур какого размера я могу разумно рассчитывать на решение с помощью GLPK?
Я играю с Пример коммивояжера , поставляемый с GLPK, и пытается понять, какой размер проблемы я могу разумно ожидать от решения. Мне удалось решить граф из 50 узлов, но 100 узлов, похоже, не сходятся в разумные сроки (30 минут или около того на...
637 просмотров
schedule
28.10.2021
Путь с наименьшей стоимостью в отсортированном массиве
Учитывая отсортированный массив A , например. {4,9,10,11,19} . Стоимость переезда из i->j составляет abs(A[j]-A[i]) . Начать с заданного элемента, например. 10 . Найдите путь с наименьшей стоимостью, не посещая один и тот же элемент...
383 просмотров
schedule
07.09.2021
Псевдокод для метода ветвей и границ для решения TSP.
Я ищу псевдокод для алгоритма B&B для задачи коммивояжера. Я нашел это: TSP - Branch and bound , но ссылки, которые кто-то дал там в качестве ответа, не были " пока не помогло мне. У вас есть примеры этого псевдокода?
Заранее спасибо!
3457 просмотров
schedule
20.09.2021
Поиск пути, который посещает все вершины ориентированного графа ровно один раз
Для данного ориентированного графа, что такое алгоритм, который посещает каждую вершину графа только один раз. Это отличается от гамильтонова цикла тем, что мне не требуется, чтобы путь начинался и заканчивался в одной и той же вершине.
Алгоритм...
2859 просмотров
schedule
26.09.2021
В формуле расстояния для TSP не возвращается число
Я пытаюсь создать базовое решение TSP на Python, и у меня возникает небольшая проблема при попытке вычислить общее расстояние между каждым порядком городов. Города создаются и хранятся в виде случайно сгенерированного 2-мерного списка; внутренние...
27 просмотров
schedule
29.10.2021
Как решить проблему TSP с помощью пакета pyGAD?
Используя пакет PyGAD, как сгенерировать элемент популяций с элементом, не повторяющимся между 1 и 12? В случайной совокупности он всегда имеет двойное значение. У меня нет идеала, как этого избежать. Или мне следует манипулировать функцией...
168 просмотров
schedule
21.09.2021
Что, если коммивояжер путешествовал на самолете?
Кажется интуитивно понятным решение двухмерной задачи коммивояжёра на глаз с использованием жадной стратегии. Однако мы можем решить TSP на глаз только в том случае, если график топографически точен, например. если от A до B равно 10 и от A до C...
79 просмотров
schedule
01.02.2022
Вопросы оптимизации муравьиной колонии: как правильно выводить результаты, что получается в результате алгоритма и другие
Я делаю алгоритм оптимизации муравьиной колонии. У меня есть несколько вопросов. Я попытался выполнить поиск с помощью муравьиной колонии , но ничего не нашел.
1 — Каков результат алгоритма?
У меня есть график, и мне нужно найти оптимальный...
514 просмотров
schedule
21.02.2022
Задача коммивояжера
Я пытаюсь разработать программу на С++ из алгоритма задачи коммивояжера. Мне нужна матрица расстояний и матрица затрат. После использования всех формул я получаю новую результирующую матрицу. Но я не понимаю, что показывает эта матрица....
6044 просмотров
schedule
09.03.2022
Google OR-Tools TSP возвращает несколько решений
Недавно я работал над поиском не только оптимального маршрута с помощью OR-Tools от Google. Я нашел пример в репозитории , но это решает только оптимальный маршрут, есть идеи, как сгенерировать более одного решения для набора точек? В настоящее...
977 просмотров
schedule
19.03.2022
Обход пространства состояний игры: больше поиска приводит к плохим результатам
Я публикую этот вопрос из codereview поскольку я обнаружил, что он не отвечает.
Эта проблема доступна на hackerrank ai . Я не прошу решений, а пытаюсь найти, что не так с моей стратегией или кодом.
Я пытаюсь решить проблему, которая, как мне...
213 просмотров
schedule
30.03.2022
Реализовать локальный поиск (2-opt) для решения TSP в Java
Я пытаюсь реализовать это, но я не могу найти хорошую статью или описание того, как это сделать, не могли бы вы, ребята, указать мне правильное направление, пожалуйста? У меня есть его реализация на С#, но я недостаточно знаю, чтобы просто...
1729 просмотров
schedule
03.04.2022
Вариация задачи коммивояжера - выберите хороший подмаршрут из множества узлов на основе ограничений.
Версия TLDR: Самый важный вопрос заключается в том, что в задаче TSP вместо поиска кратчайшего гамильтонова цикла есть хорошие способы найти лучший путь (я полагаю, тот, который посещает наибольшее количество узлов), который имеет длину не более X...
2737 просмотров
schedule
16.04.2022
Как превратить стандартный решатель коммивояжёра в решатель цены для or-tools?
Я настроил прекрасный решатель для «какого маршрута лучше всего посетить 1000 узлов» на моем графике.
Но я хотел бы решить вопрос «каким кратчайшим путем можно посетить любые 500 из 1000 заданных узлов в моем графе».
Думаю, мне нужно добавить...
554 просмотров
schedule
04.05.2022
Остается ли оптимальное решение TSP оптимальным даже после пропуска нескольких городов?
Допустим, я знаю глобальное оптимальное решение стандартной задачи коммивояжёра для 100 городов. Теперь предположим, что продавец хочет пропустить 5 городов. Нужно ли переделывать TSP? Будет ли последовательность городов, полученная простым...
174 просмотров
schedule
31.05.2022
Детальный вопрос при применении генетического алгоритма к коммивояжеру
Я читал разные материалы по этому поводу и понимаю принципы и концепции, однако ни в одной из статей не упоминаются детали того, как рассчитать пригодность хромосомы (которая представляет собой маршрут) с участием соседних городов (в хромосоме),...
611 просмотров
schedule
13.06.2022
Пролог: рекурсия по списку с одним одноразовым правилом
Скорее всего, я не смог правильно сформулировать ключевые слова для поиска. Я пытаюсь рекурсивно оценить разницу последовательных записей в списке и продолжать добавлять их в глобальный счетчик. Проблема заключается в циклическом предложении в...
550 просмотров
schedule
15.06.2022
Модифицированный коммивояжер
Учитывая структуру графа с асимметричными затратами на ребрах, есть ли способ пройти определенный набор узлов с наименьшими затратами, если вы можете посетить каждый узел только один раз? Задача формулируется так, что такой путь должен существовать.
137 просмотров
schedule
22.06.2022
Где найти набор сложных задач коммивояжёра (с известными решениями/приближениями)?
Я хочу попробовать свои силы в поиске эвристик/аппроксимаций для решения задачи коммивояжёра, и для этого я ищу несколько «жестких» экземпляров TSP (вместе с их наиболее известными решениями), чтобы попытаться решить их и посмотреть, насколько хорошо...
1387 просмотров
schedule
24.06.2022
Алгоритм поиска пути ко всем городам
Я надеюсь, что уже есть прямой алгоритм решения этой проблемы, но не уверен, как называется проблема такого типа и, следовательно, где искать решение. В чем-то она похожа на задачу коммивояжера, но я думаю, что она должна быть намного проще....
287 просмотров
schedule
28.06.2022
