算法浅析

比眉伴天荒 2022-07-16 06:29 222阅读 0赞

**算法**

经常采用的算法设计技术主要有分治法、动态规划法、贪心法、回溯法、分支限界法等。

**一、分治法**

算法思想：分而治之。将一个难以解决的大问题分解成一些规模较小的相同问题，各个击破。例如，一个国家要实现治理井井有条，从省、市、县、乡、村分而治之。

归并法是分治法中一个很好的例子。在这之前我们接触过二路归并，所以提到归并，大家会有所熟悉。不错，他们其实很像很像。

**二路归并：**

![241114583494532.png][]

看成是 n 个有序的子序列（长度为 1），然后两两归并。

![241115271305226.png][]

得到 n/2 个长度为2 或 1 的有序子序列。继续亮亮归并

![241116189748663.png][]

最后一趟

![241116487555529.png][]

**归并：**

![Center][]

**二、动态规划法**

与分治法类似，基本思想：将待求解问题分解成若干个子问题，先求解子问题，然后从子问题的解得到原问题的解。与分治法不同的是，适合用动态规划法求解的问题，经分解得到的子问题不是独立的。若用分治法来解这类问题，则相同的子问题会被求解多次，以至于最后解决原问题需要耗费指数级时间。然而，不同子问题的数目常常只有多项式量级。如果能够保存已解决子问题的答案，在需要时再找出已求得的2答案，这样就可以避免大量的重复计算，所以我们用一个表来记录所有已解决的问题的答案。不管该问题是否被用到，只要它被计算过，就将其结果填入表中。这就是动态规划。

用于求最优解。动态规划法分为线性动规，区域动规，树形动规，背包动规等

最典型的有0-1背包问题，每次放入整个物品，不可放入部分。

**三、贪心法**

贪心法经常用于解决最优化问题。与动态规划不同的是，贪心法在解决问题的策略上是仅根据当前已有的信息作出选择，一旦作出选择，不管将来有什么结果，这个选择都不会改变。通过人民币面值问题，我们知道它总是最优，因为银行的巧妙安排。贪心不是总能得到最优解，得到的是可行解。

**应用：**背包问题

它与0-1背包问题类似，知识每个物品可以部分装入背包，采用贪心策略求解，三种方式可以得到可行解：按最大价值先放背包；按最小重量先放背包；按最大单位重量价值先放背包。

**四、回溯法**

首先定义问题的解空间，将解空间很好的组织起来，用树或图的形式。然后按照深度优先的方式搜索整个解空间。

**应用：**0-1背包问题

先确定要放入的物品，然后讲0-1背包问题转换为背包问题，将部分物品装入，获取最大价值。

**总结**

*  小胜胜于智，大胜胜于德。

*  有需求，就有了算法

*  有了需求，才需要智。

*  善于思考，善于分析，不要只在自己角度想问题。

[241114583494532.png]: /images/20220716/684d825f15cc4d048473c3be397322bf.png
[241115271305226.png]: /images/20220716/ef58721a651c42b082faa69db26b0728.png
[241116189748663.png]: /images/20220716/bd27d72c57474d43bb82d7bd30f812a1.png
[241116487555529.png]: /images/20220716/9a8a7c25d1644f5bae3a14838325ff8c.png
[Center]: /images/20220716/afcd3af2abe841d3b871615349e1f055.png