1. 题目

传送门= ̄ω ̄=

2. 题解

网上基本上所有 Dalao 都是写的 “三分套三分”Orz

(好像 WJMZBMR 写的是模拟退火,为啥我一开始写模拟退火挂了呢 QvQ 可能我太弱了)

先讲下这题吧。

首先 lxhgww 的路径一定是从 $A$点上传送带 $AB$,走 $x$个单位时间 ($0\leq x\leq \frac{AB}{P}$),再下 $AB$传送带,徒步走上 $CD$传送带(不一定是在 $C$点上传送带),走 $y$个单位时间到达 $D$点 ($0\leq y\leq \frac{CD}{Q}$)

设用时为 $f(x,y)$($x,y$的意义见上文)

则:

设 $f1(t)$表示从 $A$点出发,沿着 $AB$走 $t$个单位时间后到达的坐标。

设 $f2(t)$表示从 $D$点出发,沿着 $DC$走 $t$个单位时间后到达的坐标。

那么:

$$f(x,y)=\frac{dis(f1(x),f2(y))}{R} + x + y$$

($dis$表示求两点之间的欧几里得距离)

好的,现在这个问题已经转化为了求一个二元函数的最小值

可以把函数放到三维空间里看成一个物体,要在一个矩形区域内找物体的最低点。

。。。

写挂模拟退火以后我就写了个粒子群优化算法。。。

这算法真 NB 啊,什么数学推导都不需要,完全把函数当做随机函数看都能过掉!

这个算法是模仿生物(鸟类)捕食的过程。把一堆粒子随机撒在函数定义域内,然后每次找出所有粒子中所在位置对应的函数值最优的粒子,并且让大家都尽量向这里加速

每个粒子都是有自己的惯性的,这样可以增加随机性,以免卡在局部最优解导致答案错误。

总之就是模拟真实的自然界啦。。。

具体很难说清楚,可以去网上搜一下这个算法,很玄妙的 QvQ

但是好像网上很少有(或者说可能根本没有)把粒子群优化算法这种人工智能算法应用于 OI 竞赛的,所以这里发一下代码,里面会写上注释的,还是看代码比较好懂=。=(其实是手缝针啦打字有点不舒服)

另外实验结果表明,粒子群算法更注重粒子个数。。。像我一开始那样开 20 个粒子就冲上去爆〇的做法真的不可取 QvQ

代码:

#include <bits/stdc++.h>

#define BS (505)//粒子数组大小
#define eps (1e-8)

using namespace std;

const int cnt = 500;//粒子个数

struct vec//向量
{
    double x, y;
    vec operator + (const vec oth) const
    {
        return (vec){x + oth.x, y + oth.y};
    }
    vec operator - (const vec oth) const
    {
        return (vec){x - oth.x, y - oth.y};
    }
    vec operator * (const double d) const
    {
        return (vec){x * d, y * d};
    }
    vec operator / (const double d) const
    {
        return (vec){x / d, y / d};
    }
};

vec A, B, C, D, P1, P2;

double P, Q, R, rx, ry;

vec f1(double x) {return A + P1 * x;}//和上文定义的 f1 意义相同

vec f2(double x) {return D + P2 * x;}//和上文定义的 f2 意义相同

double Squ(double a) {return a * a;}

double dis(vec a, vec b)//求 a,b 的欧几里得距离
{
    return sqrt(Squ(a.x - b.x) + Squ(a.y - b.y));
}

double f(double x, double y)//和上文定义的 f 意义相同
{
    return x + y + dis(f1(x), f2(y)) / R;
}

double Rand() {return (double)rand() / RAND_MAX;}//返回一个 [0,1] 的随机实数

struct Bird {double vx, vy, x, y, f, pb, pbx, pby;} b[BS];//粒子们

//vx,vy 是速度向量,x,y 是位置向量,f 是当前位置的函数值,pb 是该粒子历史最优值

double w = 1, gb = 1e233, gbx, gby;

//w 是精度权重, gb 是全局目前最优值, gbx,gby 是取到全局最优值时的自变量 x,y

void Update(int a)//更新粒子 a 的状态,这里具体原理请见算法实现原理
{
    b[a].vx = b[a].vx * w + Rand() * w * (gbx + b[a].pbx - b[a].x * 2);
    b[a].vy = b[a].vy * w + Rand() * w * (gby + b[a].pby - b[a].y * 2);
    //b[a].v * w 是因为有惯性,另外的项则是尽量像更优解靠近
    b[a].x += b[a].vx, b[a].y += b[a].vy;//更新位置向量
    //下面 4 行是防止粒子出界,出界则反弹回来(这里我没在网上找到相关资料介绍如何处理出界,所以是自己 YY 的)
    if (b[a].x < 0) b[a].x = 0, b[a].vx = -b[a].vx;
    if (b[a].y < 0) b[a].y = 0, b[a].vy = -b[a].vy;
    if (b[a].x > rx) b[a].x = rx, b[a].vx = -b[a].vx;
    if (b[a].y > ry) b[a].y = ry, b[a].vy = -b[a].vy;
    b[a].f = f(b[a].x, b[a].y);//计算当前位置函数值
    if (b[a].f < b[a].pb)//更新局部最优解
        b[a].pbx = b[a].x, b[a].pby = b[a].y, b[a].pb = b[a].f;
}

int main(int argc, char const* argv[])
{
    scanf("%lf%lf%lf%lf", &A.x, &A.y, &B.x, &B.y), P1 = B - A;
    scanf("%lf%lf%lf%lf", &C.x, &C.y, &D.x, &D.y), P2 = C - D;
    scanf("%lf%lf%lf", &P, &Q, &R), srand(P + Q + R);
    rx = dis(B, A) / P, ry = dis(D, C) / Q;
    if (!rx) P1.x = P1.y = 0; else P1 = P1 / rx;//特判传送带是一个点的情况
    if (!ry) P2.x = P2.y = 0; else P2 = P2 / ry;
    for (int i = 1; i <= cnt; i += 1)//随机撒点
    {
        b[i].x = b[i].pbx = Rand() * rx, b[i].y = b[i].pby = Rand() * ry;
        b[i].f = b[i].pb = f(b[i].x, b[i].y);
        b[i].vx = b[i].vy = 0;
        if (gb > b[i].pb) gbx = b[i].pbx, gby = b[i].pby, gb = b[i].pb;
    }
    for (int p = 1; p <= 900; p += 1, w *= 0.99)//迭代 900 次,0.99 的 900 次方已经对答案无影响
        for (int i = 1; i <= cnt; i += 1)
            if (Update(i), gb > b[i].pb)
                gbx = b[i].pbx, gby = b[i].pby, gb = b[i].pb;//更新全局最优解
    printf("%.2f\n", gb);
    return 0;
}
分类: 文章

XZYQvQ

炒鸡辣鸡的制杖蒟蒻一枚QvQ

2 条评论

litble · 2018年3月27日 9:36 下午

Orz 人工智能 dalao,马克一下,有时间再膜一膜这个算法

    konnyakuxzy · 2018年3月27日 10:43 下午

    Orz Dalao 不要吊打我啊 QvQ
    害怕.jpg
    哪有您的特殊分治技巧厉害呀 QvQ
    您太强啦 Orz%%%%%

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用 * 标注