Оптимизация задачи коммивояжера для посещения городов [закрыто] ⇐ C++

[Anonymous]

Я студент колледжа и изучаю алгоритмы. Профессор задал нам очень трудный вопрос о TSP.

Реализовать задачу TSP, используя лучший первый алгоритм (так что это будет возврат, «ветви и границы» и «лучшее в первую очередь»). Поскольку вы ищете цикл, город старта/финиша не имеет значения. Поэтому мы предполагаем, что start и Город финиша всегда имеет индекс 0.

Для связанного использования используйте решение ослабленной задачи, обсуждаемое на занятии: TSP использует два ограничения
[*]Обязательно посетить все города. [*]каждый город посещается один раз (кроме начала) Попробуйте отбросить один из них и посмотрите, сможете ли вы решить полученную расслабленную ситуацию. проблема.
Драйвер вызывает функцию std::vector SolveTSP(char const* имя файла); Возвращаемое значение — это вектор индексов городов в порядке их посещения. Первое и последнее значения всегда равны 0 (начало=0, ...., окончание=0). Пример: 0 4 2 1 3 0 Это пример карты: 10 1 3 3 5 4 2 1 4 4 1 3 2 3 5 4 4 5 4 4 3 1 2 3 3 2 1 1 2 5 4 2 2 2 1 1 2 4 1 4 5 2 2 4 1 4 где 10 — количество городов

Я написал эвристику ближайшего соседа, и она решила половину тестовых случаев. В остальных случаях тайм-аут истекает, поскольку алгоритм занял слишком много времени. Я поспрашивал, и друг предложил ранний выход, чтобы алгоритму не приходилось продолжать расчет, когда стоимость текущего пути превышает стоимость наилучшего пути. Он решил 70% тестовых случаев, но последние 3 тестовых случая все еще находятся в тайм-ауте. Есть ли еще способы оптимизировать свой код? Это мой tsp.cpp:
#include #include #include #include #include #include использование пространства имен std; константный INT INF = INT_MAX; структура State { международный город; внутренний уровень; векторный путь; int посетил; // Битовая маска для представления посещенных городов внутренняя стоимость; State(int _city, int _level, const вектор& _path, int _visited, int _cost) : город (_city), уровень (_level), путь (_path), посещенный (_visited), стоимость (_cost) {} bool оператор>(const State& другое) const { стоимость возврата > прочее.стоимость; } }; int NearestNeighborHeuristic(const вектор& distances, int numCities) { вектор посетил (numCities, false); векторный путь; ИНТ TotalCost = 0; // Начинаем с города 0 ИНТ CurrentCity = 0; посетил [текущийСити] = правда; path.push_back(currentCity); for (int i = 1; я