1 A 3 B C 对于网络中任一结点i，设d(i)表示结点i与其父结点间的衰减量，D(i)为从结点i
2 2 1 2 到结点i的子树中任一叶子结点的衰减量的最大值，并有如下递推公式： D E G F D(i)=0 若i为叶结点 2 1 D(i)= max{D(j) + d(j)} 若2 j是i的孩子 2 i不是叶结点且
H I J K 在此公式中，要计算某结点的D 值，必须先计算其孩子结点的D值，因而必须后序遍历图98-a 网络分布示意图 二叉树，当访问一个结点时，计算其D值。
例如，D(B)=max{D(D)+d(D)，D(E)}=4，若容忍值为3，则在B点或其祖先的任意一点放置放大器，并不能减少B与其后代的衰减量，必须在D点放置一个放大器或在其孩子结点放置一个或多个放大器。若在结点D 处放置一个放大器，则D(B)=2。
根据上述分析，设计如下存储结构： struct element {
int D; // 该结点的衰减量 int d; // 父结点的衰减量
bool boost; //当且仅当本处设置放大器，则boost为true };
struct BiNode {
element data;
BiNode *lchild,*rchild; };
计算并放置放大器的伪代码为： 1. D(i) = 0 ;
2. for (i 的每个孩子j )
2.1 如果D(j) +d(j)>容忍值，则在j处放置放大器; 2.2 否则D(i) = max{D(i)，D(j) +d(j)} ;
81.TSP问题 1) 问题描述
所谓TSP问题是指旅行家要旅行n个城市，要求各个城市经历且仅经历一次，并要求所走的路程最短。该问题又称为货郎担问题、邮递员问题、售货员问题，是图问题中最广为人
知的问题。 2) 基本要求
(1) 上网查找TSP问题的应用实例；
(2) 分析求TSP问题的全局最优解的时间复杂度； (3) 设计一个求近似解的算法； (4) 分析算法的时间复杂度。 3) 设计思想
对于TSP问题，一种最容易想到的也肯定能得到最佳解的算法是穷举法，即考虑所有可能的旅行路线，从中选择最佳的一条。但是用穷举法求解TSP问题的时间复杂度为Ο(n!)，当n大到一定程度后是不可解的。
本实验只要求近似解，可以采用贪心法求解：任意选择某个城市作为出发点，然后前往最近的未访问的城市，直到所有的城市都被访问并且仅被访问一次，最后返回到出发点。
为便于查找离某顶点最近的邻接点，可以采用邻接矩阵存储该图。算法用伪代码描述如下：
1. 任意选择某个顶点v作为出发点； 2. 执行下述过程，直到所有顶点都被访问： 2.1 v=最后一个被访问的顶点；
2.2 在顶点v的邻接点中查找距离顶点v最近的未被访问的邻接点j； 2.2 访问顶点j；
3. 从最后一个访问的顶点直接回到出发点v；
82.机器调度问题 1)问题描述
机器调度是指有m台机器需要处理n个作业，设作业i的处理时间为ti，则对n个作业进行机器分配，使得：
(1) 一台机器在同一时间内只能处理一个作业； (2) 一个作业不能同时在两台机器上处理； (3) 作业i一旦运行，则需要ti个连续时间单位。
设计算法进行合理调度，使得在m台机器上处理n个作业所需要的处理时间最短。 2) 基本要求
(1) 建立问题模型，设计数据结构；
(2) 设计调度算法，为每个作业分配一台可用机器； (3) 给出分配方案。 3) 设计思想
假设有七个作业，所需时间分别为{2, 14, 4, 16, 6, 5, 3}，有三台机器，编号分别
为m1、m2和m3。这七个作业在三台机器上进行调度的情形如图100-a所示，阴影区代表作业的运行区间。作业4在0到16时间被调度到机器1上运行，在这16个时间单位中，机器1完成了对作业4的处理；作业2在0到14时间被调度到机器2上处理，之后机器2在14到17时间处理作业7；在机器3上，作业5在0～6时间完成，作业6在6～11时间完成，作业3在11～15时间完成，作业1在15～17时间完成。注意到作业i只能在一台机器上从si时刻到si +ti时间完成且任何机器在同一时刻仅能处理一个作业，因此最短调度长度为17。
时间 分配 m1 m2 m3 作业5 作业4 作业2 作业6 作业7 作业3 作业1 6 5 16 17 4 图100-a 三台机器的调度示
在上述处理中，采用了最长时间优先（LPT）的简单调度策略。在LPT算法中，作业按其所需时间的递减顺序排列，在分配一个作业时，将其分配给最先变为空闲的机器。 下面设计完成LPT算法的存储结构。
· 为每个机器设计数据类型： struct MachineNode {
int ID; //机器号 int avail; //机器可用时刻 };
· 为每个作业设计数据类型： struct JobNode {
int ID; //作业号 int time; //处理时间 };
LPT算法用伪代码描述如下：
1. 如果作业数n≤机器数m，则 1.1 将作业i分配到机器i上；
1.2 最短调度长度等于n个作业中处理时间最大值； 2. 否则，重复执行以下操作，直到n个作业都被分配：
2.1 将n个作业按处理时间建成一个大根堆H1； 2.2 将m个机器按可用时刻建立一个小根堆H2； 2.3 将堆H1的堆顶作业分配给堆H2的堆顶机器；
2.4 将H2的堆顶机器加上H1的堆顶作业的处理时间重新插入h2中； 2.5 将堆H1的堆顶元素删除； 3. 堆H2的堆顶元素就是最短调度时间；