蚁群算法求解tsp c语言

以下是使用蚁群算法求解TSP问题的C语言代码：

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

#define N 20 // 城市数量
#define M 100 // 蚂蚁数量
#define ALPHA 1.0 // 信息素重要程度因子
#define BETA 5.0 // 启发函数重要程度因子
#define RHO 0.5 // 信息素挥发因子
#define Q 100 // 常系数
#define MAX_T 200 // 运行代数
#define MAX_DIST 100000 // 最大距离

double dist[N][N]; // 城市之间的距离矩阵
double pheromone[N][N]; // 信息素矩阵
int best_path[N]; // 最优路径
double best_length; // 最优路径长度

// 计算两个城市之间的距离
double calc_dist(int i, int j) {
    return sqrt(pow(i - j, 2) + pow(i - j, 2));
}

// 初始化城市之间的距离矩阵
void init_dist() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            dist[i][j] = calc_dist(i, j);
        }
    }
}

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

// 计算蚂蚁k从城市i到城市j的启发值
double calc_eta(int i, int j, int visited[]) {
    double sum = 0.0;
    for (int k = 0; k < N; k++) {
        if (!visited[k]) {
            sum += pow(pheromone[i][k], ALPHA) * pow(1.0 / dist[i][k], BETA);
        }
    }
    return pow(pheromone[i][j], ALPHA) * pow(1.0 / dist[i][j], BETA) / sum;
}

// 选择下一个要访问的城市
int select_next(int k, int visited[]) {
    double p[N];
    double p_sum = 0.0;
    int cur_city = visited[k];
    for (int i = 0; i < N; i++) {
        if (!visited[i]) {
            p[i] = calc_eta(cur_city, i, visited);
            p_sum += p[i];
        }
    }
    double r = (double)rand() / RAND_MAX;
    double a = 0.0;
    for (int i = 0; i < N; i++) {
        if (!visited[i]) {
            a += p[i] / p_sum;
            if (r <= a) {
                return i;
            }
        }
    }
    return -1;
}

// 计算路径长度
double calc_length(int path[]) {
    double len = 0.0;
    for (int i = 0; i < N - 1; i++) {
        len += dist[path[i]][path[i + 1]];
    }
    len += dist[path[N - 1]][path[0]];
    return len;
}

// 更新信息素矩阵
void update_pheromone() {
    double delta_pheromone[N][N];
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            delta_pheromone[i][j] = 0.0;
        }
    }
    for (int k = 0; k < M; k++) {
        int path[N];
        int visited[N];
        for (int i = 0; i < N; i++) {
            visited[i] = 0;
        }
        int start_city = rand() % N;
        path[0] = start_city;
        visited[start_city] = 1;
        for (int i = 1; i < N; i++) {
            int next_city = select_next(k, visited);
            path[i] = next_city;
            visited[next_city] = 1;
        }
        double length = calc_length(path);
        for (int i = 0; i < N - 1; i++) {
            delta_pheromone[path[i]][path[i + 1]] += Q / length;
        }
        delta_pheromone[path[N - 1]][path[0]] += Q / length;
        if (length < best_length) {
            best_length = length;
            for (int i = 0; i < N; i++) {
                best_path[i] = path[i];
            }
        }
    }
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            pheromone[i][j] = pheromone[i][j] * (1.0 - RHO) + delta_pheromone[i][j];
        }
    }
}

// 主函数
int main() {
    srand(time(NULL));
    init_dist();
    init_pheromone();
    best_length = MAX_DIST;
    for (int t = 0; t < MAX_T; t++) {
        update_pheromone();
    }
    printf("Best path: ");
    for (int i = 0; i < N; i++) {
        printf("%d ", best_path[i]);
    }
    printf("\nBest length: %lf\n", best_length);
    return 0;
}

该代码使用了蚁群算法来解决TSP问题，其中包括初始化城市之间的距离矩阵和信息素矩阵、计算蚂蚁的启发值、选择下一个要访问的城市、计算路径长度、更新信息素矩阵等操作。最后输出最优路径和最优路径长度。