算法设计之—直接遍历/穷举法、贪心算法_旅游资讯

admin

2024-03-15 19:06:46

算法是对完成特定问题的程序执行序列描述，表象为从问题初始状态到问题结束状态的所有路径之中寻找可行路径，若无先验经验，根据执行方式不同可以划分为无规则和有规则（启发式）方法。

无规则方法为穷举，改进方法为递推和迭代；有规则方法有分治、贪心、动态规划、分支定界法等。

穷举法：适用于解决极小规模或者复杂度线性增长，而线性规模不会很大的状态。

递推法：利用问题本身的递推关系先求解递推关系再求解问题的一种方法。一般可解决问题都能得出通项公式或者递推公式。

迭代法：辗转法。不断用变量的新值来代替旧值的过程。其重要的过程为确定迭代变量、确定迭代关系式、并对迭代过程进行控制。

一：直接遍历态（穷举法）

程序运行状态是可以别遍历的，遍历算法执行每一个状态，最终会找到一个最优的可行解。

二：分治法

对于输入规模很大的问题，直接求解问题非常困难，可把其N个输入划分成K个不通子集的集合，能够得到K个不通的子问题，并分别求出各个子问题。在得出子问题的解后，还可以找到合适的方法合并问题的解。过程为划分——求解子问题（解法一般与原问题相同）——合并。

其算法代表有：快速排序、归并排序、线性时间选择、汉诺塔问题；

大整数乘法、Strassen矩阵乘法、棋盘覆盖、最接近点对问题、循环赛日程表。

斯特拉森乘法：对矩阵运算的改进算法。