这次课介绍两个例子。 调度问题与投资问题，通过这两个例子 来考虑一下什么叫做算法设计。先看看调度问题。 这里边有n项任务，每个任务有一个加工时间， 从0时刻开始把这些任务安排到一台机器上。 每个任务的完成时间是从0开始计时， 到这个任务加工截止的时间，那么我们希望是能找到一个好的安排方案， 使得总的完成时间达到最小。 这是一个例子，这里边一共有五个任务，1，2，3，4，5。 下边是它们的每个任务的加工时间。 这个实例怎么样来做它的安排呢？ 我们来看一个安排方案。这里就是一个安排方案，这个 方案呢，是按照加工时间小的先安排， 那么把它的加工时间排一下序， 最小的是3，5，8，10，15， 就是按照这个顺序来安排任务，那么它的解呢就是原来 任务标号是1号，3号，2号，4号，5号这个加工顺序。 那么对于这样的一个加工来讲，它的总的完成时间是什么呢？ 可以用下边的公式来计算，下边我们看一下这个总的完成时间的公式， 在这个公式里面，第一个任务只需要3的时间就完成了。 第二个任务呢到这个位置完成是3加5， 第三个任务是3加5加8， 这是第四个任务的时间，这是第五个任务的时间。 那总的完成时间呢，应该把这些个加起来，最后应该等于94。 观察一下这个表达式，我们发现， 第一个任务的加工时间出现了5次， 3，3，3，3，3，第二个任务的加工时间呢，出现了四次， 那么第三个任务加工时间出现了三次， 第四个任务加工时间出现了两次， 最后一个任务加工时间出现了一次。这个就是它的这个完成时间的公式。 下边对这个问题进行建模。 它的输入是任务集合标号是1到n， 第j项任务的加工时间呢是一个正整数。 这一共有n个任务的加工时间，问题的输出呢是一个排列， 相当于是i1，i2，in， 这是1，2，n的一个排列顺序。 那么在这个排列下，它的完成时间怎么计算呢，按照下面的公式计算， 我们看到这个公式它是从1到n， 这n个任务，那么k等于1的就是排在第一号的任务，它的加工时间是t1， i1，然后它出现了n次，当k等于1的话，这是它出现的次数。 那么我们对所有的k一求和呢，那这个公式就正好代表了 整个的总的完成时间，那问题的解应该 满足什么条件呢，使得这个值达到最小的那个排列，就是问题的解。 我们把这个排列记作I*，I*是加工时间 在所有加工时间达到最小的那个排列，这就是对问题的建模。 下边我们看一下刚才讲的那个算法：贪心算法。 加工时间短的先安排，这个算法它是正确的吗？ 它能不能保证对所有的输入实例都得到最优的解呢？ 我们可以证明一下，这就是证明的方法。 我们假定有一个安排的顺序，就是一个调度方案， 这个方案呢，它中间出现了一个逆序，什么叫逆序呢？就是加工时间长的排在前面了， 加工时间短的排在后面了，这就是相邻的一个逆序。 如果在这个调度中有这样的一个逆序， 下边我们把这两个任务交换一下顺序，把加 工时间短的放到前面，加工时间长的放到后面。 这样得到一个新的调度g，那么除了这两个任务以外，其他的任务的次序都不变。 我们下边观察一下，这两个不同调度的加工时间有什么变化？ 我们发现刚才的那个公式里面，加工时间 在前面的这个任务它的加工时间出现的次数要多， 在后面的这个，出现的次数要少。那我们现在加工时间长的， 到这个调度中减少了一次，而加工时间短的 在这个调度中多了一次，其他的部分都不改变。 因此这两个加工时间的差就是满足下面的公式： 就是后边这个调度加工时间减掉前面的调度的加工时间， 正好是tj就是这个短的时间减掉长的时间，这是一个负数。 所以通过这个式子说明，我们减少了一个逆序 以后，它的加工时间是总的时间是减少了， 从这个分析就可以看到，我们算法的逆序是按照加工时间从小到大排的。 它的顺序没有逆序出现，因此它在总的加工时间中达到最小的，它是个最优解。 但是这种直觉， 就是我们想着加工时间短的先加工，这样的想法 并不是在所有的问题中都是正确的。这里有一个反例： 背包，这个问题是有四件物品： 1号，2号，3号，4号四件物品， 每个物品呢，它有一个重量：3，4，5，2这是它们的重量。 下边是价值：7，9，9，2这是价值。 背包呢最多装6重量， 这种情况下你怎么选择物品使得装入背包的价值达到最大？ 这是一个典型的实例。背包问题的实例。 下边我们想想看怎么装合适呢？可能会想到 单位重量的价值越大的优先装，这可能是一种可行的方法。 下边我们就来看一看刚才那个实例。 如果我们把它按照单位重量的价值， 从大到小排个序，那么这个是1号物品， 它的重量是3，价值是7， 这个单位重量价值大于2号，2号大于3号，3号大于4号。所以这是一个排序。 那按照这个排序来讲我们先装1号物品， 这就是一种贪心的策略，那这个策略会得到什么解呢？ 我们可以看到先装了1号物品以后，2号不能装了，一装超重了。 3加4大于6了。3号也不能装了，只能装4号物品。 这样装的是1号和4号物品，重量达到了5，价值正好是9。 但是这个是不是问题的最优解呢？我们来看一下， 实际上有一个更好的解，就是这个解。 装2号和4号物品，单位价值，单位重量价值最大的 不装，那这个时候它的 解是2，4两个物品，重量达到了6，而价值达到了11，显然比这个9的价值要好。 所以通过这个例子看到，贪心的选择不一定对所有的问题它都是正确的。 这就是涉及到算法设计的问题。 我们看一下算法设计是做什么事情。首先要对问题建模。 刚才我们讲到的，这两个例子背包和刚才讲到的 这个调度问题都是建模。然后选择什么样的算法，如何描述这个算法， 下边考虑的是这个算法是不是对所有的实例都得到最优解。 你怎么证明它的正确性，如果不是的话，能不能找到反例。 这就是算法设计所需要考虑的一些事情。 下边我们看看另外的一个例子。 这个例子呢是投资问题，有m元钱，投资给n个项目， 每个项目投资它有一个效益函数就是 x元钱，投给第i个项目，它产生的效益由这个函数来计算。 下边我们是讲的是这m元钱分配给n个项目，你怎么分配？ 就是每个项目得多少钱？这样使得总的投资效益达到最大。 这也是一个组合优化问题。下边就是一个实例： 这是5万元钱，投资给4个项目， 这个表就是效益函数表，这个投资给第一个 项目的产生的效益，这个是钱数：1，2，3，4，5这是它的效益。 这是投资给第二个项目的效益，这是第三个，这个第四个。 那么针对这样的问题，应该怎么考虑它的算法？ 首先对这个问题建模。 它的输入有这样一些参数：n 项目数，m钱数，这个是效益函数。 它的解是什么呢？解是一个n维的向量。 也就是说x1是投给第一个项目的钱数，x2是投给第二个项目的钱数， xn是投给第n个项目的钱数。你要给出了这个向量，相当于对钱的分配方案已经给出来了。 那么这一个解应该满足什么条件呢？满足下面的条件。 这个是目标函数，我们看到这是投给第i个项目的钱数xi， 投给第i个项目，它产生的效益就是这一项， 那当我们对所有的项目从1到n来求和的时候， 就是总效益，这个总效益希望它最大化。这个是我们的目标，解所要达到的目标。 那解还有个约束条件，就是你总钱数是m，因此 我们把所有的钱数投给每个项目的钱数都加起来，正好等于m，而且这个钱 我们取自然数。就是非负的整数。 这个mn，m也是一个整数，假定就是这样一个例子。 那这就是这问题进行的建模。在这个建模下，考虑什么算法呢？ 可能想到的有这种穷举的算法，就是蛮力算法。 蛮力算法就是我们考察它的每一个可行的分配方案， 计算出每个方案的效益，最后从其中找出最大效益的那个方案。 下面我们看一下这就是解的表示是一个向量， 那么这些x加起来应当正好等于m， 那有一组对这些x的一个赋值，就是一个可行的 分配方案。我们对这个方案计算出下面的效益值， 从其中找出最大的效益值的那个向量就可以了。 下面我们对刚才那个实例做一下蛮力算法。 那么一开始考虑到这个公式就是所有的 钱数的总和等于5，那么看看这些歌钱究竟有哪几个可行的分配， 第一个分配就是0005， 这个分配的效益值是24，可以通过查这个表计算出来。 那么第二个分配呢是0014，它的效益值是25， 还有第三个分配，这个分配的效益值是32， 就这样做下去，枚举出所有的分配方案呢一共有56种， 最后一个分配方案的效益值是15。 那么这里面最大的效益的方案 是哪一个呢？我们可以看到，就是这样的方案，是1031. 就是第一个是10000元，第二个不分配， 第三个项目分配3万，第四个项目分配1万。 那么它的产生的效益应该是这三个效益值加起来，最后是61. 这是一种可行的算法。 那这个算法究竟好不好呢？我们来分析一下。 下面我们看一下这个算法的效率。 就是说，满足这个方程的解有多少个？ 就是说，我们需要尝试那些个分配方案有多少个。 我们先对这个解的构成做一下估计。把这个解， 就是这个一组这样的向量可以表达成下面的一个0,1,序列， 第一部分1一共有x1个正对应它的第一个分量， 第二部分有x2个1，对应它的第二个分量。 最后一个有xn个1，对应它的最后的分量。 把这些个1的序列中间用0间隔开， 就可以得到这样的一个0,1序列。每一个分配的方案都和这种0,1,序列做一个对应。 下面看一个对应的方案。假定n=4,m=7， 这是一个实例的参数。 那么它的可行解一个分配的方案可能是1,2,3,1， 这个加起来正好是7.对于这一个解它的对应的序列那就是这是一个1， 这是两个1，三个1，一个1，中间用0隔起来。就可以照这样的对应。 那么通过这个对应可以看到，任何一个解就等于 这样序列，等于对应于这样的序列，那么解的个数呢，恰好和这个序列的个数是一样多的。 下面我们来估计一下序列的个数。序列的个数一共是 m个1，n-1个0，所以m+n-1个位置，我们选m个位置来放1， 就是这个组合数。那这个组合数表达成组合公式就是这个公式。 这个公式的计算结果呢，我们可以看到， 它是一个1+epsilon的m+n-1次方， 啊，那么这个epsilon呢是一个大于0的数。 所以相当于是一个指数函数。指数函数是非常可怕的。它增长的速度非常快。 那么，有没有更好的算法呢？ 这是所关心的问题。 所以通过这个例子我们可以看到，对于算法来讲， 有些问题很容易找到好的算法。 当然有些问题它的好多算法才需要一些设计的技术。 这次课我们介绍的是下面一些问题。 首先作为问题求解来讲，必须先要建模。 对输入参数和解给出形式化的描述或者半形式化的描述。 接着我们就要考虑求解的算法。采用什么算法设计技术， 像刚才讲过的iii啊，甚至还有其他的算法的设计技术。 那么，这个算法是不是正确，它能不能保证对所有的实例都得到正确的解， 这是需要证明的。最后要分析算法的效率。 对于有些个算法如果它的效率很低的时候 这个算法是不能使用的。像这些个问题，建模，设计算法，分析算法， 是算法设计中的主要的工作。
