Cogs 线型网络

题解

解

1

最优组合问题
传统的动态规划算法 $O(n^22^n)$ 在 $n = 20$ 的情况下空间、时间、精度
并不优秀
我们尝试使用随机化算法
可以用退火过掉这道题
我们考虑可以枚举全排列进行选择，这样的解一定是最优的
但这样和动态规划没有太大的不同
考虑，如果某次尝试已经得到了一个不错的解，如果大面积打乱就不是一个好的选择，只需改动该排列中的几个位置。

2

下面介绍模拟退火算法在该题中的应用
首先初始化排列
每次改动几个位置后计算出解
如果该解比当前解更优，就接受该解
否则以一定的概率接受该解
这个接受方法在之前提到过

inline bool Accept(DB delta, DB now_t) {
    if(delta <= 0) return 1;
    return rand() <= exp((- delta) / now_t) * RAND_MAX;
}
inline DB Work() {
    DB now_t = Max_t;
    Node p;
    while(now_t > 0.01) {
        Node p2(p);
        if(Accept(p2.Dis() - p.Dis(), now_t)) p = p2;
        now_t *= Delta;
    }
    return p.Dis();
}

很显然这个 $Work$ 函数我们要多执行几遍

Code

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <cstdlib>
using namespace std;
const int N = 25;
#define DB double
int n;
DB x[N], y[N], dis[N][N];
const DB Max_t = 10000;
const DB Delta = 0.999;
struct Node {
    int path[N];
    Node() {
        for(int i = 0; i <= n; i ++)
        path[i] = i;
    }
    Node(const Node & a) {
        for(int i = 0; i <= n; i ++) path[i] = a.path[i];
        std:: swap(path[rand() % n + 1], path[rand() % n + 1]); 
    }
    inline DB Dis() {
        DB ret = 0;
        for(int i = 1; i <= n; i ++) {
            ret += dis[path[i - 1]][path[i]];
        }
        return ret;
    }
};
inline bool Accept(DB delta, DB now_t) {
    if(delta <= 0) return 1;
    return rand() <= exp((- delta) / now_t) * RAND_MAX;
}
inline DB Work() {
    DB now_t = Max_t;
    Node p;
    while(now_t > 0.01) {
        Node p2(p);
        if(Accept(p2.Dis() - p.Dis(), now_t)) p = p2;
        now_t *= Delta;
    }
    return p.Dis();
}
int main() {
    freopen("linec.in", "r", stdin);
    freopen("linec.out", "w", stdout);
    srand(220180505);
    std:: cin >> n;
    for(int i = 1; i <= n; i ++) std:: cin >> x[i] >> y[i];
    for(int i = 1; i <= n; i ++) {
        dis[i][i] = 0;
        for(int j = i + 1; j <= n; j ++)
            dis[i][j] = dis[j][i] = hypot(x[i] - x[j], y[i] - y[j]);
    }
    DB Answer = 1e18;
    int T = 200;
    for(; T; T --) {
        DB imp = Work();
        Answer = std:: min(Answer, imp);    
    }
    printf("%.2lf", Answer);
    return 0;
}