旅行售货员问题 分支限界法 c语言代码

分支限界法是一种求解问题的方法，可以用来解决旅行售货员问题。该问题是指一个售货员要依次访问n个城市，并且每个城市只能访问一次，最后回到起始城市。要求找出一条最短的路径，使得售货员完成销售任务。

为了用分支限界法求解旅行售货员问题，可以使用深度优先搜索算法。以下是用C语言编写的代码示例：

#include <stdio.h>

#define MAX_CITIES 10
#define INF 9999999

int n; // 城市数量
int matrix[MAX_CITIES][MAX_CITIES]; // 城市距离矩阵
int bestPath[MAX_CITIES]; // 最短路径
int visited[MAX_CITIES]; // 是否已访问过

int minCost = INF; // 最小成本

void travel(int currentCity, int *path, int cost) {
    if (currentCity == 0 && cost < minCost) {
        minCost = cost;
        for (int i = 0; i < n; i++) {
            bestPath[i] = path[i];
        }
    }
    
    for (int nextCity = 0; nextCity < n; nextCity++) {
        if (!visited[nextCity] && matrix[currentCity][nextCity] != INF) {
            visited[nextCity] = 1;
            path[currentCity + 1] = nextCity;
            travel(nextCity, path, cost + matrix[currentCity][nextCity]);
            visited[nextCity] = 0;
        }
    }
}

int main() {
    printf("请输入城市数量：");
    scanf("%d", &n);

    printf("请输入城市间距离矩阵（用INF表示无法直接到达）：\n");
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &matrix[i][j]);
        }
    }
    
    int path[MAX_CITIES];
    path[0] = 0; // 起始城市
    visited[0] = 1;
    
    travel(0, path, 0);
    
    printf("最短路径：");
    for (int i = 0; i < n; i++) {
        printf("%d ", bestPath[i]);
    }
    printf("0\n");
    
    printf("最小成本：%d\n", minCost);
    
    return 0;
}

以上代码通过深度优先搜索算法遍历所有可能的路径，并记录最短路径和对应的成本。最后输出最短路径和最小成本。

请注意，以上代码仅为示例，实际使用时可能需要根据具体情况进行适当修改和优化。