旅行售货员回溯法c语言代码实现

旅行售货员问题（Traveling Salesman Problem, TSP）是一个经典的组合优化问题，涉及寻找一条经过所有城市恰好一次且总行程最短的路径。回溯法是解决这类问题的一种常用搜索策略。在C语言中，我们可以使用递归和数组来实现一个基本的TSP回溯算法。以下是一个简化的示例代码：

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

// 城市数据结构
typedef struct {
    int id;
    int x, y; // 坐标
} City;

// 计算两点之间的曼哈顿距离
int manhattan_distance(City* city1, City* city2) {
    return abs(city1->x - city2->x) + abs(city1->y - city2->y);
}

// 检查路径是否包含所有城市且没有重复
int is_valid_path(int* path, int n, int current_city, bool visited[]) {
    for (int i = 0; i < n; i++) {
        if (visited[i] && path[i] != current_city) return 0;
    }
    return path[n - 1] == current_city;
}

// 回溯函数
void tsp_backtrack(City* cities, int n, int* path, int start, int current_city, bool visited[], int min_cost) {
    if (current_city == n) {
        // 如果路径有效，计算总距离并更新最小成本
        if (is_valid_path(path, n, start, visited)) {
            int cost = 0;
            for (int i = 0; i < n; i++) {
                cost += manhattan_distance(&cities[path[i]], &cities[path[(i + 1) % n]]);
            }
            if (cost < min_cost) {
                min_cost = cost;
                printf("New minimum: %d\n", min_cost);
            }
        }
        return;
    }

    // 生成所有可能的下一位城市
    for (int next_city = start; next_city != current_city; next_city++) {
        visited[next_city] = true;
        tsp_backtrack(cities, n, path, start, current_city + 1, visited, min_cost);
        visited[next_city] = false;
    }
}

// 主函数
int main() {
    int n;
    printf("Enter the number of cities: ");
    scanf("%d", &n);
    City* cities = malloc(n * sizeof(City));
    // 假设输入城市坐标...
    // 为每个城市读取坐标...

    int* path = malloc(n * sizeof(int)); // 初始化路径
    bool visited[n]; // 记录已访问的城市
    tsp_backtrack(cities, n, path, 0, 0, visited, INT_MAX); // 从城市0开始

    free(path);
    free(cities);
    return 0;
}