原题连接

TCO2018 Marathon Round2 问题 CrystalLighting 地址.

问题简述：

• $N * M$的网格，有些格子里有一些水晶（Crystal），有些格子是个障碍物，有些格子是空的；
• 每个水晶有独特的颜色，其中有3个单色：blue (1), yellow (2) and red (4)，和3个复色green (3 = blue + yellow), violet (5 = blue + red) and orange (6 = yellow + red)；
• 水晶正常是不发光的，需要用灯光来点亮，灯光只有3中原色，即blue (1), yellow (2) and red (4)，且灯的光只能上下左右4个方向照射；
• 点亮单色的水晶只要有一种颜色的灯射入即可，点亮复色的灯需要对应的两种颜色的灯光射入才能点亮；
• 如果光遇到水晶，或障碍，那么光停止传播；
• 光不能照到另一盏灯上（假设照上去会爆炸，- -！）；
• 希望你在网格中，空的格子里放入 灯，障碍，或者 镜子，使其能尽可能多的正确点亮网格中的水晶。

计分方法：

• 点亮一个单色水晶+20分
• 点亮一个复色水晶+30分
• 点错一个水晶-10分
• 每放入一个灯、镜子、障碍有对应的随机3种$cost$，不过每个测试数据，花费一定

以下是一个案例：

赛程回顾

这场时间点非常尴尬，一方面项目非常赶几乎没有时间优化方案，但为了哪怕1点积分还是豁出去了。

不像之前的几场马拉松，看完题脑海里立马会出现一个大概的思路。这个问题，我想大部分人看完题目应该会一脸懵逼，以至于最后比赛结束时才100多一些的选手提交。

其难点主要有：

• 复杂（非常易写出bug）的规则模拟。且不说实现一个高效的模拟器加速搜索过程，想实现能正确模拟规则的模拟器都是一个比较困难的事；
• 严重非连续性状态空间，对凸优化类似的思路简直就是灾难，比如其中复色灯需要点到第二个颜色才能获得有意义的梯度，比如镜子、障碍与灯的安放顺序决定梯度的变化，等等等...
• 爆炸级的搜索空间，如果选择（启发式）搜索的角度切入，这个状态空间基本崩溃，超越围棋复杂度量级，且缺少明显的启发式；

在最初的两天，我也主要以yy为主，一方面没时间写，另一方面也完全没有想法。不过第3天还是没有什么好的idea的我，决定不如先随机试试，（ps：其实随机往往是个不坏的方法，一方面出发总比原地待命有意义；另一方面随机往往提供了一个可以参考的baseline，可以帮你参照未来的某个思路是不是work）。我的随机策略也很简单，就是随便往一个地方放入一个合法的灯、镜子、障碍，如果能获得更好的收益就保留，不能收益就放弃这个操作。实际上这个策略在第3天的排行榜中看起来还不算太坑的，大概能排在60~70%的位置。

后来，又尝试了给复色灯点亮其中一个颜色下，增加一个额外的分数，即创建一个梯度使其往凸问题靠近。实际这个策略非常有效，立马能带来40%~60%+的增益。立刻进入接近50%的位置。

之后的1天，主要尝试在这个随机的基础上利用遗传的方式直接优化，不得不说如果搜索时间有很大富余时遗传总是能给你带来不错的收益，尤其对这种“恶心”的问题。大致比之前提升了50%，排名也第一次进入top 50%，因为排行榜进步的也非常快，= =。

再之后的时间，主要是周末的时间了，都在与局部搜索战斗，我尝试在一个不大的区域内尽可能的不计梯度问题的深搜，比如先枚举某N个格子放什么（最后优化到能搜到N=3，当然也在放弃了大量状态分支的基础上才勉强完成的），放完后再按梯度随机往里面塞其他物件。效果当然也不错，最后好不容易挣扎在了30%~40%的位置里。

总算艰难的拿到1点积分，总的来说虽然做的不算很好，但也是非常开心的，毕竟第一次在TCO拿到积分。

思路整理

