旅行商问题代码c语言实现

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

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

#define POP_SIZE 100  // 种群大小
#define CROSS_RATE 0.8  // 交叉率
#define MUTATION_RATE 0.01  // 突变率
#define N_GENERATIONS 500  // 迭代次数
#define N_CITIES 20  // 城市数量

// 定义城市结构体
typedef struct {
    float x, y;
} City;

City cities[N_CITIES];  // 城市数组

// 生成城市坐标
void init_cities() {
    srand(time(NULL));
    for (int i = 0; i < N_CITIES; i++) {
        cities[i].x = (float) rand() / RAND_MAX * 100;
        cities[i].y = (float) rand() / RAND_MAX * 100;
    }
}

// 计算两个城市之间的距离
float get_distance(City city1, City city2) {
    float x1 = city1.x, y1 = city1.y;
    float x2 = city2.x, y2 = city2.y;
    return sqrt(pow(x1 - x2, 2) + pow(y1 - y2, 2));
}

// 计算路径长度
float get_fitness(int *individual) {
    float distance = 0;
    for (int i = 0; i < N_CITIES - 1; i++) {
        City city1 = cities[individual[i]];
        City city2 = cities[individual[i+1]];
        distance += get_distance(city1, city2);
    }
    City city1 = cities[individual[N_CITIES - 1]];
    City city2 = cities[individual[0]];
    distance += get_distance(city1, city2);
    return 1 / distance;
}

// 随机生成初始种群
void init_pop(int (*pop)[N_CITIES]) {
    for (int i = 0; i < POP_SIZE; i++) {
        for (int j = 0; j < N_CITIES; j++) {
            pop[i][j] = j;
        }
        for (int j = 0; j < N_CITIES; j++) {
            int index = rand() % N_CITIES;
            int temp = pop[i][j];
            pop[i][j] = pop[i][index];
            pop[i][index] = temp;
        }
    }
}

// 选择
void selection(int (*pop)[N_CITIES], float *fitness, int (*parents)[2]) {
    for (int i = 0; i < POP_SIZE; i++) {
        int index1 = rand() % POP_SIZE;
        int index2 = rand() % POP_SIZE;
        if (fitness[index1] > fitness[index2]) {
            parents[i][0] = index1;
        } else {
            parents[i][0] = index2;
        }
        index1 = rand() % POP_SIZE;
        index2 = rand() % POP_SIZE;
        if (fitness[index1] > fitness[index2]) {
            parents[i][1] = index1;
        } else {
            parents[i][1] = index2;
        }
    }
}

// 交叉
void crossover(int (*pop)[N_CITIES], int (*parents)[2], int (*offspring)[N_CITIES]) {
    for (int i = 0; i < POP_SIZE; i++) {
        if ((float) rand() / RAND_MAX < CROSS_RATE) {
            int index1 = rand() % N_CITIES;
            int index2 = rand() % N_CITIES;
            if (index1 > index2) {
                int temp = index1;
                index1 = index2;
                index2 = temp;
            }
            for (int j = index1; j <= index2; j++) {
                offspring[i][j] = pop[parents[i][0]][j];
            }
            int k = 0;
            for (int j = 0; j < N_CITIES; j++) {
                if (k == index1) {
                    k = index2 + 1;
                }
                if (k < N_CITIES && !contains(offspring[i], k, pop[parents[i][1]][j])) {
                    offspring[i][k] = pop[parents[i][1]][j];
                    k++;
                }
            }
        } else {
            for (int j = 0; j < N_CITIES; j++) {
                offspring[i][j] = pop[parents[i][0]][j];
            }
        }
    }
}

// 突变
void mutation(int (*offspring)[N_CITIES]) {
    for (int i = 0; i < POP_SIZE; i++) {
        if ((float) rand() / RAND_MAX < MUTATION_RATE) {
            int index1 = rand() % N_CITIES;
            int index2 = rand() % N_CITIES;
            int temp = offspring[i][index1];
            offspring[i][index1] = offspring[i][index2];
            offspring[i][index2] = temp;
        }
    }
}

// 替换
void replacement(int (*pop)[N_CITIES], float *fitness, int (*offspring)[N_CITIES], float *offspring_fitness) {
    for (int i = 0; i < POP_SIZE; i++) {
        if (offspring_fitness[i] > fitness[i]) {
            for (int j = 0; j < N_CITIES; j++) {
                pop[i][j] = offspring[i][j];
            }
            fitness[i] = offspring_fitness[i];
        }
    }
}

// 判断一个值是否在数组中
int contains(int *array, int length, int value) {
    for (int i = 0; i < length; i++) {
        if (array[i] == value) {
            return 1;
        }
    }
    return 0;
}

// 输出结果
void print_result(int *best_individual, float best_fitness) {
    printf("最短路径长度：%.2f\n", 1 / best_fitness);
    printf("最短路径：");
    for (int i = 0; i < N_CITIES; i++) {
        printf("%d ", best_individual[i]);
    }
    printf("\n");
}

int main() {
    init_cities();  // 生成城市坐标
    int pop[POP_SIZE][N_CITIES];  // 种群数组
    init_pop(pop);  // 随机生成初始种群
    float fitness[POP_SIZE];  // 适应度数组
    for (int i = 0; i < POP_SIZE; i++) {
        fitness[i] = get_fitness(pop[i]);  // 计算适应度
    }
    int parents[POP_SIZE][2];  // 父代数组
    int offspring[POP_SIZE][N_CITIES];  // 子代数组
    float offspring_fitness[POP_SIZE];  // 子代适应度数组
    for (int generation = 0; generation < N_GENERATIONS; generation++) {
        selection(pop, fitness, parents);  // 选择
        crossover(pop, parents, offspring);  // 交叉
        mutation(offspring);  // 突变
        for (int i = 0; i < POP_SIZE; i++) {
            offspring_fitness[i] = get_fitness(offspring[i]);  // 计算子代适应度
        }
        replacement(pop, fitness, offspring, offspring_fitness);  // 替换
    }
    int best_individual[N_CITIES];  // 最优个体
    float best_fitness = 0;  // 最优适应度
    for (int i = 0; i < POP_SIZE; i++) {
        if (fitness[i] > best_fitness) {
            best_fitness = fitness[i];
            for (int j = 0; j < N_CITIES; j++) {
                best_individual[j] = pop[i][j];
            }
        }
    }
    print_result(best_individual, best_fitness);  // 输出结果
    return 0;
}

该代码使用遗传算法来求解旅行商问题，使用欧氏距离作为城市之间的距离。通过遗传算法的迭代过程，不断优化种群中的个体，最终得到一条最短路径。