指派问题:求作业序列的最小数目

Question

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

需要排列连续的作业以形成作业序列，使得作业序列M的数量最小。

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

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

我正在寻找一种算法来解决这个问题。

示例

N=6

可以执行以下工作：

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

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

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

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

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

1-2-3

4-5-6

然后是M=2。

这可以看作是寻找进行所有飞行(工作)的最小机组人员数量的问题。

Answer 1

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

将每个作业看作是图中的一个节点。该方法的其余部分与top sort相同。

解决问题的步骤：

1. 最初，每个节点的in-degree为0。

1. 现在可以根据给定的作业关系更改所有节点的入度。

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

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

1 -> 2

1 -> 5

2 -> 3

4 -> 2

4 -> 5

5 -> 6

inDegree1 =0

inDegree2 =2 (1->2, 4->2)

inDegree3 =1 (2->3)

inDegree4 =0

inDegree5 =2 (1->2, 4->5)

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

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

，则4将保留为未处理的节点，其in-degree为0。因此，如果我们从4运行DFS，那么4, 5, 6将被处理。作为这些节点之间的关系(4->5->6)。

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

备注：对路径进行处理后，可以找到新的未处理的节点，其在度为0。例如，考虑关系1->2, 2->3，2->4。

如果您首先处理路径1->2->3，则4将处于未处理状态。

如果您首先处理路径1->2->4，则3将处于未处理状态。

只需遵循基本的拓扑排序过程就可以给出答案。你必须计算一下，有多少未处理的节点带有0度，你运行的是DFS。

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

• Topological Sorting CP-Algorithms

• Topological Sorting GFG

• Topological Sort Tutorials & Notes | HackerEarth