蛮力法研究论文

《算法设计与分析基础》学习 --- 蛮力法 要重温算法思想，并以《算法设计与分析基础》这本书作为教材。该书每一章介绍一种算法设计思想。今天从最简单的开始写起，打好基础。以后再逐步深入，学习更深入的算法。 蛮力法就是一种解决问题的最简单最直观的最容易理解方法，虽然它简单，而且在实际应用中因为效率的原因可能不能派上用场，但是还是不能忽略它。正如书中作者所说，在解决小规模问题的时候也不失为一个方法，而且也是更复杂算法的基础。 一、选择排序 以最简单的思路解决排序问题，对于N个元素的数组，通过N次扫描数组，每次选择出最小的元素放置到正确的位置，N趟扫描后即完成排序。 show sourceview source print? 01/* 02 蛮力法-选择排序 03 将输入数组排成非递减数组 04 05 array:待排数组 06 n:数组大小，即[0,n-1] 07*/08void SelectionSort(int array[],unsigned int n) 09{ 10 int min; 11 for(int i=0;i0) 13 { 14 last = 0; 15 for(int j=0;jarray[j+1]) 18 { 19 int temp = array[j]; 20 array[j] = array[j+1]; 21 array[j+1] = temp; 22 23 last = j; //记录最近一次交换值的位置 24 } 25 } 26 i = last; 27 } 28}//BubbleSort但是在最差的情况下，它还是O(n*n)的时间复杂度。 三、顺序查找和字符串的蛮力匹配 顺序查找，再简单不过的查找算法了，算是对蛮力思想的一种应用。以及字符串的蛮力匹配也是这样的。

旅行商问题是经典的组合优化问题，目的是在给定的一组城市和它们之间的距离矩阵中，找到一条最短的路径，使得该路径能够经过每个城市一次且仅一次。蛮力法和回溯法是解决旅行商问题的两种常见方法。蛮力法是一种穷举搜索方法，它通过枚举所有可能的路径，找到最短的路径。这种方法简单易懂，但是随着城市数量的增加，搜索空间将呈指数级增长，计算时间将变得非常长，因此只适用于少量城市的情况。回溯法是一种更加高效的方法，它通过不断尝试不同的路径，找到最短的路径。回溯法在搜索过程中，可以根据实际情况进行剪枝，从而减少搜索的空间和时间，因此在解决大规模旅行商问题时，回溯法通常比蛮力法更加高效。总的来说，蛮力法和回溯法都是解决旅行商问题的经典方法，蛮力法简单而直观，回溯法更加高效。在实际应用中，可以根据问题的规模和特点选择合适的方法进行求解。

蛮力法（brute force method，也称为穷举法或枚举法）是一种简单直接地解决问题的方法，常常直接基于问题的描述，所以，蛮力法也是最容易应用的方法。蛮力法特性： （1）理论上，蛮力法可以解决可计算领域的各种问题。 （2）蛮力法经常用来解决一些较小问规模的问题。 （3）对于一些重要的问题（如排序、查找、串匹配），蛮力法可以设计一些合理的算法，这些算法具有实用价值，而且不受输入规模的限制。 （4）蛮力法可以作为某类问题时间性能的下界，来衡量同样问题的其他算法是否具有更高的效率。查找问题中使用蛮力法。 顺序查找： 是指在查找集合中一次查找值为k的元素，若查找成功，则给出元素在查找集合中的位置；若查找失败，则给出失败信息。 【想法】：将查找集合放在一维数组中，然后从数组的一端向另一端逐个将元素与带查找值进行比较，若相等，则查找成功，给出该元素在查找中的序号；若整个数组检测完仍未找到与带差值相等的元素，则查找失败，给出失败标志0。我们在查找过程中还要注意下标是否越界的问题。 算法的实现方法一： int SeqSearch1(int r[] ,int n, int k) //数组r[1] r[n]中存放查找集合。 { int i = n; while(i>0 && r[i]!k) //注意检测比较位置是否越界。 { i--; } return i; }上述算法我们每次都要去判断数组的下标是否越界，为了避免在查找过程中每一次比较前都要判断查找位置是否越界，可以设置观察哨，即将待查值放在查找方向的“尽头”处，则比较位置i至多移动到下标0处。