题解 P7812 Dark Forest

· · 题解

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 左右。

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

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

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