个人网站内容如何填写,厦门网站建设制作工具,营销策划精准营销,高端网站建设哪家更专业蛮力法#xff08;brute force method#xff0c;也称为穷举法或枚举法#xff09;是一种简单直接地解决问题的方法#xff0c;常常直接基于问题的描述#xff0c;所以#xff0c;蛮力法也是最容易应用的方法。虽然#xff0c;用蛮力法设计的算法时间特性往往也是最低的…蛮力法brute force method也称为穷举法或枚举法是一种简单直接地解决问题的方法常常直接基于问题的描述所以蛮力法也是最容易应用的方法。虽然用蛮力法设计的算法时间特性往往也是最低的但是许多问题我们一开始并没有很优化的算法而蛮力法则可以帮助我们从低效的算法结构中剖析低效的缘由进而提炼出更为优化的算法。 蛮力法在排序算法中的应用选择冒泡蛮力法在查找算法中的应用蛮力法在字符串匹配问题中的应用蛮力法在求解“最近对”问题中的应用蛮力法在求解凸包问题中的应用蛮力法在求解最优解问题中的应用TSP背包问题配对问题 一、蛮力法在排序算法中的应用
对于一个排序问题我们能想到的最简单的排序方法就是选择和冒泡
1、选择排序时间复杂度O(n^2) public class Main {public static void main(String[] args) {int[] a {89, 45, 68, 90, 29, 34, 17};int min;for (int i 0; i a.length-1; i) {min i;for (int j i1; j a.length; j) {if (a[j] a[min]) {min j;}}int temp a[i];a[i] a[min];a[min] temp;}for (int i 0; i a.length; i) {System.out.print(a[i] );}}
}
选择排序的思路就是如此虽也有优化思路例如每次迭代出最大值和最小值放在开头和结尾。但是选择排序必然要编译算真整个数组所以最好的优化结果也是O(n^2)。
2、冒泡排序时间复杂度O(n^2) public class Main {public static void main(String[] args) {int[] a {89, 45, 68, 90, 29, 34, 17};int min;for (int i 0; i a.length-1; i) {for (int j 0; j a.length-1-i; j) {if (a[j1] a[j]) {int temp a[j];a[j] a[j1];a[j1] temp;}}}for (int i 0; i a.length; i) {System.out.print(a[i] );}}
}
发现问题对于冒泡排序我们都知道即使已经排好顺序循环还是会继续进行即使只比较不交换。 优化思路当判断到数组已经不再发生改变之后就终止循环。
当然这就是蛮力法的一个应用通过蛮力的解法来找到优化的思路 二、蛮力法在查找算法中的应用
对于查找算法来说最简单的一个思路就是逐个匹配直到找到目标元素
顺序查找 public class Main {public static void main(String[] args) {int[] a {89, 45, 68, 90, 29, 34, 17, 0};int k 45;int i 0;a[a.length-1] k;while (a[i] ! k) {i;}if (i a.length-1) {System.out.println(i);} else {System.out.println(no find);}}
}
上面的算法不同于大家常见的算法这是在顺序查找时常用的一个小技巧将查找建添加到列表末尾也称
限位器
那么查找必定会成功这样就不比在每次循环都检查是否达到的末尾只需再循环外面做一次即可。
发现问题如果未定的数组是有序的即使后面的元素都不可能等于查找建但是算法不会停止
优化思路当我们当查到一个比查找键还大的元素仍未找到那么就可以终止循环了。
三、蛮力法在字符串匹配问题中的应用 字符串匹配问题通常是给定一个n个字符组成的串称为文本一个mmn个字符的串称为模式从文本中寻找匹配模式的子串。显然我们需要逐个匹配这是蛮力算法的典型特点。
蛮力匹配时间复杂度O(n^2) public class Main {public static void main(String[] args) {String[] a {a,b,c,d,e,f,g,h};String[] b {e,f};int flag 0;for (int i 0; i a.length-b.length; i) {int j 0;while (j b.length b[j] a[ij]) {j j1;if (j b.length-1) {flag 1;System.out.println(i);}}}if (flag 0) {System.out.println(no find);}}
}
发现问题这样的蛮力方法对于文本中的每个字母都会进行匹配而这无疑增加了许多冗余的比较 优化思路KMP算法
四、蛮力法在求解“最近对”问题中的应用
最近对问题是在计算几何问题中最简单的是指在一个包含n个点的集合中找到距离最近的两个点我们这里只研究二维空间中的版本高维计算基本类似区别只在于计算两点之间距离的公式略有不同下面是标准的欧几里得距离公式 class Point {int x;int y;public Point(int x, int y) {this.x x;this.y y;}
}
public class Main {public static void main(String[] args) {Point[] points new Point[5];points[0] new Point(1,3);points[1] new Point(2,1);points[2] new Point(3,5);points[3] new Point(4,4);points[4] new Point(5,2);double d 99999999;for (int i 0; i points.length-1; i) {for (int j i1; j points.length; j) {d Math.min(d, Math.sqrt(Math.pow(points[i].x-points[j].x, 2)Math.pow(points[i].y-points[j].y, 2)));}}System.out.println(d);}
} 由图可知最近的两个点就是35和44
发现问题开方计算实际上结果大多是无理数计算机计算整数的平方根并不是一件轻松的事情所以应该尽量在高效的算法中避免开方计算。
优化思路全都比较未开方之前的数即可 五、蛮力法在求解凸包问题中的应用
凸包问题向来是计算几何中最重要的问题之一许多各式各样的应用大多要么本身就是图凸包问题要么其中一部分需要按照凸包问题解决。
凸集合定义对于平面上一个点集合如果集合中的任意两点p和q为端点的线段都属于该集合那么称这个集合为凸集合。
凸包定义一个点集合S的凸包是包含S的最小凸集合。我们可以假设有一块板子板子上面有许多钉子用一根橡皮筋将所有的钉子都围住凸包就是以橡皮筋圈为边界的区域。 在坐标平面上穿过两个点x1, x2x2, y2的直线方程为 axby c 其中a y2- y1, b x1 - x2, c x1y2 - y1x2
上述方程基于两点式直线方程
由两个点连起来的直线会将平面分成两部分其中半个平面的点都满足axbyc 另一半平面中的点都满足axbyc 对于线上的点来说满足axbyc。因此算法的思路就是对于每个点带入axby-c判断表达式结果的符号是否相同即可。 import java.util.*;class Point {int x;int y;public Point(int x, int y) {this.x x;this.y y;}Overridepublic String toString() {return Point{ x x , y y };}
}
public class Main {public static void main(String[] args) {Point[] points new Point[6];List arr new ArrayList();points[0] new Point(1,3);points[1] new Point(2,1);points[2] new Point(3,5);points[3] new Point(4,4);points[4] new Point(5,2);points[5] new Point(3,2);arr outerTrees(points);Iterator it arr.iterator();while (it.hasNext()) {System.out.println(it.next().toString() );}}private static ListPoint outerTrees(Point[] points) {SetPoint ans new HashSet();/*** 只有一个点* */if (points.length 1){ans.add(points[0]);return new ArrayList(ans);}for (int i 0; i points.length-1; i){for (int j i 1; j points.length; j){int oneSide 0;for (int k 0; k points.length; k){if (k i || k j) {continue;}if (calcuTriangle(points[i], points[j], points[k]) 0){oneSide;}}if (oneSide points.length-2 || oneSide 0){ans.add(points[i]);ans.add(points[j]);}int otherSide 0;for (int k 0; k points.length; k){if (k i || k j) continue;if (calcuTriangle(points[i], points[j], points[k]) 0){otherSide;}}if (otherSide points.length-2 || otherSide 0){ans.add(points[i]);ans.add(points[j]);}}}return new ArrayList(ans);}private static int calcuTriangle(Point a1, Point a2, Point a3) {return a1.x * a2.y a3.x * a1.y a2.x * a3.y - a3.x * a2.y - a2.x * a1.y - a1.x * a3.y;}
} 六、蛮力法在求解最优解问题中的应用
1、TSP旅行商问题要求我们找出一条n个给定城市之间的最短路径使我们再回到出发的城市之前对欧每个城市都只访问一次。我们可以用赋权图来描述这个问题那么算法的目的就是求解一个图的最短哈密顿回路问题。
哈密顿回路同样可以定义为 其中第一个顶点和最后一个顶点相同其他n-1个顶点互不相同。那么我们就可以通过生成n-1个中间城市的组合来的到所哟逇旅行线路来出最短的线路。 import java.util.Scanner;public class Main {static int[][] a new int[5][5];static int[] bestWay new int[6];static int min 99999999;static int sum 0;static Scanner in new Scanner(System.in);public static void main(String[] args) {/*** 假设a为1号点b为2号点,c为3号点d为4号点* 1 2 2* 1 3 5* 1 4 7* 2 3 8* 2 4 3* 3 4 1* */for (int i 1; i 7; i) {int x in.nextInt();int y in.nextInt();int z in.nextInt();a[x][y] z;a[y][x] z;}for (int i 2; i a.length; i) {for (int j 2; j a.length; j) {if (j ! i) {for (int k 2; k a.length; k) {if (k ! i k ! j) {sum a[1][i] a[i][j] a[j][k] a[k][1];if (min sum) {min sum;bestWay[1] 1;bestWay[2] i;bestWay[3] j;bestWay[4] k;bestWay[5] 1;}}}}}}for (int i 1; i bestWay.length-1; i) {System.out.print(bestWay[i] --);}System.out.println(bestWay[bestWay.length-1]);System.out.println(min);}
} 发现问题我们可以发现这有3对不同的线路而对于每队线路中不同的只是线路的方向。
优化思路固定住每条线路的方向将顶点排列数目减半。
实际上用蛮力方法来解决这种问题是极为不明智的这里只是给出一个思路当顶点数目过多时还是要采用诸如动态规划贪心等方法来优化的。
2、背包问题给定n个重量为w1w2w3...wn, 价值为v1v2v3...vn的物品和一个称重为C的背包求这些物品中一个最有价值的子集。 import java.util.Scanner;public class Main {static int n, c;static int max 0;static int[] w, v;static Scanner in new Scanner(System.in);public static void main(String[] args) {n in.nextInt();c in.nextInt();w new int[n1];v new int[n1];for (int i 1; i n; i) {w[i] in.nextInt();v[i] in.nextInt();}/*** 对于n个物品会存在2^n个中组合方式* 采用二进制的1,0来表示物品是否被选择比采用数组要方便数组每次都要遍历一遍* */for (int i 0; i Math.pow(2, n); i) {int k i;int tempw 0;int tempv 0;for (int j 1; j n; j) {/*** 二进制位对应w[],v[]* 每次检查末位数字是否为1之后数去除末位数字* */if (k % 2 1) {tempw w[j];tempv v[j];}k / 2;}if (tempw c) {if (tempv max) {max tempv;}}}System.out.println(max);}
}
发现问题显然2^n次的迭代始终效率都是低下的
优化思路背包问题最好的解决方法自然是用动态规划来解决当然也可以用回溯或者分支界限法。
3、分配问题可以理解为有n个任务需要分配给n个人执行一个任务对应一个人。对于每一对i,j1,2,3,...,n来说将第j个任务分配给第i个人的成本是c[i,j]求出总成本最小的方案。我们当然不能从每一行中选出最小的元素因为这写最小的元素可能在同一列。这个问题和旅行商问题有相似之处基本思路也是将数据放到一个成本矩阵C中枚举出每种情况找出成本最小值 代码基本和TSP一样略。
发现问题同样是大数据量处理起来的效率问题
优化思路匈牙利算法