这类问题不涉及太多技巧，简单说就是想办法加速模拟，尤其是加速局部修改的迭代更新效率。毕竟，比的基本就是谁搜的优秀的状态多，谁的最终得分高。

如果主搜索是建立在需要梯度的方法之上的（例如：模拟退火之类方法），以下技巧非常重要：

• 构造额外的梯度，因为双色水晶需要到第二的颜色被正确点亮是才会得分，显然只点一个灯是亏本的！这里就需要给双色水晶在点亮第一个颜色的时候给与一定的奖励来获得梯度。
• 总结一下大家的策略，首先我的我直接给第一个颜色一个得分$X$，$10<=X<=20$，至于具体给哪个值？我设计了一个贪心方法，带入每种X模拟一遍，得分最高的X作为最后的X。其次，是几个高分大佬的策略，他们给了一个非常天才的方法$X=ConstValue - Func(LeftTime)$，即给出了一个随着时间递减的函数来提供这个额外的梯度，这有个好处，一开始X比较高便于启发式搜索，后期X比较低，利于算法删除掉无效的灯。第三类方案是一开始给单色的水晶一个负分，这样从另一个角度给出了梯度。
• 实际上模拟退火之类的方法其实可以不给额外的梯度，也可以靠回火越过这个坎，不过效率会大打折扣。

全局搜索与局部搜索的结合。这个问题全图是$100 * 100$的，由于存在大量的坎，所以全局搜索很难靠运气实现某个局部的优化，这时需要在搜索的后期引入局部搜索。前期的全局搜索是为了快速的获得一个base尽可能高的可行解，后期的局部搜索是为了对局部进行优化。局部搜索的细节总结：

• 分割多个小的blocks，根据自己算法的复杂度定，我的局部搜索用的枚举前3步站位，在用贪心快速构造局部的剩余解，这个枚举比较耗，所以只能处理$5 * 5$小block。也有大佬用beam search的，但是效果看起来不是很理想。
• 实际上退火更适合这里的局部搜索（SA的大佬们普遍分数更好），如果用这个方案block可以选的更大一些，比如$10 * 10$之类。
• 注意权衡每个block的搜索占时，尽量留给每个block均匀的时间优化，局部搜索的聚焦性能带来非常多提升。

关于各种算法里的迭代操作，主要就以下几种，基本大家都能想到：

• 加入一个灯 or 一个镜子 or 障碍；
• 删除一个灯 or 一个镜子 or 障碍；
• 一些combo，不过事实表明这个不是很重要，没有一样能优化的很好，SA对其几乎不明感。
• 注意点，3个镜子可能构成环，这个问题需要考虑一下。

如何加速迭代过程？

• 其实不做任何处理，很裸的模拟稍加一些优化就能轻松实现$O(N)$的单步迭代与$O(N)$的单步检测效率，因为光路的直线性质，直接模拟ray的路径就可以。
• 一般而言，不难想到将单步检测效率优化至$O(1)$，同时能保持$O(N)$的单步迭代。这个可以通过保存和维护每个格子上4个方向可以通过的光路将打在哪个格子上的信息实现。这个优化是极有意义的，因为大部分的探索是bad的，并不需要迭代，这个可以增加更多的探索可能；
• 不过有大佬将两者同时优化到$O(1)$（只能说，一脸懵逼）。

其他可行的优化：

其实这种一看就搜不完的问题，总是可以用遗传算法的框架进行优化的。遗传的好处就是存在概率创造出能结合两个解局部优势的新的解。

不过这个问题的两个解怎么结合呢？我用的策略，将两个解每个格子放什么东西都存在一个list里，然后随机乱序，然后依次向网格里放这个东西，如果能放进去就放，不能放进去就跳过。在全局搜索阶段还是带来了一定的提升的。

总结

这问题有点难，不过多花点时间试试还是可以做的。做的好不好是另一回事，开心就好。

另外，我这次最有意义的一步优化是通过写出一个bug偶然发现的，恩，从那一刻开始我开始重新思考bug的意义。错误也许并不总是一件坏事。