2018 TCO Marathon Poland特别场回顾 12月 10, 2018
contest
0 条评论

概述

关键词
  • Graph Coloring Problem（图染色）
  • Tabu Search（禁忌搜索）
  • Kempe Chain
  • 优化方法
  • Algorithm
问题来源
  • 2018 TCO Marathon - Poland Lightning Round是TCO18 Warsaw的特别场。原题链接.

问题

问题大意：
$H * W$的网格，每个格子属于一个区域(Region,但属于同一个区域的所有格子不一定是联通的)，每个格子被初始为一种颜色(Color)。对(i,j)坐标的格子，记其所属区域为Region(i,j),其初始颜色为Color(i,j)。

操作：对所有区域r各进行一次操作。该操作为：选择一种颜色c，将属于区域r的所有格子全部染成颜色c。

目标：所有操作做完，希望达到目标有：

  • 必要条件：不存在两个相邻的格子（相邻指两个格子有公共边）会同时满足条件：1）属于不同的区域，2）拥有相同的颜色。
  • 优化目标：两个优化目标：1）网格里出现的颜色尽可能少；2）与初始颜色不一致的格子尽可能少。

评价：如果，最终网格中一共使用了$CN$个颜色，有$PN$个格子颜色与初始值不同，那么，得分为$Score=CN*PN$.

注意点：这个问题四染色是不对的，因为Region并不一定是一个连通区域。

赛程回顾

这比赛恰好刷在了东8区的周六~周一，时间上基本在周末，感觉非常科学。周六加班之余简单构思了一下，大致思路如下：

  • 花大部分的时间去最小化Color的数量，即目标里的CN；
  • 用剩余的时间去搜索更小的PN值；

之所以采用这么一个策略，主要是受到原问题如下描述的误导。

  • Scoring
    Your raw score for an individual test case will be calculated as (100000 * total number of colors used + number of pixels recolored). If your return was invalid (was formatted incorrectly, returned an invalid map coloring, etc.), the score for this test case will be -1.

这个只是一个显示分数的方案，其实并不是比赛最终排名的方法，排名的计分方法是$Score=CNPN $，而我却一直误以为是$Score=CN10^5+PN$。尴尬 = =|| 但实际影响并不大（至少不致命），后面会说为什么。

关于如何去最小化Color数量？

首先原问题可以很容易转换成一个图染色问题，Region作为节点，两个Region相邻则建边，很显然。

图染色问题的优化方法里Tabu Search是比较好的（当然，还有很多其他的启发式搜索的方法，不过很多论文讨论过各种方法的优劣性，我们直接取结论就好了，毕竟马拉松时间有限）。不过Tabu其实只是一个算法框架，具体实现细节上的不同还是有一些区别的，毕竟效率高就能搜更多状态。

初期实现的Tabu的大致实现流程：

  1. 随机化构造一组解，确定K染色问题的K的上届；
  2. 在求解了K的可行解后，尝试求解$K=K-1$的染色问题；
  3. 对所有节点全部随机K染色，无视冲突情况，构造完成时，计算冲突值T（每存在一对相邻的节点同色，冲突值+1）；
  4. 用Tabu Search进行状态迭代，对当前状态，下一个状态构造方法是 改变当前一个节点的颜色，并记录其新的冲突值T',对每一个有冲突的节点进行尝试，并选取T'最优的值迭代（注意：Tabu Search是允许$T'>T$的）；
  5. 迭代若干时间内，有解GoTo 2，无解，GoTo 3再试一遍；
  6. 得到能求解到的最小K，以及一组可行解。
再提一些细节点：

数据结构:
由于计算邻域只改一个节点的颜色，所以可以维护一个二维数组NeibCol[node][color]记录节点node节点所有相邻节点中有多少个染色是color色的，再维护每个节点的颜色数组Color[node]。那么很显然一个节点是不是存在冲突节点，只用判断NeibCol[node][Color[node]]>0即可。而把一个节点染成另一个颜色c2，也可以简单的通过NeibCol[node][Color[node]]-NeibCol[node][c2]计算收益。维护起来也不用多说，很简单高效。

