第三章-蛮力法.ppt

* * * * * * * * * * * * * * 算法分析与设计Analysis and Design of Computer Algorithms 第三章 蛮力法 Brute Force * 蛮力法 就像宝剑不是撬棍一样，科学也很少使用蛮力。——Edward Lytton 认真做事常常是浪费时间。——Robert Byrne 蛮力法是一种简单直接地解决问题的方法，常常直接基于问题的描述和所涉及的概念定义。 * 蛮力法的优点 可以用来解决广阔领域的问题 对于一些重要的问题，它可以产生一些合理的算法 解决问题的实例很少时，它让你花费较少的代价 可以解决一些小规模的问题 可以作为其他高效算法的衡量标准 * 教学内容 选择排序和冒泡排序 顺序查找和蛮力字符串匹配 最近对核凸包问题的蛮力算法 穷举查找 要求 掌握蛮力法的基本思想，了解排序和查找问题的蛮力算法。 * 选择排序 A[min] * 冒泡排序 算法 BubbleSort(A[0..n-1]) //该算法用冒泡排序对数组A[0..n-1]排序 //输入：一个可排序的数组A //输出：非降序排列的数组 for i?0 to n-2 do for j?0 to n-2-i do if A[j+1]A[j] swap A[j] and A[j+1] * 顺序查找 * 蛮力字符串匹配 * 蛮力字符串匹配 Θ(n+m)=Θ(n) * 最近对问题 * 凸包问题 定义 对于平面上的一个点集合（有限或无限），如果以集合中任意两点P和Q为端点的线段都属于这个集合，则这个集合是凸的。 定义 一个点集合S的凸包是包含S的最小凸集合。 * 凸包问题 定理 任意包含n2个点（不共线）的集合S的凸包是以S中的某些点为顶点的凸多边形。 凸包问题是为一个n个点的集合构造凸包的问题。 极点：对于任何一集合中的点为端点的线段来说，它们不是这种线段的中点。 对于一个n个点集合中的两个点Pi和Pj，当且仅当该集合中的其他点都位于穿过这两点的直线的同一边时它们的连线是该集合凸包边界的一部分。 直线方程：ax+by=c a=y2-y1 , b=x1-x2, c=x1y2-y1x2 * 穷举查找 旅行商问题 穷举查找 背包问题 * 穷举查找 分配问题 N个任务分配给n个人，任务j分配给人i的成本是C[I,j] * 任务1 任务2 任务3 任务4 人员1 9 2 7 8 人员2 6 4 3 7 人员3 5 8 1 8 人员4 7 6 9 4 * 小结 蛮力法是一种简单直接地解决问题的方法，通常直接基于问题的描述和所涉及的概念定义。 蛮力法的主要优点是它广泛的适用性和简单性；它的主要缺点是大多数蛮力算法的效率都不高。 除了相关问题的一些规模非常小的实例，穷举查找法几乎是不实用的。 * * * * * * * * * * * * * *