蚁群算法（C语言实现）

蚁群算法是一种模拟蚂蚁觅食行为的启发式算法，常用于求解NP难问题，比如旅行商问题、图着色问题等。以下是一个简单的蚁群算法的C语言实现。

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

#define MAX_CITY_NUM 100 // 最大城市数
#define MAX_ANT_NUM 100 // 最大蚂蚁数
#define MAX_GEN_NUM 100 // 最大迭代次数
#define ALPHA 1.0 // 信息素重要程度因子
#define BETA 2.0 // 启发式因子
#define RHO 0.5 // 信息素挥发因子
#define Q 100 // 信息素强度常数
#define MAX(x, y) ((x) > (y) ? (x) : (y)) // 宏定义求最大值

int city_num; // 城市数量
int ant_num; // 蚂蚁数量
int gen_num; // 迭代次数
double distance[MAX_CITY_NUM][MAX_CITY_NUM]; // 城市距离矩阵
double pheromone[MAX_CITY_NUM][MAX_CITY_NUM]; // 信息素矩阵
int ants[MAX_ANT_NUM][MAX_CITY_NUM]; // 蚂蚁走过的路径
double best_distance = 1e9; // 最短路径长度
int best_path[MAX_CITY_NUM]; // 最短路径
double delta_pheromone[MAX_CITY_NUM][MAX_CITY_NUM]; // 每只蚂蚁释放的信息素

// 生成[0, 1)之间的随机数
double rand_double() {
    return rand() / (double)RAND_MAX;
}

// 初始化城市距离矩阵
void init_distance() {
    srand((unsigned int)time(NULL)); // 设置随机数种子
    for (int i = 0; i < city_num; i++) {
        for (int j = i + 1; j < city_num; j++) {
            double d = rand_double() * 100; // 生成[0, 100)之间的随机数
            distance[i][j] = distance[j][i] = d;
        }
    }
}

// 初始化信息素矩阵
void init_pheromone() {
    for (int i = 0; i < city_num; i++) {
        for (int j = 0; j < city_num; j++) {
            pheromone[i][j] = 1.0; // 初始信息素强度为1
        }
    }
}

// 选择下一个城市
int select_next_city(int ant, int cur_city) {
    double p[MAX_CITY_NUM]; // 保存选择概率
    double sum_prob = 0.0; // 概率之和
    for (int i = 0; i < city_num; i++) {
        if (ants[ant][i] == -1) { // 判断城市是否已经被走过
            double prob = pheromone[cur_city][i] * pow(1.0 / distance[cur_city][i], BETA); // 计算选择概率
            p[i] = prob;
            sum_prob += prob;
        }
        else {
            p[i] = 0.0;
        }
    }
    if (sum_prob == 0.0) { // 如果所有城市都已被走过，返回-1表示没有下一个城市可走
        return -1;
    }
    double r = rand_double() * sum_prob; // 生成[0, sum_prob)之间的随机数
    double sum = 0.0;
    for (int i = 0; i < city_num; i++) {
        if (ants[ant][i] == -1) {
            sum += p[i];
            if (sum >= r) {
                return i;
            }
        }
    }
    return -1; // 这里实际上不会执行到
}

// 模拟一只蚂蚁走一遍路径
void simulate_ant(int ant) {
    for (int i = 0; i < city_num; i++) {
        ants[ant][i] = -1; // 初始化蚂蚁没有走过任何城市
    }
    int start_city = rand() % city_num; // 随机选择一个起点城市
    ants[ant][0] = start_city; // 将起点城市设置为第一个走过的城市
    for (int i = 1; i < city_num; i++) {
        int cur_city = ants[ant][i - 1]; // 当前所在城市
        int next_city = select_next_city(ant, cur_city); // 选择下一个城市
        if (next_city == -1) { // 如果没有下一个城市可走，跳出循环
            break;
        }
        ants[ant][i] = next_city; // 将下一个城市设置为下一个走过的城市
    }
}

// 更新信息素矩阵
void update_pheromone() {
    for (int i = 0; i < city_num; i++) {
        for (int j = 0; j < city_num; j++) {
            delta_pheromone[i][j] = 0.0; // 初始化每只蚂蚁释放的信息素为0
        }
    }
    for (int k = 0; k < ant_num; k++) { // 每只蚂蚁都要更新信息素
        double distance_k = 0.0; // 蚂蚁k走过的路径长度
        for (int i = 1; i < city_num; i++) {
            int cur_city = ants[k][i - 1];
            int next_city = ants[k][i];
            distance_k += distance[cur_city][next_city];
        }
        if (distance_k < best_distance) { // 如果蚂蚁k找到了更短的路径，更新最短路径
            best_distance = distance_k;
            for (int i = 0; i < city_num; i++) {
                best_path[i] = ants[k][i];
            }
        }
        for (int i = 1; i < city_num; i++) {
            int cur_city = ants[k][i - 1];
            int next_city = ants[k][i];
            delta_pheromone[cur_city][next_city] += Q / distance_k; // 蚂蚁k释放的信息素
        }
        delta_pheromone[ants[k][city_num - 1]][ants[k][0]] += Q / distance_k; // 蚂蚁k释放的信息素
    }
    for (int i = 0; i < city_num; i++) {
        for (int j = 0; j < city_num; j++) {
            pheromone[i][j] = pheromone[i][j] * (1 - RHO) + delta_pheromone[i][j]; // 更新信息素
        }
    }
}

// 主函数
int main() {
    scanf("%d%d%d", &city_num, &ant_num, &gen_num); // 读入城市数量、蚂蚁数量、迭代次数
    init_distance(); // 初始化城市距离矩阵
    init_pheromone(); // 初始化信息素矩阵
    for (int gen = 0; gen < gen_num; gen++) { // 迭代gen_num次
        for (int ant = 0; ant < ant_num; ant++) { // 每次迭代每只蚂蚁都要走一遍
            simulate_ant(ant);
        }
        update_pheromone(); // 更新信息素矩阵
    }
    printf("最短路径长度: %.2lf\n", best_distance);
    printf("最短路径: ");
    for (int i = 0; i < city_num; i++) {
        printf("%d ", best_path[i]);
    }
    printf("\n");
    return 0;
}

这段代码实现了一个简单的蚁群算法，读入城市数量、蚂蚁数量、迭代次数，随机生成城市距离矩阵和初始信息素矩阵，每次迭代每只蚂蚁走一遍路径，更新信息素矩阵，最后输出最短路径长度和最短路径。代码中用了一些宏定义和全局变量，可能不太符合一般的编程规范，但是为了简洁易懂而这么写了。