用禁忌搜索算法解决TSP问题，c++实现，每个节点用二维坐标系表示

好的，禁忌搜索算法可以用来解决TSP问题，以下是C++实现的示例代码：

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <cstdlib>

using namespace std;

const int MAXN = 100;

// 城市的数量
int n;
// 城市的坐标
int x[MAXN], y[MAXN];
// 最优路径和距离
vector<int> bestPath;
double bestDistance;

// 计算两个城市之间的距离
double dist(int i, int j) {
    return sqrt((x[i]-x[j])*(x[i]-x[j]) + (y[i]-y[j])*(y[i]-y[j]));
}

// 计算一条路径的总距离
double getPathDistance(const vector<int>& path) {
    double distance = 0.0;
    for (int i = 0; i < n; ++i) {
        distance += dist(path[i], path[(i+1)%n]);
    }
    return distance;
}

// 生成一个初始解
vector<int> generateInitialPath() {
    vector<int> path(n);
    for (int i = 0; i < n; ++i) {
        path[i] = i;
    }
    random_shuffle(path.begin(), path.end());
    return path;
}

// 交换路径中的两个城市
void swapCities(vector<int>& path, int i, int j) {
    swap(path[i], path[j]);
}

// 禁忌搜索算法
void tabuSearch(int maxIter, int tabuSize) {
    // 初始化当前路径和最优路径
    vector<int> currentPath = generateInitialPath();
    bestPath = currentPath;
    bestDistance = getPathDistance(currentPath);

    // 初始化禁忌表
    vector<vector<int>> tabuList(n, vector<int>(n, 0));

    for (int iter = 1; iter <= maxIter; ++iter) {
        // 选择最好的相邻解
        int bestI = -1, bestJ = -1;
        double bestDelta = 1e9;
        for (int i = 0; i < n; ++i) {
            for (int j = i+1; j < n; ++j) {
                // 计算交换位置i和j的路径长度变化
                double delta = dist(currentPath[i], currentPath[j])
                             + dist(currentPath[(i+1)%n], currentPath[(j+1)%n])
                             - dist(currentPath[i], currentPath[(i+1)%n])
                             - dist(currentPath[j], currentPath[(j+1)%n]);
                // 如果这个交换比当前最好的还要好，且不在禁忌表中，就更新最好的交换位置
                if (delta < bestDelta && tabuList[i][j] == 0) {
                    bestDelta = delta;
                    bestI = i;
                    bestJ = j;
                }
            }
        }

        // 更新当前路径和最优路径
        swapCities(currentPath, bestI, bestJ);
        double currentDistance = getPathDistance(currentPath);
        if (currentDistance < bestDistance) {
            bestPath = currentPath;
            bestDistance = currentDistance;
        }

        // 将这个交换加入禁忌表
        tabuList[bestI][bestJ] = tabuList[bestJ][bestI] = tabuSize;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (tabuList[i][j] > 0) {
                    tabuList[i][j]--;
                }
            }
        }
    }
}

int main() {
    srand(time(NULL));

    // 输入城市的数量和坐标
    cin >> n;
    for (int i = 0; i < n; ++i) {
        cin >> x[i] >> y[i];
    }

    // 运行禁忌搜索算法，输出最优路径和距离
    tabuSearch(1000, n/2);
    cout << "Best path:\n";
    for (int i = 0; i < n; ++i) {
        cout << bestPath[i] << " ";
    }
    cout << "\nBest distance: " << bestDistance << endl;

    return 0;
}

这段代码中，我们定义了一个`tabuSearch()`函数来实现禁忌搜索算法，其中`maxIter`表示最大迭代次数，`tabuSize`表示禁忌表的大小。函数中首先生成一个初始路径，然后不断迭代，每次选择最好的相邻解并更新路径和禁忌表，直到达到最大迭代次数为止。最后输出最优路径和距离。

在`tabuSearch()`函数中，我们使用了一个二维数组`tabuList`来表示禁忌表，其中`tabuList[i][j]`表示位置i和j是否在禁忌表中。在每次更新路径和禁忌表时，我们将这个交换加入禁忌表，并将禁忌表中的所有交换次数减1，以保证交换不会一直在禁忌表中。