选择最优状态:

  • 一个方案：可以用最大堆来维护当前修改操作下哪个操作最优，可以把每次迭代的节点选择的效率略微提高一些。不过注意保存version的概念，因为一个操作可能在几步迭代后，已经不再合法，因为之前的迭代可能已经修改过这个节点，或这个节点邻居节点。

  • 另一个方案：维护冲突节点的集合，每次迭代只对其中一部分节点（比如1/4）进行计算，然后去这些里的最优解，这里最好做一些缓存的工作，保存一个version就行，重复算划不来。

  • version：解释一下，一个点被迭代了，那么，该节点与其邻点version=++global_version。这样就能快速判断一个历史缓存的有效性了。

不论选哪个效果都不错。不过也可以每次简单遍历全部节点算最优，就是有点浪费时间，效率不太好。

禁忌表规则:

出于效率+省内存的考虑，禁忌表只用了近似规则，大致如下两种思路：

  • 方案一：直接禁止操作过的节点若干回合。（禁止列表大小试了一下20~size(node)/20较好）
  • 方案二：将一步操作的逆操作禁止若干回合。（禁止列表小一些较好，比如20左右，这题。这个方案更接近完整的Tabu方法的规则）
关于如何优化重染色grid数量的问题

因为一开始以为得分是$Score=CN*10^5+PN$，所以也没花太多时间设计。大致思路就是：

  1. 开一个新的禁忌表，叫“永久禁忌表”记PT,放在这个表里的节点禁止被修改。初始值为空TP={}。
  2. 随机把一个Region的染色强行改成初始时这个Region最多/次多的颜色，同时把这个节点永久加入禁忌表TP
  3. 再跑Tabu看看能不能解，无解的话就还原那个节点的颜色；有解的话,计算一下这个解是不是比之前的优，更优就迭代，否则也还原；
  4. 重试2，直到永久禁忌表满了.

显然这个方法有一点提升，但是提升不大。不过好在大部分的这部分做的都不好，就是所谓了，最优化了错误的方向，依然不算太烂，毕竟本题的主要矛盾是第一部分求解。

更稳定的K-Color求解

比赛第二天，也就是周末，不用加班，又翻了翻论文，发现还有个更稳妥的方案。论文见《Hybrid Evolutionary Algorithms for Graph Coloring》

大致在思路是在Tabu外层包一个混合进化的壳子，这个混合进化的思路大致如下：

壳子

  • 同时保存多个需要迭代的状态,V1、V2；

  • 选出两个状态，进行Crossover(V1, V2)操作；这个Crossover(V1, V2)简单说就是交替的从V1与V2中选一个包含节点最多的颜色集合，并把选出这个颜色集合作为生成状态的一个颜色集合。操作完后剩余的点，全部随机染色；

  • 将如上生成的新状态放入TabuSearch算一会儿，然后替换掉V1和V2中比较差的一个。

这个方法确实会比单一Tabu Search稳的多，一方面种群的存在，能规避随机初始点好坏不定的风险，另外及时淘汰掉比较坏的状态。

不过同样出于效率的考量，种群我只定了8，确实也不是很稳。但我在实现时，加了一个新的规则，就是每次大循环中10%的概率会构造一个新的状态，并替换掉当前最坏的情况。一定情况下弥补了种群数量小的问题。

周一上班，于是掉了一天的排名。晚上下班回家，突然发现需要优化的最终目标是$CN*PN$,做了一些优化，但已经无力回天了。悲剧，终！

大佬们的策略总结

结束后看了一下大佬们的讨论帖，出现了一些关于同时优化PN与CN的策略，以及提升PN的策略。总结一下我忽略掉的情况：

优化PN: 引入Kempe Chain的局部迭代方法，由于Kempe Chain的操作是对局部的连通区域内的两个颜色进行交换，不会破坏之前的求解状态，所以可以较快速的迭代优化。

求最佳CN时顺便优化PN: 比如在求解Tabu时，有意识的把颜色往Cost小的方向改。没看到具体代码，猜测可能是搜索的过程中，随机的把某个节点改成一个Cost更低的颜色，然后在继续？类似加入禁忌表之类的？不是很确定，但感觉很不错的策略。

其他的细节目前讨论出来的不多，以后再看看吧。太晚了，睡了 ~~

Post Views: 3,986