Описание тега traveling-salesman
"Задача коммивояжера" - это классическая задача информатики, которая включает в себя поиск кратчайшего пути, по которому гипотетический продавец мог бы совершить одно посещение каждого места на карте (в виде графика).
3
ответа
"нет подходящей функции для вызова 'Map<Flat>:: functionname"
Я пытаюсь настроить среду для путешествующих продавцов. Это моя попытка: #include <iostream> using namespace std; #include<stdlib.h> #include <cstdlib> #include <cmath> class Base //Allocate the memory space { protected: int …
24 фев '15 в 17:31
2
ответа
Задача о коммивояжере коммивояжера
Я прочитал пару статей и пример кода о том, как решить TSP с помощью генетических алгоритмов, оптимизации колоний муравьев и т. Д. Но все, что я обнаружил, не включало временные (оконные) ограничения, например. "Я должен быть у клиента х до 12 утра)…
14 апр '10 в 07:22
0
ответов
Сложность времени алгоритма в коммивояжере?
В настоящее время я изучаю TSP и хочу объединить две простые эвристики в одном алгоритме. Он работает, используя алгоритм ближайшего соседа для создания тура, а затем улучшая его, используя своп с 2 опциями для каждой комбинации. Я полагаю, что коли…
30 авг '18 в 03:14
1
ответ
Маршрут между А и В со станциями между
Я явно скучаю по лесу сквозь деревья... я знаю о проблеме коммивояжера, но есть ли другой алгоритм / проблема, которая лучше соответствует моим потребностям / описанию? Мне нужно описать мою проблему с помощью такого математического описания. У меня…
24 сен '13 в 19:20
1
ответ
TSP для полного ориентированного графа
Существует ли алгоритм полиномиального времени для задачи коммивояжера на полном ориентированном графе?
18 окт '16 в 19:10
0
ответов
Как реализовать граф для REST API
Я пытаюсь создать эффективный планировщик курса для инженерной школы в моем колледже, и мне нужно будет составить график всех предлагаемых курсов и различных способов навигации по ним до выпуска. Я реализовал проблему типа TSP в C, но теперь задаюсь…
06 янв '16 в 04:18
3
ответа
Решение проблем, которые не могут быть решены даже эффективно?
Как эти проблемы попадают в гобелен из комплектов P, NP, NP-Hard и т. Д.? Я не знаю, существуют ли вообще такие проблемы, но то, что инициировало мой мыслительный процесс, было размышлением о разрешении проблемы коммивояжера: Given a list of cities …
31 мар '14 в 20:02
1
ответ
Вариант минимального связующего дерева коммивояжера
Я пытаюсь решить следующее графическое упражнение: В неориентированном взвешенном графе есть V вершин и E ребер. Найдите минимальный вес, необходимый для посещения T(T<=V) вершин, начиная с вершины, помеченной как 0. Кроме того, если между двумя пос…
26 мар '15 в 20:48
1
ответ
Антагонизм в генетических алгоритмах для коммивояжера Проб. среди противоположных путей по тому же маршруту
Я почти уверен, что мой вопрос должен быть расследован, но мне не хватает жаргона, который поможет мне искать литературу. Я пишу генетический алгоритм, который решает тип задачи коммивояжера (TSP). Как и в стандартном TSP, мой вариант не имеет понят…
14 дек '15 в 19:41
1
ответ
Как учесть изменения пользователя в результате и учесть их в VRP
Я работаю над одним VRP(проблема маршрутизации транспортных средств), чтобы составить план обслуживания пикапов и отбрасывания, так как VRP - это сложная задача NP-пользователя, который редактирует план в соответствии с их требованиями. Теперь я пла…
29 янв '19 в 11:29
0
ответов
Сценарий наименьшего расстояния
На днях у меня была проблема, которая была довольно интересной. Это касается планирования серии "турниров". Ниже приведены ограничения: Есть 7 команд с именами A, B, ..., G Турнир состоит из 3 команд, все команды в турнире играют 1 игру против двух …
30 июн '15 в 09:02
1
ответ
Проблемы НП могут быть решены в детерминистически-экспоненциальное время?
Любая проблема в NP может быть решена за детерминированное экспоненциальное время, или мы можем сказать, что любой язык в NP может быть решен с помощью алгоритма, работающего за время 2^O(n^k), т. е. NP ⊆ EXP неформально говоря, мы просто пробуем ка…
19 ноя '13 в 14:53
1
ответ
Перевод кода Python из gurobipy в PuLP в Python
Я новичок в PuLP и LP в целом. При переводе кода предназначен для gurobipi библиотека, поэтому она может быть использована с PuLPЯ застрял в следующем коде gurobipy, который создает переменные. # Create variables. # x[i, j] is 1 if the edge i->j …
04 окт '16 в 15:19
1
ответ
Решение TSP в лабиринте с использованием ACO
Я пишу алгоритм, который включает задачу коммивояжера и задачу решения лабиринта. По сути, в лабиринте есть точки, и нам нужно найти наиболее оптимальный путь ко всем этим точкам и в конечном итоге выйти из лабиринта. Мы начали использовать алгоритм…
23 окт '14 в 10:08
4
ответа
Командующий продавец отправляет устаревшие товары на разные рынки
Какую эвристику можно использовать для решения следующей задачи? Компания Quality Blimps Inc. стремится расширить свои продажи в других городах (N), поэтому они наняли вас в качестве продавца, чтобы он летал в другие города для продажи дирижаблей. Б…
04 фев '13 в 16:24
1
ответ
Алгоритм поиска Hill Climbing Применяется к коммивояжеру
Допустим, нам дано 7 городов A, B, C, D, E, F, G, и у нас есть начальное состояние ABCDEFGA с некоторой стоимостью 'x', я не понимаю, какими будут дочерние элементы этого узла. будет ли проходить вторая итерация алгоритма восхождения на гору? Будет …
20 фев '13 в 02:11
0
ответов
Оптимальное рисование 2D-изображений с помощью, например, головки принтера
Я не знаю, нахожусь ли я на правом стеке обмена для этого типа вопроса. У меня есть машина, которая похожа на принтер. Он наносит материал на поверхность, как карандаш рисует на бумаге. Я могу кормить этот совет списком координат для рисования. У ме…
04 сен '15 в 12:26
0
ответов
MathProg рекурсивная функция
Я столкнулся с проблемой подсчета связанных узлов в Mathprog при попытке решить довольно большую проблему TSP: допустим, у меня есть set C := 0..645; # a set of nodes set A := {i in C, j in C: i!=j}; # a set of edges функция расстояния d(c1,c2) var …
08 сен '12 в 10:12
0
ответов
Бесконечный цикл в базовом алгоритме жадности для TSP
Я пытаюсь реализовать базовый жадный алгоритм для задачи коммивояжера в Python 2.7. У меня есть словарь под названием d_dict = {(city1,city2):distance}, в котором хранятся расстояния между городами. Здесь все города связаны друг с другом. Мне просто…
11 янв '17 в 15:25
0
ответов
Как превратить стандартный Решатель для путешествующих продавцов в Решатель для сбора цен для or-tools?
Я настроил точный решатель для *, что является лучшим маршрутом для посещения 1000 узлов "в моем графике. Но я хотел бы решить вопрос "какой кратчайший маршрут для посещения любых 500 из 1000 заданных узлов в моем графике". Я думаю, я должен как-то …
02 сен '15 в 08:02