0

我有N不同的工作。有些工作可以连续完成。

需要将连续的作业排列成作业序列，以使作业序列的数量M最少。

问题在于最大基数匹配的形式。

但是确定最大基数匹配时，作业序列的数量是最小的吗？

我正在寻找一种算法来解决它。

例子

N=6

可以从事以下工作：

然后，作业 1 可以转到作业 2、5。

然后作业 2 可以转到作业 3。

然后，作业 4 可以转到作业 2、5。

然后作业 5 可以转到作业 6。

执行工作分配，我们得到以下 2 个工作序列：

1-2-3

4-5-6

那么M=2。

这可以看作是找到完成所有航班（工作）的最少机组人员的问题。

4

1 回答 1

0

这个问题与拓扑排序有关。

将每个作业视为图的一个节点。该方法的其余部分与顶级排序相同。

解决问题的步骤：

  1. 最初，每个节点的入度为 0。

  2. 现在根据给定的工作关系更改所有节点的入度。

  3. 现在从入度为 0 的节点运行 DFS 或 BFS。其余过程与拓扑排序相同。

让我们考虑您给定的输入。

1 -> 2

1 -> 5

2 -> 3

4 -> 2

4 -> 5

5 -> 6

度数[1] = 0

度数[2] = 2 ( 1->2, 4->2)

度[3] = 1 ( 2->3)

度[4] = 0

度[5] = 2 ( 1->2, 4->5)

度[6] = 1 ( 5->6)

如果我们首先从节点 1 运行 DFS，将其对应的节点标记为已完成，然后 1, 2, 3将处理节点。作为这些节点之间的关系 ( 1->2->3)。

注意：这里它处理的节点可以1, 5, 6基于关系1->5->6。它也会给出正确的答案。首先处理哪些节点，这取决于您制作邻接列表的方式。

然后4将作为入度为 0 的未处理节点留下。因此，如果我们从 运行 DFS 4， 4, 5, 6则将被处理。作为这些节点之间的关系 ( 4->5->6)。

所以你有你的答案，那就是2。

注意：处理路径后，可以找到未处理且入度为 0 的新节点。例如，考虑关系1->2, 2->3, 2->4。

如果您首先处理路径1->2->3，4则将不进行处理。

如果您首先处理路径1->2->4，3则将不进行处理。

只需遵循基本的拓扑排序过程即可为您提供答案。您必须从多少度数为 0 的未处理节点中计算您正在运行 DFS。

了解拓扑排序的有用资源：

于 2021-09-06T09:10:35.430 回答