Jie Chu

I am studying the sensor coverage problem, where Čech complex should be the best fit.

这个问题本身可以转化成图论的问题。把每个御魂组合表示成图的顶点，顶点的边如果定义为公用同一个御魂，那么问题就变成了在这个图上寻找最大的独立集。 另外一种定义，图的顶点依然为御魂组合，两个组合如果不共用御魂则用一条边把他们连起来，这样问题就变成了在这个图上找Maximum clique。 这两个图互为补图，这两个问题都是NPC的，也就是基本上只能依靠穷举找到最优解，但是有一些近似解法可以考虑。 也可以生成Maximal clique/independent set，就是局部的最优解，但这里有一个问题比较关键，就是如果有不同的独立组合方案，那么如何定义哪一套更好？

> > 这个问题本身可以转化成图论的问题。把每个御魂组合表示成图的顶点，顶点的边如果定义为公用同一个御魂，那么问题就变成了在这个图上寻找最大的独立集。 > > 另外一种定义，图的顶点依然为御魂组合，两个组合如果不共用御魂则用一条边把他们连起来，这样问题就变成了在这个图上找Maximum clique。 > > 这两个图互为补图，这两个问题都是NPC的，也就是基本上只能依靠穷举找到最优解，但是有一些近似解法可以考虑。 > > 也可以生成Maximal clique/independent set，就是局部的最优解，但这里有一个问题比较关键，就是如果有不同的独立组合方案，那么如何定义哪一套更好？ > > 这个只有一个解吧，还是NPC。我甚至想过最大流来着，也是一个解。这里应该是输出所有可能情况，不同方案可以按攻击x爆伤或类似的去比，但没必要，因为全都要啊。 > > 而且我觉得IO瓶颈倒是挺严重的，完全不写文件的话上面写的那个naive的算法能十分钟算完50M文件，可以接受了。这方面的话我不知道写csv会不会比这个xls快，这几天都在超鬼王了233 全都要就意味着要遍历所有可能，不是时间太久就是内存不够或者两个问题都存在。 你说的算法，应该就是求Maximal clique的一种算法的扩展：已知一个大小为N的clique，尝试所有顶点可以扩展成N+1的clique（如果存在的话）。根据第二种定义的图，以所有的边作为起点（N=2的clique），可以找出N+1的clique的集合，然后重复这个过程。我实现了一个版本，但是处理1w种御魂方案就已经内存不够了。肝完鬼王我再去看看能不能优化一下... 我不太清楚你怎么写的，但是感觉IO不是大的问题才对，如果把中间结果缓存在内存里最后输出呢？可以贴个代码给大家参考一下。