TSP 算法给出不正确的输出

Question

我花了几个小时试图找出我的程序有什么问题，但我无法弄清楚。这是一个最低旅游成本的项目。 (TSP)

c 代表城市，a 代表弧形（2 个城市之间的旅行费用）

我用来测试的输入：

这是我的代码。上面的输入应该给出 10500 minTour，但它显示 5600。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cassert>
#include <sstream>
#include <cstdlib>
#include <string>
#include <stdint.h>


using namespace std;



static char gFirstCity = 0;
static unsigned graph[50][50] = {0};
static unsigned minTour = 0xffffffff;


void swap (char *x, char *y)
{
    char temp;
    temp = *x;
    *x = *y;
    *y = temp;
}
void permute(char* cities, unsigned start, unsigned length)
{
   if (start == (length-1))
   {

       cout << endl;
       unsigned cost =0;


       cost+= graph[(unsigned)gFirstCity][(unsigned)*cities];

       for(unsigned i = 0; i < length-1; i++ )
       {
        cost+=graph[(unsigned)cities[i]][(unsigned)cities[i+1]];
        for(int i = 0; i < length; i++){
            cout << (int)cities[i];
        }
       }
       cost+=graph[(unsigned)cities[length-1]][(unsigned)gFirstCity];
       for(int i = 0; i < length; i++){
           cout << (int)cities[i];
       }
       if(cost<minTour){
           minTour = cost;
       }
   }
   else
   {
        for (unsigned j = start; j < length; j++)
        {
            swap((cities + start), (cities + j));
            permute(cities, start + 1, length);
            swap((cities + start), (cities + j));
        }
    }
}


int main()
{
    string cities;
    string line;
    char command = 0;
    unsigned city = 0;
    while (getline(cin, line))
    {
        sscanf(line.c_str(), "%c %d", &command, &city);
        if (command != 'c')
            break;
        cities.push_back((unsigned char)city);
    }

    gFirstCity = cities[0];

    unsigned to = 0;
    unsigned from = 0;
    uint32_t cost = 0;

    sscanf(line.c_str(), "%c %d %d %d", &command, &to, &from, &cost);
    graph[to-1][from-1]=cost;
    graph[from-1][to-1]=cost;


    while (getline(cin, line))
    {
        sscanf(line.c_str(), "%c %d %d %d", &command, &to, &from, &cost);
        graph[to-1][from-1]=cost;
        graph[from-1][to-1]=cost;
    }


    permute((char*)cities.c_str()+1, 0, cities.length()-1);
    cout << minTour << endl;

    return EXIT_SUCCESS;

Answer 1

在代码中添加了一些调试输出后，最大的问题似乎是您的算法不一致地混合了数组索引和城市。

例如，您的gStartCity用作数组索引（从0开始），但实际上是一个城市编号（从1开始）。

你在实际获取成本时使用数组索引1-5，但你将成本分配给数组索引0-4。

我相信您可以通过将两组 graph[][] 作业更改为：

来获得预期的结果

graph[to][from]=cost;
graph[from][to]=cost;

graph[][] 的定义将允许在不覆盖其他内容的情况下进行此操作，并且您的寿命不足以使该算法计算出 49 个城市的最佳路径，因此差异无关紧要（49城市将需要大约 6E+62 条可能的路径；即使您每秒可以检查一百万条路径，这也只需要大约 20,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000 年的计算时间。

你的代码很难阅读和遵循，所以我不确定如何最好地解决你在大多数数组索引上偏离 1 的基本问题，但至少这应该得到它运行更接近您期望的方式。

TSP 算法给出不正确的输出

Algorithm for TSP giving incorrect output

c++

algorithm

swap