模拟退火
模拟退火是一种随机化算法,可以用来求解某些数据范围较小的最优化问题。由于其通常不能保证正确性,因此一般在数据量非常小或者题目允许输出近似值时才使用。
假如我们要最小化一个多元函数 \(f(s)\) 的值。我们先选择一个初始状态 \(s=s_0\)。模拟退火就是根据某些规则转移 \(s\),直到其收敛到最优解附近。
其规则具体如下:
- 初始时有一个变量 \(T\) 表示当前温度;
- 若 \(T\ge lim\):
- 随机转移到 \(s\) 附近的一个新状态 \(s'\),计算 \(f(s')\);
- 如果 \(f(s')\le f(s)\),则直接转移:\(s\leftarrow s'\);
- 否则,以 \(p=\exp(-\frac{f(s')-f(s)}T)\) 的概率转移:\(s\leftarrow s'\);
- 否则,不进行转移;
- \(T'\leftarrow T\times stp\);
\(stp\) 一般取 \(0.99999\),\(lim\) 取 \(10^{-15}\),\(T\) 和转移代价有关,一般 \(\ge 5\)。
- 找到高效计算 \(f(s)\) 的算法可以减少单次转移的时间消耗,提高退火次数;
- \((1-stp)\) 一般不小于 \(10^{-5}\),否则会超时;
- 提取关键影响 \(f\) 值的信息,缩短初始状态和最优解之间的距离,也可以更准确的找到最优解;
选择合适的状态和转移,剩下的就是套板子。
P2210 Haywire
代码
P3936 Coloring
代码
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 |
|
250520 模拟赛 T1
题意
有一张 \(n\) 个节点 \(m\) 条边的有向图。你可以进行若干次操作(至少一次),每次操作你选择一个节点 \(u\),将 \(u\) 指向的所有节点的点权 --w[v]
,将所有指向 \(u\) 的节点的点权 ++w[v]
。最小化点权最大值。
\(n\le 50,\ m\le 1000\)
操作次数不应超过 \(10^5\);