我想做一些类似于约会调度算法的事情（N 个人有 N 个空闲-忙碌插槽，约束满足）。但我的附加要求是我应该能够给出第二个最优解、第三个最优解等等。是否有可能在不严重影响性能的情况下实现这一目标？
问问题
569 次
1 回答
1
没有很多研究（据我所知）从最优化的顺序开始寻找解决方案，因为大多数时候我们只关心找到尽可能有效的解决方案。因此，假设可能不会出现更好的解决方案，我将给出这个解决方案。
要找到最有效的解决方案，请使用链接问题中接受的答案。为方便起见，复制到这里：
在二分图中找到最大匹配（一组顶点是人的集合，另一个在槽的集合上，如果人可用于该槽，则人和槽之间存在边）。
这个问题可以用Hopcroft-Karp 算法来解决。
最坏情况下的复杂性，如果图稀疏则更好。
O(n5/2)
现在，反过来，尝试从输入图中删除输出的每条边并再次运行算法。
这些运行之一应该为您提供次优。
现在，反过来，尝试从图中删除输出的每条边，使您获得次优，然后再次运行算法。
现在第三最优应该在生成的集合中。
现在类似地尝试删除第三最优图的边缘。
等等。
复杂：
O(n5/2)在最坏的情况下获得最优解。
O(n7/2)( ) 在最坏的情况下生成每个下一个解决方案。O(n.n5/2)
例子：
说你有边缘a,b,c,d,e,f,g。
假设最大匹配是a,b,c。
现在您a从输入图中删除并获取b,c,d,e,f,g.
假设这个图的最大匹配是c,d,e。
现在您b从输入图中删除并获取a,c,d,e,f,g.
假设这个图的最大匹配是a,d,e。
现在您c从输入图中删除并获取a,b,d,e,f,g.
假设这个图的最大匹配是a,b,g。
现在c,d,e,a,d,e或a,b,g将是次优的（假设它是a,b,g）。
现在尝试删除a, b, 然后g从中a,b,d,e,f,g获取并获取这 3 个图形中每个图形的最大匹配。
这 5 个集合中的一个（生成的 6 个集合，不包括第二个最优集合）应该是第三个最优集合。
等等。
证明：
我得再考虑一下...
笔记：
例如，假设我们有a,b,c,d,e最大匹配为 的边a,b,c。
我们删除a并得到c,d,e最大匹配。
我们删除b并得到c,d,e最大匹配。
请注意，这两个是相同的，因此您不应将一个作为第二最佳而将另一个作为第三最佳。
尽管您应该保留两者 - 您需要检查从删除生成的图形c，d以及e从两者生成的图形b,c,d,e和a,c,d,e。
由于您将需要检查从两者中删除的所有边何时c,d,e是下一个最佳时间，这可能会对运行时间产生一些负面影响。
于 2013-11-04T06:51:24.310 回答