分支限界法求解旅行商问题c语言代码

以下是使用分支限界法求解旅行商问题的C语言代码：

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

#define N 4

int graph[N][N] = {{0, 10, 15, 20},
                   {10, 0, 35, 25},
                   {15, 35, 0, 30},
                   {20, 25, 30, 0}};

int best_path[N];
int current_path[N];
bool visited[N] = {false};
int best_cost = INT_MAX;
int current_cost = 0;

void branch_and_bound(int current_vertex, int level)
{
    if (level == N)
    {
        if (current_cost + graph[current_vertex][0] < best_cost)
        {
            best_cost = current_cost + graph[current_vertex][0];
            for (int i = 0; i < N; i++)
            {
                best_path[i] = current_path[i];
            }
        }
        return;
    }

    for (int i = 0; i < N; i++)
    {
        if (!visited[i])
        {
            visited[i] = true;
            current_path[level] = i;
            current_cost += graph[current_vertex][i];
            if (current_cost + (N - level) * graph[current_vertex][i] < best_cost)
            {
                branch_and_bound(i, level + 1);
            }
            visited[i] = false;
            current_cost -= graph[current_vertex][i];
        }
    }
}

int main()
{
    visited[0] = true;
    current_path[0] = 0;
    branch_and_bound(0, 1);

    printf("Best cost: %d\n", best_cost);
    printf("Best path: ");
    for (int i = 0; i < N; i++)
    {
        printf("%d ", best_path[i]);
    }
    printf("0\n");

    return 0;
}

这个代码使用了一个邻接矩阵来存储图，并且假设起点为0。在branch_and_bound函数中，我们使用深度优先搜索的方式找到所有可能的路径，并使用当前最优解来剪枝。最后，程序输出了最短路径的距离和路径本身。