自动搬运

查看原文

来自洛谷，原作者为

	critnos 咔菲好喝。

搬运于2025-08-24 22:33:19，当前版本为作者最后更新于2021-02-19 10:25:20，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

1

全排列。

2

写了一个丢人的 $O(n^3 2^n)$ 的状压 dp 跑了 2min。

3

大眼观察不难得到结论：当 $n\ge 4$ 时，初始排列为 $\{1,2,3\}$，后面从 $4$ 开始每个数 $x$ 插入到 $x-1$ 和 $x-2$ 之间。

遗传应该比较难过，跑一晚上没准能过呢（

4~5

给退火的（我本机用退火跑 1s 造的数据，但是用退火过掉这两个点却很困难，不知道为什么）。

6~10

本来想给裸的遗传一点部分分的，然后发现裸的遗传比退火还差。

这些点是给遗传的。

定义“基因”为排列 $p$，定义一次“变异”为交换 $p$ 中的两个元素，定义一个基因的“优秀程度”为他的权值。

其实我写的也不算遗传（我用 TSP 尝试了下交配，发现并不比用大量变异代替交配优秀，另外多种群遗传也不比这个优秀），就是每次让每个基因变异生成 $10$ 个儿子，然后按照权值排序。限制种群大小，生成下一代之后只保留最优秀的 $maxn$ 个。

同时采取保留精英策略，把父辈中的最优秀基因完整复制到下一代中。

但这样仍然不足以通过本题，还需要一个优化：因为遗传局部收敛比较慢，所以改良上面的保留精英策略，把父辈中的最优秀基因先变异一次，然后对它爬山，爬山 $10000$ 次基本就可以了。

在测试 TSP 问题的时候，同样跑 10s，退火和爬山均是 28w 左右（路线总长），遗传是 25w 左右，上面的做法可以去到 16w 左右。

没有实现粒子群和蚁群，不知道能不能通过本题。

物竞天择，适者生存，这才是题目真正的意义。

代码不放了，需要者私信。