用C语言实现分支限界法实现旅行售货员问题

分支限界法是求解TSP问题的另一种常用方法，可以通过优先队列来实现。下面是用C语言实现分支限界法求解TSP问题的示例代码：

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

#define MAX_N 20
#define INF 0x3f3f3f3f

int graph[MAX_N][MAX_N]; // 节点距离矩阵
bool visited[MAX_N]; // 是否访问过
int best_cost = INF; // 最优解
int n; // 节点个数

typedef struct {
    int cur; // 当前节点
    int cost; // 当前路径花费
} Node;

typedef struct {
    Node node;
    int bound; // 上界
} Element;

typedef struct {
    Element arr[MAX_N * MAX_N];
    int front, rear;
} Queue;

// 初始化队列
void init_queue(Queue *q) {
    q->front = q->rear = 0;
}

// 入队
void enqueue(Queue *q, Element e) {
    q->arr[q->rear++] = e;
}

// 出队
Element dequeue(Queue *q) {
    return q->arr[q->front++];
}

// 判断队列是否为空
bool is_empty(Queue *q) {
    return q->front == q->rear;
}

// 计算当前节点的上界
int get_bound(Node node) {
    int bound = node.cost;
    int min1 = INF, min2 = INF;
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            if (graph[node.cur][i] < min1) {
                min2 = min1;
                min1 = graph[node.cur][i];
            } else if (graph[node.cur][i] < min2) {
                min2 = graph[node.cur][i];
            }
        }
    }
    if (min1 != INF) {
        bound += min1;
    }
    if (min2 != INF) {
        bound += min2;
    }
    return bound;
}

// 分支限界法
void tsp_branch_bound() {
    Queue q;
    init_queue(&q);

    // 将起点加入队列
    Node start = {0, 0};
    visited[0] = true;
    Element start_elem = {start, get_bound(start)};
    enqueue(&q, start_elem);

    // 搜索队列中最优解
    while (!is_empty(&q)) {
        Element cur_elem = dequeue(&q);
        Node cur_node = cur_elem.node;

        // 更新最优解
        if (cur_elem.bound >= best_cost) {
            continue;
        }
        if (cur_node.cur == 0 && cur_node.cost != 0 && all_visited()) {
            best_cost = cur_node.cost;
            continue;
        }

        // 尝试从当前节点出发，走遍所有未访问过的节点
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                Node next_node = {i, cur_node.cost + graph[cur_node.cur][i]};
                Element next_elem = {next_node, get_bound(next_node)};
                enqueue(&q, next_elem);
                visited[i] = false;
            }
        }
    }
}

// 判断是否所有节点都已经访问过
bool all_visited() {
    for (int i = 0; i < n; i++) {
        if (!visited[i]) {
            return false;
        }
    }
    return true;
}

int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &graph[i][j]);
        }
    }
    tsp_branch_bound();
    printf("%d\n", best_cost);
    return 0;
}

其中，`Queue`表示优先队列，`Element`表示优先队列中的元素，包括当前节点和上界。`get_bound`函数计算当前节点的上界，`all_visited`函数判断是否所有节点都已经访问过。在主函数中，我们读入节点距离矩阵，调用分支限界法求解TSP问题，输出最优解。