@p:用c语言写旅行商问题

旅行商问题（TSP问题）是一个经典的组合优化问题，在计算机科学和数学领域都有广泛的研究。它的问题描述为：给定一组城市和每对城市之间的距离，求解访问每一座城市恰好一次并回到起始城市的最短回路。

以下是用C语言实现TSP问题的简单代码：

#include <stdio.h>
#include <limits.h>

#define V 4  // 图的顶点个数

int graph[V][V] = { // 图的邻接矩阵
    { 0, 10, 15, 20 },
    { 10, 0, 35, 25 },
    { 15, 35, 0, 30 },
    { 20, 25, 30, 0 }
};

int visited[V] = {0}; // 记录每个节点是否被访问过
int path[V]; // 记录路径

int min(int a, int b) {
    return (a < b) ? a : b;
}

int tsp(int current) {
    int i, j;
    int min_path = INT_MAX;
    int temp_path;

    visited[current] = 1;
    path[0] = current;

    for (i = 0, j = 1; j < V; i++, j++) {
        int next;
        int min_distance = INT_MAX;

        for (int k = 0; k < V; k++) {
            if (!visited[k] && graph[current][k] < min_distance) {
                next = k;
                min_distance = graph[current][k];
            }
        }

        temp_path = tsp(next);
        if (temp_path < min_path) {
            min_path = temp_path;
            for (int k = 0; k < V; k++) {
                path[k + 1] = path[k];
            }
            path[0] = next;
        }

        visited[next] = 1;
        current = next;
    }

    return min_path + graph[current][path[0]];
}

int main() {
    int result = tsp(0);

    printf("最短路径为: %d\n", result);
    printf("路径为: ");
    for (int i = 0; i < V; i++) {
        printf("%d ", path[i]);
    }
    printf("%d\n", path[0]);

    return 0;
}

该代码使用递归的方式实现了TSP问题的求解。在每一次递归中，找到与当前节点最近的未访问节点，并以该节点为起点继续递归，直到所有节点都被访问过为止。在回溯过程中，记录经过的路径，并计算路径长度。最终返回最短路径长度和路径本身。