c++代码实现蚁群算法遍历无向图求经过所有节点求最短路径

以下是使用C++实现蚁群算法遍历无向图求解最短路径的示例代码：

#include <iostream>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <ctime>

using namespace std;

const int MAXN = 100; // 最大节点数
const double ALPHA = 1.0; // 信息素重要程度
const double BETA = 5.0; // 启发式因子重要程度
const double RHO = 0.5; // 信息素挥发因子
const double Q = 100.0; // 信息素增加强度系数
const int MAX_GEN = 100; // 最大迭代次数

// 无向图类
class Graph {
public:
    Graph(int n) : n_(n) {
        // 初始化邻接矩阵
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) {
                    adj_matrix_[i][j] = 0.0;
                } else {
                    adj_matrix_[i][j] = adj_matrix_[j][i] = (double)(rand() % 100 + 1);
                }
            }
        }
    }

    double get_edge(int i, int j) const { return adj_matrix_[i][j]; }
    int get_n() const { return n_; }

private:
    double adj_matrix_[MAXN][MAXN];
    int n_;
};

// 蚂蚁类
class Ant {
public:
    Ant(int start, int n) : cur_node_(start), tabu_(n, false), tour_length_(0.0) {
        tabu_[start] = true;
        tour_.push_back(start);
    }

    void choose_next(const Graph& graph) {
        double sum = 0.0;
        double p[MAXN] = {0.0};
        for (int i = 0; i < graph.get_n(); i++) {
            if (!tabu_[i]) {
                p[i] = pow(graph.get_edge(cur_node_, i), ALPHA) * pow(1.0 / (1.0 + tour_length_), BETA);
                sum += p[i];
            }
        }

        double rand_val = (double)(rand() % 10000) / 10000.0;
        double select_val = rand_val * sum;
        int next_node = -1;
        double tmp_sum = 0.0;
        for (int i = 0; i < graph.get_n(); i++) {
            if (!tabu_[i]) {
                tmp_sum += p[i];
                if (tmp_sum >= select_val) {
                    next_node = i;
                    break;
                }
            }
        }

        if (next_node == -1) {
            for (int i = 0; i < graph.get_n(); i++) {
                if (!tabu_[i]) {
                    next_node = i;
                    break;
                }
            }
        }

        tour_.push_back(next_node);
        tabu_[next_node] = true;
        tour_length_ += graph.get_edge(cur_node_, next_node);
        cur_node_ = next_node;
    }

    void update_pheromone(double delta_pheromone[MAXN][MAXN]) {
        for (int i = 0; i < tour_.size() - 1; i++) {
            int from = tour_[i], to = tour_[i + 1];
            delta_pheromone[from][to] += Q / tour_length_;
            delta_pheromone[to][from] += Q / tour_length_;
        }
    }

    const vector<int>& get_tour() const { return tour_; }
    double get_tour_length() const { return tour_length_; }

private:
    int cur_node_;
    vector<bool> tabu_;
    vector<int> tour_;
    double tour_length_;
};

// 蚁群算法类
class ACO {
public:
    ACO(int num_ants, double evap_rate, double init_pheromone)
        : num_ants_(num_ants), evap_rate_(evap_rate), init_pheromone_(init_pheromone) {}

    vector<int> solve(const Graph& graph) {
        // 初始化信息素矩阵
        double pheromone[MAXN][MAXN];
        for (int i = 0; i < graph.get_n(); i++) {
            for (int j = 0; j < graph.get_n(); j++) {
                pheromone[i][j] = init_pheromone_;
            }
        }

        // 迭代搜索
        vector<int> best_tour;
        double best_tour_length = 1e9;
        for (int gen = 0; gen < MAX_GEN; gen++) {
            vector<Ant> ants;
            for (int i = 0; i < num_ants_; i++) {
                ants.push_back(Ant(rand() % graph.get_n(), graph.get_n()));
            }

            double delta_pheromone[MAXN][MAXN] = {0.0};
            for (int i = 0; i < num_ants_; i++) {
                for (int j = 1; j < graph.get_n(); j++) {
                    ants[i].choose_next(graph);
                }
                ants[i].update_pheromone(delta_pheromone);
                if (ants[i].get_tour_length() < best_tour_length) {
                    best_tour = ants[i].get_tour();
                    best_tour_length = ants[i].get_tour_length();
                }
            }

            // 更新信息素
            for (int i = 0; i < graph.get_n(); i++) {
                for (int j = 0; j < graph.get_n(); j++) {
                    pheromone[i][j] = pheromone[i][j] * (1.0 - evap_rate_) + delta_pheromone[i][j];
                }
            }
        }

        return best_tour;
    }

private:
    int num_ants_;
    double evap_rate_;
    double init_pheromone_;
};

int main() {
    srand(time(NULL));

    // 创建无向图
    Graph graph(10);

    // 创建蚁群算法对象并求解
    ACO aco(10, RHO, 1.0 / (double)graph.get_n());
    vector<int> tour = aco.solve(graph);

    // 输出结果
    cout << "Best tour length: " << endl;
    cout << tour.size() << endl;
    for (int i = 0; i < tour.size(); i++) {
        cout << tour[i] << " ";
    }
    cout << endl;

    return 0;
}

在该示例代码中，我们使用了一个简单的随机图（即每条边的权重为随机值），并使用上文提到的蚁群算法求解该图中经过所有节点的最短路径。在代码中，我们定义了 `Graph` 类表示无向图，`Ant` 类表示蚂蚁，`ACO` 类表示蚁群算法。在 `ACO` 类的 `solve` 方法中，我们进行了多次迭代搜索，并在每次迭代中更新信息素。最终，我们输出了找到的最优路径及其长度。