一种非完全图下的TSP求解算法

序

旅行商问题（Traveling Salesman Problem，简称TSP）是组合优化中的一个经典问题，就是给定一组城市和城市之间的距离，找到一条最短路径使得每个城市只被访问一次后返回到起点。

一些传统的解法都是基于完全图的，我在网上也很少找到非完全图的解法，非完全图应该在实际应用中会更实用，这里我简单实现一个算法。

算法细节

与完全图的差异

非完全图意味着某些节点之间不相连，这样求解时就需要考虑这样情况，不能直接假设两个节点直连。

图的预处理

最开始要对图进行预处理，这里我们针对于该图使用Kruskal算法构建一颗最小生成树，之后针对该树进行分支删减，以达到最终路线是一个环路。

我这里使用的输入的形式是邻接矩阵，假设路线图是这样的：

对应的邻接矩阵则是

using GraphVec = std::vector<std::vector<int>>;
GraphVec graph_8 = {
        {0, 3, 1, 1, 1, 0, 0, 0},
        {3, 0, 1, 0, 0, 1, 0, 0},
        {1, 1, 0, 1, 0, 0, 2, 0},
        {1, 0, 1, 0, 0, 0, 0, 1},
        {1, 0, 0, 0, 0, 1, 1, 1},
        {0, 1, 0, 0, 1, 0, 0, 1},
        {0, 0, 2, 0, 1, 0, 0, 1},
        {0, 0, 0, 1, 1, 1, 1, 0},
    };

最开始我们先来看下使用到的数据结构：

struct Edge{
    Edge() = default;
    Edge(int s, int e, int w) :
        start(s),
        end(e),
        weight(w) {}

    int start = -1;
    int end = -1;
    int weight = -1;
};

这里很简单，我就是将两个节点的边做了一下抽象

然后简单看一下最小生成树的构建过程：

using TreeDeque = std::deque<Edge>;
TreeDeque makeMSTByKruskal(const GraphVec& graph) {
    std::priority_queue<Edge, std::vector<Edge>, decltype(compare)> queue(compare);
    for (int i = 0; i < graph.size(); ++i) {
        for (int j = 0; j < graph[0].size(); ++j) {
            if (i < j && graph[i][j] > 0) {
                queue.emplace(i, j, graph[i][j]);
            }
        }
    }

    std::set<int> visited;
    TreeDeque tree;
    while (!queue.empty()) {
        auto edge = queue.top();
        queue.pop();

        if (visited.find(edge.start) != visited.end() && visited.find(edge.end) != visited.end()) {
            continue;
        }

        visited.insert(edge.start);
        visited.insert(edge.end);
        tree.push_back(edge);
    }

    return tree;
}

这里使