算法分析作业--第5章课件

1、算法分析工作第5章，1，PPT学习交换，贪心方法，优化问题约束条件目标函数最优度量标准(贪心规则，贪心选择特性)考试，证明贪心方法不一定能求出最优值，大多数情况下得到更好的值；2，PPT学习交流，2，3，6，7，8，9，11，12，3，PPT学习交流，P121-2，为以下情况下的背包问题寻找最佳解决方案，n=7，将上述数据情况的背包问题记录为I。设定FG(I)是GREEDY-KNAPSACK在以pi的非增量顺序输入货物时生成的解决方案，FO(I)是最佳解决方案。FO(I)/FG(I)是多少？以非Wi顺序输入项目时重复的讨论。4，PPT学习通信，寻找背包问题的最佳解决方案，n=7，m=15贪心标

2、准(X5，x1，X6，x3，x7，x2，x4)=(1，1，x4)，5，PPT学习交流，按Pi的郑智薰增长顺序：n=7，m=15根据贪心(X6，x3，x1，x4，X5，x2，x7)=(1，1，1 P122-3，(0/1背包问题)5.3节讨论的背包问题，以最大限度的约束条件修改，xi=0或1in这种背包问题称为0/1背包问题。 不要把东西或全部放在背包里，也不要全部装。解决这个问题的贪心策略是根据IPI/wi wi的不对称顺序，如果考虑的东西可以进入的话，就放在背包里。证明这个策略不一定能得到最优解。8，PPT学习交流，P122-3，证明：按照IPI/wi的不对称顺序，把东西放在背包里。从大到小连

3、续放进去，如果能装满背包，肯定是最佳解决方案。否则，最佳解决方案，9，PPT学习交流，P122-3，例如n=3，M=6，(P1，p2，p3)=(3，4，8)，(w1，w2)问题证明。假设将、10、PPT学习交换、P122- 6、L1、L2、ln的n个程序存储在一个磁带上，检索程序I的频率为fi。如果程序按i1、I2、in的顺序存储，预计搜索时间(ERT)不一定是按：11、PPT学习交流、Li的顺序存储的程序获得最小的ERT。Fi特定的非增量存储程序不一定会获得最小的ERT。按Fi/li顺序保存程序时检查ERT的最小值。12，PPT学习通信，P122- 6已证明，Li的非顺序存档程序不一定能获得

4、最小的ERT。i: (L1，L2)=(10，12) (f1，F2)=(0.4，0.6) ERT (I)=10 * 0.4 (10 12)，i: (L1，L2)=(2，1) (f1，F2)=(0.6，0.4)ERT(I)=2 * 0.6(2 1)* *假设i1、I2、in按fi/li未增加的顺序存储，如fi1/li1fi2/li2fin/lin，则ert=fi1 Li 1 fi 2(li1 li2)fik(li1 li2 lik).fin)预计j1、j2、Jn按顺序存档，检索时间为ERT，并且只需证明ertert(按fi/li不排序的顺序存储)即可证明最佳解决方案。如果等于J1，J2，jn，i1

5、，I2，in，则证明命题。15，PPT学习交流，否则，程序JK可以设置与第一个和相邻程序JK 1的关系fjk/ljk0，都是ert，显然是ERT。16，PPT学习交流，优化解决方案的所有此类逆序对相似的程序交换位置，每个结果解决方案都不大于原始优化解决方案，因此最终转换后解决方案也是最佳解决方案，最终解决方案是程序按fi/li的郑智薰增长顺序存储的顺序。证明命题。，17，PPT学习通信，P122-7，L1，L2，ln中的n个程序，假定它们分别写入两个磁带T1和T2，我希望最大搜索时间保持在最低限度。也就是说，如果存储在T1和T2中的程序集合分别为a和b，则选定的a和b会使max成为最小值。获得

