一个带有限期的作业排序问题： n=5, (p1,p2,p3,p4,p5)=(6,3,4,8,5), (t1,t2,t3,t4,t5)=(2,1,2,1,1), (d1,d2,d3,d4,d5)=(3,1,4,2,4), 采用“9.4 带有限期的作业排序”中的估计函数和上界函数u的定义，画出FIFO, LIFO, LC三种检索方法对上述问题所生成的、大小可变的元组表示的部分状态空间树（要求树中结点按生成次序编号），求出对应于最优解的罚款值。

首先，我们需要定义一些符号：

- $n$：任务数量
- $p_i$：第 $i$ 个任务的处理时间
- $t_i$：第 $i$ 个任务的惩罚时间
- $d_i$：第 $i$ 个任务的期限
- $C_i$：第 $i$ 个任务的完成时间
- $w_i$：第 $i$ 个任务的惩罚值

接下来，我们按照题目要求，使用FIFO、LIFO和LC三种检索方法，生成部分状态空间树。

### FIFO

按照FIFO检索方法，我们先处理第一个任务，然后处理第二个任务，以此类推。因此，我们可以得到以下的部分状态空间树：

        0(0,0,0,0,0)
        / |  |  |  | \
       /  |  |  |  |  \
      /   |  |  |  |   \
  (1,0,0,0,0) ... (5,0,0,0,0)
    /|   |  |  |  |  | ... \
   / |   |  |  |  |  |       \
  /  |   |  |  |  |  |        \
(2,0,0,0,0) ... (5,0,0,0,1) (3,0,0,0,0) ... (5,0,0,1,0)
 |   |   |  |  |  | ...     |             |
 |   |   |  |  |  |           \            \
 |   |   |  |  |  |            \            \
(3,0,0,0,0) ... (5,0,1,0,0)   (4,0,0,0,0)   (5,1,0,0,0)
  |   |   |  |  | ...         |             |
  |   |   |  |  |             \            \
  |   |   |  |  |              \            \
 (4,0,0,0,0) ... (5,2,0,0,0)   (5,0,0,0,0)   (5,0,0,0,0)
     |   |  |  | ...          |
     |   |  |  |              \
     |   |  |  |               \
    (5,0,0,0,0)               (5,0,0,0,0)
         |                      |
         |                      |
         |                      |
        ...                    ...

上面的数字表示当前处理到的任务编号，括号中的数字分别表示 $C_1$ 到 $C_n$ 的值，最后一个数字表示当前的惩罚值。

我们可以看到，FIFO检索方法生成的状态空间树比较简单，因为它只考虑了任务的先后顺序，没有考虑其他因素。

### LIFO

按照LIFO检索方法，我们先处理最后一个任务，然后处理倒数第二个任务，以此类推。因此，我们可以得到以下的部分状态空间树：

        0(0,0,0,0,0)
        / |  |  |  | \
       /  |  |  |  |  \
      /   |  |  |  |   \
  (5,0,0,0,0) ... (1,0,0,0,0)
    /|   |  |  |  |  | ... \
   / |   |  |  |  |  |       \
  /  |   |  |  |  |  |        \
(5,0,0,0,1) ... (1,0,0,0,0) (5,0,0,0,2) ... (2,0,0,0,0)
 |   |   |  |  |  | ...     |             |
 |   |   |  |  |  |           \            \
 |   |   |  |  |  |            \            \
(5,0,1,0,0) ... (1,0,0,0,0)   (5,1,0,0,0)   (4,0,0,0,0)
  |   |   |  |  | ...         |             |
  |   |   |  |  |             \            \
  |   |   |  |  |              \            \
 (5,2,0,0,0) ... (1,0,0,0,0)   (5,0,0,0,0)   (5,0,0,0,0)
     |   |  |  | ...          |
     |   |  |  |              \
     |   |  |  |               \
    (5,0,0,0,0)               (5,0,0,0,0)
         |                      |
         |                      |
         |                      |
        ...                    ...

我们可以看到，LIFO检索方法生成的状态空间树和FIFO检索方法生成的状态空间树类似，只是任务的处理顺序相反。

### LC

按照LC检索方法，我们先处理剩余任务中惩罚值最大的任务。因此，我们可以得到以下的部分状态空间树：

        0(0,0,0,0,0)
        / |  |  |  | \
       /  |  |  |  |  \
      /   |  |  |  |   \
  (4,0,0,0,8) ... (1,0,0,0,5)
    /|   |  |  |  |  | ... \
   / |   |  |  |  |  |       \
  /  |   |  |  |  |  |        \
(5,0,0,0,13) ... (2,0,0,0,9) (3,0,0,0,7) ... (1,0,0,0,5)
 |   |   |  |  |  | ...     |             |
 |   |   |  |  |  |           \            \
 |   |   |  |  |  |            \            \
(5,1,0,0,12) ... (2,0,0,0,9) (5,0,0,0,13) ... (3,0,1,0,7)
  |   |   |  |  | ...         |             |
  |   |   |  |  |             \            \
  |   |   |  |  |              \            \
 (5,2,0,0,10) ... (1,0,0,0,5)  (5,3,0,0,8)   (4,0,0,0,8)
     |   |  |  | ...          |             |
     |   |  |  |              \            \
     |   |  |  |               \            \
    (5,0,0,0,13)               (5,0,0,0,13)  (5,0,0,0,13)
         |                      |
         |                      |
         |                      |
        ...                    ...

我们可以看到，LC检索方法生成的状态空间树和前两种方法生成的状态空间树不同，因为它考虑了任务的惩罚值。在这个树中，我们先处理惩罚值最大的任务，然后依次处理剩余任务中惩罚值最大的任务。这种方法可以保证在有限期的作业排序问题中得到最优解。

接下来，我们需要计算对应于最优解的罚款值。在我们生成的部分状态空间树中，所有叶子结点都是处理完所有任务后的状态。我们可以找到惩罚值最小的叶子结点，这就是对应于最优解的状态。然后，我们可以沿着这个叶子结点的父节点一直向上回溯，计算出对应的罚款值。在这个例子中，对应于最优解的罚款值为5。