c++ 调用求解器编写tsp

TSP（Traveling Salesman Problem）是一个经典的 NP 难问题，暴力搜索解决不了，需要使用启发式算法或者求解器。求解器是一种专门用于求解优化问题的软件，可以快速求解 TSP 问题。

下面是使用 C++ 调用求解器 Gurobi 求解 TSP 问题的示例代码：

#include <iostream>
#include <cstring>
#include <gurobi_c++.h> // 引入 Gurobi 求解器头文件
using namespace std;

const int N = 20;
int n;
double x[N], y[N];
double dist[N][N];

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) cin >> x[i] >> y[i];

    // 计算距离矩阵
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            dist[i][j] = dist[j][i] = sqrt((x[i] - x[j]) * (x[i] - x[j]) + (y[i] - y[j]) * (y[i] - y[j]));

    try {
        GRBEnv env = GRBEnv(); // 创建 Gurobi 环境
        GRBModel model = GRBModel(env); // 创建 Gurobi 模型
        model.set(GRB_StringAttr_ModelName, "tsp"); // 设置模型名称

        // 创建决策变量
        GRBVar x[n][n];
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                x[i][j] = model.addVar(0.0, 1.0, dist[i][j], GRB_CONTINUOUS, "x_" + to_string(i) + "_" + to_string(j));

        // 添加约束条件
        for (int i = 0; i < n; i++) {
            GRBLinExpr expr = 0;
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                expr += x[i][j];
            }
            model.addConstr(expr == 2);
        }

        // 设置目标函数
        GRBLinExpr obj = 0;
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                obj += x[i][j];
        model.setObjective(obj, GRB_MINIMIZE);

        // 求解模型
        model.optimize();

        // 输出结果
        cout << "Optimal tour: ";
        for (int i = 0; i < n; i++)
            for (int j = i + 1; j < n; j++)
                if (x[i][j].get(GRB_DoubleAttr_X) > 0.5)
                    cout << i << " -> " << j << " ";
        cout << endl;
        cout << "Optimal distance: " << model.get(GRB_DoubleAttr_ObjVal) << endl;
    } catch (GRBException e) {
        cout << "Error code = " << e.getErrorCode() << endl;
        cout << e.getMessage() << endl;
    } catch (...) {
        cout << "Exception during optimization" << endl;
    }

    return 0;
}

上面的代码中，我们使用 Gurobi 求解器来求解 TSP 问题。首先，我们需要引入 Gurobi 求解器的头文件 `gurobi_c++.h`。然后，我们需要创建 Gurobi 环境和模型，设置模型名称。

接着，我们需要创建决策变量，即二维数组 `x[i][j]` 表示从节点 i 到节点 j 是否走这条边。我们需要设置决策变量的取值范围，即 0 到 1 之间的实数，并设置决策变量的系数，即边的长度。然后，我们需要添加约束条件，即每个节点都恰好走一次，并设置目标函数，即最小化总路程。

最后，我们调用模型的 `optimize` 方法来求解模型，输出最优解，即遍历所有节点的最短路径和总长度。如果求解过程出现错误，我们需要捕获异常并输出错误信息。

需要注意的是，在使用 Gurobi 求解器时，我们需要先在官网上下载并安装 Gurobi 软件，并获取一个 Gurobi 许可证才能使用。