也称枚举法、穷举法、蛮力法。
基本思想: 根据提出的问题枚举所有可能状态,并用问题给定的条件检验哪些是需要的,哪些是不需要的,能使命题成立即为其解。
for(循环变量x取所有可能的值):
if (x满足指定的条件):
# 执行想用的操作
print(x)
...
return ...
太多数题目如果第一时间不能想出最优解,就可以使用最简单的暴力法来完成。
顺序查找、简单选择排序、冒泡排序都属于暴力法的思路。
暴力法本质就是枚举搜索,。一般适用于枚举法求解的问题的两个条件:
暴力法优化:
回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。按照深度优先搜索的策略;
如果搜索到某一结点时要先判断该结点是否包含问题的解,如果包含问题的解,称为活结点,就从该结点出发继续探索下去;
如果该结点不包含问题的解,称为死结点,则回溯到最近的活结点继续搜索,也就是逐层向其他祖先结点回溯。
步骤如下:
分支限界法:类似于回溯法,也是一种在问题的解空间树T上搜索问题解的算法。但在一般情况下,分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出T中满足约束条件的所有解,而分支限界法的求解目标则是找出满足约束条件的一个解,或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解,即在某种意义下的最优解。
常见的有队列式搜索和优先队列搜索;
队列式搜索:存储结点的数据结构是队列,采用先进先出的方式
优先队列搜索:数据结构式优先队列(堆),按最大值或最小值优先出队的方式
分治法:把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。
贪心算法:在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。
迭代: 重复执行一系列运算步骤,从前面的量依次求出后面的量的过程。此过程的每一次结果,都是由对前一次所得结果施行相同的运算步骤得到的
递归是种算法结构,很多算法的实现是基于这个算法结构
迭代和递归可以简单的理解为:
迭代是 A 不停调用 B 递归是 A 不停调用 A