洛谷P2210 Haywire（模拟退火和遗传算法）

74 阅读 0 评论 49 点赞

我是靠谱客的博主孝顺小懒猪，这篇文章主要介绍洛谷P2210 Haywire（模拟退火和遗传算法），现在分享给大家，希望可以做个参考。

题目描述
Farmer John有 NN 只奶牛,(4 leq N leq 124≤N≤12,其中 NN 是偶数).

他们建立了一套原生的系统，使得奶牛与他的朋友可以通过由干草保护的线路来进行对话交流.

每一头奶牛在这个牧场中正好有3个朋友，并且他们必须把自己安排在一排干草堆中.

一条长 LL 的线路要占用刚好 LL 堆干草来保护线路。

比如说，如果有两头奶牛分别在草堆4与草堆7中，并且他们是朋友关系，那么我们就需要用3堆干草来建造线路，使他们之间能够联系.

假设每一对作为朋友的奶牛都必须用一条单独的线来连接，并且我们可以随便地改变奶牛的位置，请计算出我们建造线路所需要的最少的干草堆.

输入格式
第 11 行：一个整数 NN. 为了方便，我们给奶牛用 1sim N1∼N 的数字进行编号.

第 2…1+N2…1+N : 每一行都有三个在 1sim N1∼N 中的整数. 第 i+1i+1 行的数字代表着第i头奶牛的三个朋友的编号。显然，如果奶牛 ii 是奶牛 jj 的三个朋友之一，那么奶牛 jj 也是奶牛 ii 的三个朋友之一.

输出格式
一个整数，代表着建造线路需要的干草堆数量的最小值.

解法1：模拟退火
基本思路是每次保留一个排列，并对这个排列random_shufle，如果可以保留（计算出的结果小于原排列，或者概率命中）新排列则保留，否则保留原排列，最后计算答案的最小值即可
（不知道为什么感觉更像套着退火壳子的爬山）

#include<bits/stdc++.h>

using namespace std;
int n;
int f[20][3];
int p[20];
int q[20];
const double alpha = 0.995;
int ans = 1e9;

int value() {
    int now = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= 2; j++)
            if (f[i][j] > i)
                now += abs(p[f[i][j]] - p[i]);
    ans = min(ans, now);
    return now;
}

void sa() {
    double T = 3000.0;
    int now = ans;
    while (T > 1e-15) {
        for (int i = 1; i <= n; i++)q[i] = p[i];
        for (int i = n; i >= 1; i--)swap(p[i], p[rand() % i + 1]);
        int de = value() - now;
        if (de < 0)now += de;
        else if (exp(1.0 * de / T) * RAND_MAX > rand())now += de;
        else swap(p, q);
        T *= alpha;
    }
}

int main() {
    srand(time(nullptr));
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++)cin >> f[i][0] >> f[i][1] >> f[i][2];
    for (int i = 1; i <= n; i++)p[i] = i;
    ans = value();
    for (int i = 1; i <= 50; i++)
        sa();
    cout << ans;
    return 0;
}

解法2：遗传算法
初始建立一个大小为m的种群，每次淘汰一半，保留的一半每一个产生随机变异，迭代一定次数之后输出最小值即可
遗传的关键是找出迭代次数和种群大小之间的平衡，这道题似乎对迭代次数要求不高，可以略微调小一点，我的遗传就是卡着时限过的

#include<bits/stdc++.h>

using namespace std;
int n;
int f[20][3];
int ans = 1e9;
const int m = 20000;
struct stock {
    int p[20];
    int v;
} arr[m + 10];

bool cmp(stock a, stock b) {
    return a.v < b.v;
}

int value(stock x) {
    int now = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= 2; j++)
            if (f[i][j] > i)
                now += abs(x.p[f[i][j]] - x.p[i]);
    ans = min(ans, now);
    return now;
}

void Breed(int mother, int son) {
    int x = 0, y = 0;
    while (x == y)
        x = rand() % n + 1, y = rand() % n + 1;
    swap(arr[mother].p[x], arr[mother].p[y]);//随机产生一点点的变异
    for (int k = 1; k <= n; k++)
        arr[son].p[k] = arr[mother].p[k];
    arr[son].v = value(arr[son]);
    swap(arr[mother].p[x], arr[mother].p[y]);
    //cerr << mother << ' ' << son << endl;
}

void Genetic() {
    int T = 50;
    while (T--) {
        //保留前40个优秀基因，淘汰60个
        //越优秀的基因可以繁殖越多的后代，排名前5的可以繁殖3个，前15的可以繁殖2个，前40的可以繁殖1个
        int cnt = m / 2;
        for (int i = 1; i <= m / 2; i++)Breed(i, ++cnt);
        sort(arr + 1, arr + n + 1, cmp);
    }
}

void init() {
    for (int i = 1; i <= m; i++) {//随机生成m组初始基因
        for (int j = 1; j <= n; j++)
            arr[i].p[j] = j;
        for (int j = n; j >= 1; j--)
            swap(arr[i].p[j], arr[i].p[rand() % j + 1]);
        arr[i].v = value(arr[i]);
    }
    sort(arr + 1, arr + m + 1, cmp);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 1; i <= n; i++)cin >> f[i][0] >> f[i][1] >> f[i][2];
    for (int i = 1; i <= 10; i++) {
        srand(time(nullptr));
        init();
        Genetic();
    }
    cout << ans << endl;
    return 0;
}