---
# System prepended metadata

title: F74096297 作業六

---

# F74096297 作業六
* 螞蟻演算法 : 
      由該路線費洛蒙和路線長度決定螞蟻接下來走的路徑, 透過更新費洛蒙來逼近最短路徑 
* 題目要求 : 
    * 對該演算法使用 mpi 去做平行化
    * 螞蟻的必須走過所有節點
    * pheromone(t + 1) = (1 - p) * pheromone(t) + Q / Length_sum 的總和 
# 費洛蒙的更新
```cpp=
for(int i = 0 ; i < city_num; ++i)
    for(int j = 0; j < city_num; ++j)
        pheromone[j][i] = pheromone[i][j] *= decrease;
.
.
.
for(int j = 0 ; j < city_num ; ++j){
    pheromone[pos][j] += quantity / sum_path;
    pheromone[j][pos] = pheromone[pos][j];
}
```
# 輪盤 percent 的計算
```cpp=
pathed[pos] = 1;
pathed_path[city_num - can_path_sum - 1] = pos;

double sum = 0;
double p[can_path_sum] = {0};
pair<double , int> Max(0.0, 0);
for(int j = 0; j < city_num; ++j){
    if(pathed[j]) continue;
    double a = 1, b = 1;
    for(int k = 0; k < alpha ; ++k) a *= pheromone[pos][j];
        for(int k = 0; k < beta ; ++k) b /= path[pos][j];
            sum += p[j] = a + b;
        
    for(int j = 0; j < city_num; ++j){
    if(pathed[j]) continue;
    p[j] /= sum;

    if(p[j] > Max.X){
        Max.X = p[j];
        Max.Y = j;
    }
    cout << p[j]
}
int des = Max.Y;
sum_path += path[pos][des];
pos = des;
```