我想做类似于 Appointment scheduling algorithm (N people with N free-busy slots, constraint-satisfaction). 的事情但我的附加要求是我应该能够给出第二最优解、第三最优解等等。 是否可以在不严重影响性能的情况下实现这一目标？
最佳答案
(据我所知)并没有太多的研究来寻找解决方案，从最优的顺序，因为大多数时候我们只关心找到一个尽可能有效的解决方案。因此，假设可能不会出现更好的解决方案，我将提供此解决方案。
要找到最有效的解决方案，请使用 the accepted answer in the linked question .为方便起见复制在这里:
Find a maximum matching in a bipartite graph (one set of vertices is the set of people and the other on the set of slots, there is an edge between a person and a slot if the person is available for this slot).
This problem can be solved with the Hopcroft-Karp algorithm.
Complexity
O(n<sup>5/2</sup>)in the worst case, better if the graph is sparse.
现在，依次尝试从输入图中移除输出的每条边，然后再次运行算法。
这些运行中的一个应该会给你第二好的结果。
现在，依次尝试从为您提供第二最优的图中删除输出的每条边，然后再次运行该算法。
现在第三最优应该在生成的集合中。
现在同样尝试删除第三最优图形的边缘。
等等。
复杂性:
O(n<sup>5/2</sup>)在最坏的情况下寻找最优解。
O(n<sup>7/2</sup>) ( O(n.n<sup>5/2</sup>) ) 在最坏的情况下生成每个下一个解决方案。
示例:
假设你有边 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 时，您需要检查从两个边移除的所有边是次优的，这可能会对运行时间产生一些负面影响。
关于algorithm - 使用次优解决方案采访调度算法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/19762443/