算法设计与分析回溯法旅行商问题C语言

以下是使用回溯法解决旅行商问题的C语言代码示例：

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

#define V 4 // 旅行商问题中的顶点数

// 旅行商问题的函数
int tsp(int graph[][V], int visited[], int curr_pos, int n, int count, int cost, int min_cost) {
    // 如果所有顶点都被访问过，则返回当前路径的总成本
    if (count == n && graph[curr_pos][0]) {
        min_cost = (cost + graph[curr_pos][0] < min_cost) ? cost + graph[curr_pos][0] : min_cost;
        return min_cost;
    }
    // 遍历所有未访问的顶点
    for (int i = 0; i < n; i++) {
        if (!visited[i] && graph[curr_pos][i]) {
            visited[i] = 1;
            min_cost = tsp(graph, visited, i, n, count + 1, cost + graph[curr_pos][i], min_cost);
            visited[i] = 0;
        }
    }
    return min_cost;
}

int main() {
    // 旅行商问题的图
    int graph[V][V] = {{0, 10, 15, 20},
                       {10, 0, 35, 25},
                       {15, 35, 0, 30},
                       {20, 25, 30, 0}};
    // 记录每个顶点是否被访问过
    int visited[V] = {0};
    visited[0] = 1; // 从第一个顶点开始
    // 调用旅行商问题函数
    int min_cost = tsp(graph, visited, 0, V, 1, 0, INT_MAX);
    // 输出最小成本
    printf("The minimum cost of the TSP problem is %d\n", min_cost);
    return 0;
}