原创算法题求助。

[a3613051]

有 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 的排序。 目前解决办法是递归全排列 找到第一条符合条件的排列方式，请问还有更好的实现方式么。

[xkeyideal]

A 与 B 互斥，B 与 A 也应该互斥吧？如果是，你的 sample 就有问题了。
根据互斥关系，构造一个无向图，不互斥的可以连通，问题转化为找到一个起点遍历所有点，并回到起点，每个点只能经过一次。
简单的办法：bfs，本质上还是全排列的剪枝版本。
如果构造无向图是正解，那么应该有其他更高效的解法。

[xkeyideal]

看一下”柯尼斯堡七桥问题“，你这个还需要加上回到起点，应该是个 NP 问题

[xmoiduts]

丢给组合优化求解器（逃）

[a3613051]

@xkeyideal 确实 a 与 b 互斥 b 也与 a 互斥 sample 有问题，因为第一时间就想到了全排列递归剪枝。所以写的随机生成也没考虑这个。 我去研究研究柯尼斯堡七桥，原本业务是一批广告，广告主要求我不能与某条广告连续播放