粒子群算法

概述

这是一种随机算法

模仿鸟类捕食

在定义域中随机撒 nn 个点,需要维护(以二维定义域为例)

  • 坐标 p(x,y)p(x,y)
  • 速度 vv ,一个二维向量
  • 历史最优值 pbpb 和其坐标

同时还要维护全局最优解及其坐标

定义三个常数 ω,c1,c2\omega,c_1,c_2

每次更新点的速度

v=ωv+c1(pbp)+c2(gbp) v=\omega v+c_1(pb-p)+c_2(gb-p)

更新坐标

p=p+v p=p+v

最后更新 pb,gbpb,gb

传送带

题目概述

LOJ #10017. 「一本通 1.2 练习 4」传送带 原题来自:SCOI 2010

在一个 22 维平面上有两条传送带,每一条传送带可以看成是一条线段。两条传送带分别为线段 AB\text{AB} 和线段 CD\text{CD}。lxhgww 在 AB\text{AB} 上的移动速度为 PP ,在 CD\text{CD} 上的移动速度为 QQ ,在平面上的移动速度 RR

现在 lxhgww 想从 AA 点走到 DD 点,他想知道最少需要走多长时间。

三分的做法显然

假设在 AB\text{AB} 上走 xx 秒,假设在 CD\text{CD} 上走 yy 秒,总时间为 f(x,y)f(x,y),然后注意边界直接跑就行

随机 1000 组数据有 97% 的正确率

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <deque>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
#define rep(i, l, r) for (int i = (l); i <= (r); ++i)
#define Rn(n) for (int i = 0; i < (n); ++i)
#define per(i, l, r) for (int i = (l); i >= (r); --i)
using std::cerr;
using std::cin;
using std::cout;
using std::endl;
using std::make_pair;
using std::pair;
typedef pair<int, int> pii;
typedef long long ll;
typedef unsigned int ui;

const int cnt = 1000, inf = 0x3f3f3f3f;

inline double dis(double a, double b) { return std::sqrt(a * a + b * b); }

struct Vector {
double x, y, len;
Vector() { x = 0, y = 0, len = 0; }
Vector(double _x, double _y) { x = _x, y = _y, calc(); }
void calc() { len = dis(x, y); }
Vector& operator+=(const Vector& b) {
x += b.x;
y += b.y;
calc();
return *this;
}
Vector operator+(const Vector& b) const {
Vector n(x + b.x, y + b.y);
return n;
}
Vector operator-(const Vector& b) const {
Vector n(x - b.x, y - b.y);
return n;
}
Vector operator*(double k) const {
Vector n(x * k, y * k);
return n;
}
} gb, a, b, c, d, uab, udc;

double gb_a, p, q, r, mx, my;

inline double dis(Vector a, Vector b) { return dis(a.x - b.x, a.y - b.y); }

double omega = 0.4, c1 = 2, c2 = 2;

std::random_device rd;
std::mt19937 gen(rd());
std::uniform_real_distribution<> qwq(0, 1);

double rr() { return qwq(gen); } // 返回 [0,1) 实数

struct Unit {
Vector p, v, pb;
double pb_a;
double ans() { return p.x + p.y + dis(a + uab * p.x, d + udc * p.y) / r; }
void upd_v() { v = v * omega + (pb - v) * c1 * rr() + (gb - v) * c2 * rr(); }
void upd() {
upd_v();
p += v;
if (p.x < 0) p.x = 0;
if (p.y < 0) p.y = 0;
if (p.x > mx) p.x = mx;
if (p.y > my) p.y = my;
double c = ans();
if (c <= pb_a) {
pb = p, pb_a = c;
if (c <= gb_a)
gb = p, gb_a = c;
}
}
} u[cnt];

int main() {
std::ios::sync_with_stdio(false);
cout.tie(0);
int t1, t2;
cin >> t1 >> t2;
a = Vector(t1, t2);
cin >> t1 >> t2;
b = Vector(t1, t2);
cin >> t1 >> t2;
c = Vector(t1, t2);
cin >> t1 >> t2;
d = Vector(t1, t2);
uab = b - a;
udc = c - d;
cin >> p >> q >> r;
mx = uab.len / p;
my = udc.len / q;
uab = (uab.len == 0 ? Vector(0, 0) : uab * (p / uab.len));
udc = (udc.len == 0 ? Vector(0, 0) : udc * (q / udc.len));
gb_a = inf;
Rn(cnt) {
u[i].p = u[i].pb = Vector(mx * rr(), my * rr());
u[i].pb_a = u[i].ans();
if (u[i].pb_a < gb_a)
gb_a = u[i].pb_a, gb = u[i].p;
}
rep(ewq, 1, 500) {
Rn(cnt) { u[i].upd(); }
}
cout.setf(std::ios::fixed);
cout << std::setprecision(2) << gb_a << endl;
return 0;
}
作者

Gesrua

发布于

2019-05-05

更新于

2020-11-21

许可协议