6、a和b贪心的一种方法是将a和b都初始化为空，然后一次考虑一个程序，如果=min，则将当前考虑的程序分配给a，否则分配给b。即使基于L1 L2 ln或基于L1 L2 ln考虑程序，此方法也证明无法生成最佳解决方案。18，PPT学习通信，证明：按以下顺序排列：L1 L2 ln L3=1，3，4 L1 L2，A=1，4，B=3，最大值为5，A=1，3，B=4，最大值为4。因此，命题得到了证明。19，PPT学习通信，证明：根据L1 L2 ln，最佳解决方案不一定会生成。L1、L2、L3、l4、l5=10、9、8、6、5、5根据L1 L2 L3 l4 l5，A=10，6，5、B=9，8，最大值为21。A

7、=10，9，B=8，6，5，最大值为19。因此，命题得到了证明。20，PPT学习通信，P123-8，n=7，(P1，p7)=(3，5，20，18，1，6，30)和(d1，d7)=(1，3证明作业即使有其他处理时间整理5.3也是真的。其中，任务I的优点基于pi0、要使用的处理时间ti0、期间diti、21、PPT学习交换、P123-8、解决方案：pi的郑智薰增长排序(p7、P3、P4、P6、p2、P1、)(P106)清理5.3:是k的工作集，=i1i2ik是j的工作顺序，这是di1di2dik .仅当j是可行的解决方案，j的作业可以在不违反调度顺序的情况下处理时，23，PPT学习交流，P123-

8、8，证明想法：位置a，b的作业交换顺序作业ra和Rb仍然可以完成作业ra和Rb之间的作业。任务完成，24，PPT学习交换，P123-8，证明：即使ti0(diti)，如果j的任务在一段时间内无法进行，并且可以按顺序处理，那么顺序中的任务k必须满足dk，这是j可能的解决方案。如果j是可行的解决方案，则=i1i2ik表明j的任务可以按di1di2din顺序排序，而不会违反截止日期。25，PPT学习通信，j是可行的解决方案，存在=r1r2rn，所以所有rk都有drk，我们根据di1di2din设置操作顺序。例如，如果使a成为raia的最小下标，并将rb=ia设置为rb=ia，则ba显然将与drbdr

9、a交换Rb。drbdra当然是因为ra和Rb可以按计划完成任务。=r1RArb rn(可行解决方案)=i1ia in (d增量)t=DRB DRA t drj，26，PPT学习通信，然后我们必须证明ra和rb之间的作业也可以按计划完成。对于Drbdra，drbdrt是两者之间的所有作业rt和可执行解决方案，因此即使在交换了作业ra和Rb后，drt也将满足。也就是说，可以按新创建的顺序处理所有任务。也就是说，您可以继续使用此方法，而不会违反一个期间。定理证明了。第5.3节中任务排序问题的27、PPT学习交换、P123-9证明：仅当子集j中的任务可以根据以下规则处理时，才表示可行的解决方案：如果j

10、的作业I没有分配处理时间，则由片A-1，A进行处理。其中A是创建1rdi的最大整数r，切片A-1，A为空。根据示例5.4的格式，在练习8中提供的数据集上运行算法5.5。28、PPT学习交流，P123-9，如果可以按照上述规则处理j的作业，那么显然j是可行的解决方案。如果j是可执行的解决方案，则根据清理5.3，j的任务可以根据时间周期的清空顺序获得i1i2ik in，并按照此顺序处理j的所有任务，如果此序列中的任何任务ik的相应持续时间为dk，并且时间片dk-1，dk为空，则分配该任务。时间片dk-1，如果dk不为空，则查找最大非空r-1，r时间片，1rdk。因为j是可执行的解决方案，所以可以找到此时间表。因此，命题得到了证明。29，PPT学习通信，n=7 (P1，p7)=(3，5，20，18，1，6，30) (D1，D7)=(4，6，(p7，P3，P4，P6，P2，p1，p5)=(30，20，18，6，5，3，1)，相应期间(2，4，3，1，3，1，2)，32 证明符合n mod (k-1)=1的正整数n具有n个外部节点的k元树t(一棵k-树中每个节点的度数最多为k-1)。此外，t的所有内部节点的度数为k .33，PPT学习交换，P123-11表示一棵树中所有内部节点的度数为证明：此树的内部节点数为I，外部节点数为