算法设计与王红梅第二蛮力法案例.ppt

* Chapter 4 Brute force method * 蛮力法求解凸包问题的基本思想 对于一个由n个点构成的集合S中的两个点Pi和Pj，当且仅当该集合中的其他点都位于穿过这两点的直线的同一边时（假定不存在三点同线的情况），他们的连线是该集合凸包边界的一部分。对每一对顶点都检验一遍后，满足条件的线段构成了该凸包的边界。 在平面上，穿过两个点 x1, y1 和 x2, y2 的直线是由下面的方程定义的： ax + by c 其中，a y2-y1, b x1-x2, c x1y2-y1x2 凸包问题 * Chapter 4 Brute force method * 这样一条直线把平面分成两个半平面：其中一个半平面中的点都满足ax + by＞c，另一个半平面中的点都满足ax + by＜c，因此，为了检验这些点是否位于这条直线的同一边，可以简单地把每个点代入方程ax + by c，检验这些表达式的符号是否相同。 凸包问题 该算法的效率如何呢？所有不同的点共组成了n n-1 /2边，对每条边都要对其他n-2个顶点求出在直线方程ax + by c中的符号，所以，其时间复杂性是O n3 。 * 所谓排列，就是指从给定个数的元素中取出指定个数的元素进行排序。组合则是指从给定个数的元素中仅仅取出指定个数的元素，不考虑排序。 * * Chapter 3 Brute force method * 生成n个元素子集的算法如下： 算法3.10——生成子集 1．初始化一个长度为n的比特串s 00…0并将对应的子集输出； 2．for i 1; i 2n; i++ 2.1 s++； 2.2 将s对应的子集输出； 显然，算法3.10的时间复杂性为O 2n ，也就是说和子集的数量成正比。 生成组合子集 * Chapter 3 Brute force method * 3.4.1 0/1背包问题 3.4.2 任务分配问题 组合问题中的蛮力法 * Chapter 3 Brute force method * [问题] 0/1背包问题是给定n个重量为 w1, w2, … ,wn 、价值为 v1, v2, … ,vn 的物品和一个容量为C的背包，求这些物品中的一个最有价值的子集，并且要能够装到背包中。 [想法]用蛮力法解决0/1背包问题，需要考虑给定n个物品集合的所有子集，找出所有可能的子集（总重量不超过背包容量的子集），计算每个子集的总价值，然后在他们中找到价值最大的子集。 0/1背包问题 序号 子集 重量 价值 序号 子集 重量 价值 1 17 2 18 3 19 4 20 5 21 6 22 7 23 8 24 9 25 10 26 11 27 12 28 13 29 14 30 15 31 16 32 对于一个具有n个元素的集合,其子集数量是2n,所以,不论生成子集的算法效率有多高,蛮力法都会导致一个Ω 2n 的算法. 0/1背包问题 * Chapter 3 Brute force method * 10 w1 7 v1 42 w2 3 v2 12 w3 4 v3 40 w4 5 v4 25 背包 物品1 物品2 物品3 物品4 0/1背包问题 * Chapter 3 Brute force method * 8 1,4 12 16 1,2,3,4 19 序号 子集 总重量 总价值 序号 子集 总重量 总价值 1 φ 0 0 9 2,3 7 52 2 1 7 42 10 2,4 8 37 3 2 3 12 11 3,4 9 65 4 3 4 40 12 1,2,3 14 不可行 5 4 5 25 13 1,2,4 15 6 1,2 10 54 14 1,3,4 16 7 1,3 11 不可行 15 2,3,4 12 不可行 不可行 不可行 不可行 不可行 0/1背包问题 * Chapter 3 Brute force method * 3.4.1 生成排列对象 3.4.2 生成子集 3.4.3 0/1背包问题 3.4.4 任务分配问题 组合问题中的蛮力法 * Chapter 3 Brute force method * 任务分配问题 假设有n个任务需要分配给n个人执行，每个任务只分配给一个人，每个人只分配一个任务，且第j个任务分配给第i个人的成本是C [i, j]（1≤i , j≤n），任务分配问题要求找出总成本最小的分配方案。 * Chapter 3 Brute force method