0

我正在尝试创建一个算法,根据规则列表确定是否存在有效的数字排列。

我有n节点和n整数,每个节点都包含一个无法配对的整数列表,我的目标是确定是否可以将每个节点与整数配对。

目前,我最好的解决方案是尝试选择一个可以配对的数字和节点,将它们从列表中删除,然后递归调用我的函数。

在最坏的情况下,这可能会在阶乘时间内产生所有可能的排列。是否可以在不生成所有排列的情况下确定是否存在有效配对?

谢谢你的帮助!

4

3 回答 3

2

这个问题将简化为最大二分匹配,您可以使用 Ford-Fulkerson 算法在 O(nm) http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm中解决它。

这个想法是你可以创建一个顶点是 n 个整数和 n 个节点的图,如果你可以使用该整数来表示该节点,那么从一个节点到一个整数会有一条有向边。从何时可以应用上述算法开始,该图可以分为两组。

于 2013-09-18T11:10:43.867 回答
0

除非您有更多关于如何生成“无法配对的整数列表”的详细信息,否则没有。这类问题的解决方案是分治算法:http ://en.wikipedia.org/wiki/Divide_and_conquer_algorithm

于 2013-09-18T11:01:14.923 回答
0

您也可以将其视为作业问题

您可以为不希望分配的组合分配巨额成本,并为所有可行组合分配零成本。

最小化你的目标函数,如果结果大于零,那么这意味着可行的分配是不可能的。

可以应用标准匈牙利算法

于 2013-09-18T11:33:36.533 回答