在作业排序问题中，如何表示解决方案？

适用条件

• 问题涉及从给定集合中选择作业的子集。
• 表示必须清楚地指示哪些作业包含在解决方案中。

理解与推导

1. 识别所有可用作业的集合。
2. 方法 1（子集）：列出解决方案中选择的特定作业。大小根据所选作业的数量而变化。
3. 方法 2（二进制向量）：创建一个长度等于作业总数的向量。如果相应的作业被选中，则将位设置为 1，否则设置为 0。
4. 验证两种表示是否传达了相同的选中信息。

例子

对于作业 $J_1$, $J_2$, $J_3$, $J_4$，选择 $J_1$ 和 $J_4$ 可以写为 $S1 = {J_1, J_4}$（子集）或 $S2 = {1, 0, 0, 1}$（二进制向量）。

容易误解的地方

• 假设二进制向量的大小根据所选作业的数量而变化。
• 将子集表示中作业的顺序与二进制向量表示中的固定位置混淆。

观看对应讲解

继续追问

• 在这段视频中，回溯法和分支限界法有什么区别？
• 在这个例子中，状态空间树是如何逐层扩展的？
• Dijkstra 算法在图论中的目的是什么？