先说说我的想法,之所以会算不出最优解,是在于筛选的顺序.书上是从0开始的,而观察冲突关系集合R,发现0只出现了2次,是出现次数最少的数字之一.因此随后的数字,很巧2,3,7都是出现次数很少的,很容易就能放进跟0的同一个子集中,因而第一个子集就被"挤满"了.当要排第二个第三个子集的时候,剩下的数字已经"太大"使得一个集合装不了多少了. 打个比方,数字就是石头,数字出现的次数就是石头的大小,现在有个杯子,往里面放石头,希望尽可能利用杯子里的空间.很自然会想到先放大的,在填小的.(这实际上是某个很著名的寓言:P)

因此我们考虑用数字的出现次数重排比赛项目放进队列的顺序,出现次数多的在前面,优先进行划分.
比如上面的例子,重新排序后是{1,4,5,6,8,0,2,3,7}(这里直接用集合表示,实际上是有顺序的),按这个顺序进入队列并按书上方法划分子集,恰好就得到最优解{1,6,3},{4,0,2},{5,7,8}

但这个方法我不知道是不是总能找到最优解,希望有高手能回答:)

另外一个想法是考虑"冲突优先",先把发生冲突的项目排在不同的时间,再进行进一步的划分.但具体的方法还不知道怎么细化,一旦想要达到最优我就无能了:(


我的想法就到这里,希望大家都说说看法,让小弟开开眼界啊~~