您的浏览器版本过低,为保证更佳的浏览体验,请点击更新高版本浏览器

以后再说X

欢迎访问绘芯科技网站!

全国订购热线:
027-87052087 13329706647

行业资讯

移动屏 95% 的算法都是基于这 6 种算法思想

作者:hxceshi 发布时间:2022-01-15 03:00 次浏览

使用贪心算法求解的经典问题有:活动选择问题是《算法导论》上的例子,也是一个非常经典的问题。深度优先搜索利用的就是回溯算法思想。它的这种算法思想,使它通常用于处理广度的搜索问题,即从一组可能的解中,选择一个满足要求的解。大多数适用于动态规划的问题,都可以使用回溯算法,只是使用回溯算法的时间复杂度比较高而已。本题是回溯算法的经典应用场景深度优先搜索利用的就是回溯算法思想。它的这种算法思想,使它通常用于处理广度的搜索问题,即从一组可能的解中,选择一个满足要求的解。即回溯的处理思想,有点类似枚举搜索。深度优先搜索

如果使用贪心算法求最优解,可以按照以下 步骤求解 :

- 不可取消:选择一旦做出,在后面遇到任何情况都不可取消最后,叠加所有步骤的最优解,就是全局最优解3.3 经典案例:活动选择问题

使用贪心算法求解的经典问题有:

其中活动选择问题是最简单的,这里详细引见这个。

活动选择问题是《算法导论》上的例子,也是一个非常经典的问题。有 n 个活动(a1,a2,…,an)需要使用同一个资源(例如教室),资源在某个时辰只能供一个活动使用。每个活动 ai 都有一个开始时间 si 和结束时间 fi 。一旦被选择后,活动 ai 就占据半开时间区间 [si,fi) 。如果 [si,fi) 和 [sj,fj) 互不堆叠,ai 和 aj 两个活动就可以被安排在这一天。

该问题就是要安排这些活动,使得尽量多的活动能不冲突的举行。例如下图所示的活动集合S,其中各项活动按照结束时间单调递增排序。

共有 7 个活动,它们在 18 个小时内需要占用的时间如上图,如何选择活动,能让这间教室利用率最高喃(能够举行更多的活动)?

贪心算法对这种问题的处理很简单的,它开始时辰开始选择,每次选择开始时间与与已选择活动不冲突的,结束时间又比较靠前的活动,这样会让剩下的时间区间更长。

最终选择活动为 a1,a4,a5,a7。为最优解。

4 回溯算法 4.1 算法策略

回溯算法是一种搜索法,试探法,它会在每一步做出选择,一旦发现这个选择无法得到期望结果,就回溯回去,重新做出选择。深度优先搜索利用的就是回溯算法思想。

4.2 适用场景

回溯算法很简单,它就是不断的尝试,直到拿到解。它的这种算法思想,使它通常用于处理广度的搜索问题,即从一组可能的解中,选择一个满足要求的解。

4.3 使用回溯算法的经典案例

等等,深度优先搜索我们在图那一章已经引见过,这里以正则表达式婚配为例,引见一下

正则表达式婚配 var string = "abbc"

var regex = /ab{1,3}c/

console.log( string.match(regex) )

// ["abbc", index: 0, input: "abbc", groups: undefined]

它的婚配过程:

在第 5 步婚配失败,此时 b{1,3} 已经婚配到了两个 b 正在尝试第三个 b ,结果发现接下来是 c 。此时就需要回溯到上一步, b{1,3} 婚配完毕(婚配到了 bb ),然后再婚配 c ,婚配到了 c 婚配结束。

5 动态规划 5.1 算法策略

动态规划也是将复杂问题分解成小问题求解的策略,与分治算法不同的是,分治算法要求各子问题是相互独立的,而动态规划各子问题是相互关联的。

所以,动态规划适用于子问题堆叠的情况,即不同的子问题具有公共的子子问题算法基本思想,在这种情况下,分治策略会做出很多不必要的工作,它会反复求解那些公共子子问题,而动态规划会对每个子子问题求解一次,然后保存在表格中,如果遇到一致的问题,从表格中获取既可,所以它无需求解每一个子子问题,避免了大量的不必要操作。

5.2 适用场景

动态规划适用于求解最优解问题,比如,从面额不定的100个硬币中任意选取多个凑成10元,求怎样选取硬币才可以使最后选取的硬币数最少又刚非常好凑够了10元。这就是一个典型的动态规划问题。它可以分成一个个子问题(每次选取硬币),每个子问题又有公共的子子问题(选取硬币),子问题之间相互关联(已选取的硬币总金额不能超过10元),边界条件就是最终选取的硬币总金额为 10 元。

针对上例,也许你也可以说,我们可以使用回溯算法,不断的去试探,但回溯算法是使用与求解广度的解(满足要求的解),如果是用回溯算法,我们需要尝试去找所有满足条件的解,然后找到最优解,时间复杂度为 O(2^n^) ,这质量是相当差的。大多数适用于动态规划的问题,都可以使用回溯算法,只是使用回溯算法的时间复杂度比较高而已。

客服