C++ 暴力法解决旅行商问题：详解代码和优化策略

以下是一个使用暴力法（exhaustive search）解决旅行商问题的 C++ 代码，可以接受任意顶点数和边数的无向图输入：

#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 20; // 最大顶点数
const int INF = 0x3f3f3f3f; // 无穷大

int n, m, ans = INF; // n为顶点数，m为边数，ans为最短路径长度
int g[MAXN][MAXN]; // 存储图的邻接矩阵
int path[MAXN]; // 存储当前路径
bool vis[MAXN]; // 标记当前顶点是否被访问过

void dfs(int u, int len, int cnt) {
    if (len >= ans) return; // 剪枝1：若当前路径长度已经超过最优解，则返回
    if (cnt == n) { // 如果所有顶点都已经访问过
        ans = len; // 更新最优解
        return;
    }
    for (int v = 0; v < n; ++v) { // 枚举下一个要访问的顶点
        if (!vis[v]) {
            vis[v] = true; // 标记为已访问
            path[cnt] = v; // 将当前顶点加入路径
            dfs(v, len + g[u][v], cnt + 1); // 递归搜索
            vis[v] = false; // 回溯，将当前顶点标记为未访问
        }
    }
}

int main() {
    ifstream fin("input.txt"); // 从文件中读入数据
    fin >> n >> m;
    memset(g, INF, sizeof(g));
    for (int i = 0; i < m; ++i) {
        int u, v, w;
        fin >> u >> v >> w;
        g[u][v] = g[v][u] = w; // 无向图，需要同时更新两个方向的边
    }
    fin.close();
    memset(vis, false, sizeof(vis));
    vis[0] = true; // 从顶点0开始搜索
    path[0] = 0; // 将0号顶点加入路径
    dfs(0, 0, 1); // 从0号顶点开始搜索，当前路径长度为0，已经访问了1个顶点
    cout << "Shortest path length: " << ans << endl;
    cout << "Path: ";
    for (int i = 0; i < n; ++i)
        cout << path[i] << ' ';
    cout << endl;
    return 0;
}

需要注意的是，暴力法的时间复杂度是指数级别的，对于大规模的图，无法在合理的时间内求解最优解。因此，在实际应用中，需要使用其他更加高效的算法来解决旅行商问题。例如：

• 贪婪算法： 从起点开始，每次选择距离当前位置最近的未访问节点，直到所有节点都被访问过。
• 动态规划： 通过构建一个表格，存储从起点到每个节点的最短路径长度，并利用表格进行递推计算。
• 模拟退火算法： 从一个随机解开始，逐步搜索更好的解，并使用一个概率函数来接受较差的解。

选择合适的算法取决于问题的规模、对解的精确度要求以及计算资源的限制。