有 M 条广告,广告有互斥条件 N ( N 为 M 的 id,互斥广告不能相邻,头尾成环状)
{"AD{id=3, mutexList=[1, 4]}","AD{id=2, mutexList=[]}","AD{id=1, mutexList=[]}","AD{id=4, mutexList=[2]}","AD{id=0, mutexList=[]}"}
求 M 的排序。 目前解决办法是递归全排列 找到第一条符合条件的排列方式,请问还有更好的实现方式么。
1
xkeyideal 2020-08-12 17:27:15 +08:00 1
A 与 B 互斥,B 与 A 也应该互斥吧?如果是,你的 sample 就有问题了。
根据互斥关系,构造一个无向图,不互斥的可以连通,问题转化为找到一个起点遍历所有点,并回到起点,每个点只能经过一次。 简单的办法:bfs,本质上还是全排列的剪枝版本。 如果构造无向图是正解,那么应该有其他更高效的解法。 |
2
xkeyideal 2020-08-12 17:36:28 +08:00
看一下”柯尼斯堡七桥问题“,你这个还需要加上回到起点,应该是个 NP 问题
|
3
xmoiduts 2020-08-12 17:48:37 +08:00 via Android
丢给组合优化求解器(逃)
|