2018 TCO Marathon Poland特别场回顾

概述

关键词
  • 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外层包一个混合进化的壳子,这个混合进化的思路大致如下:

《2018 TCO Marathon Poland特别场回顾》

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

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

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

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

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

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


大佬们的策略总结

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

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

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

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

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注

This site uses Akismet to reduce spam. Learn how your comment data is processed.