算法设计和常见的算法设计模式

时间:2018-09-14 15:47:35   来源:上海尚学堂   阅读:

一、算法设计和算法设计模式

算法设计是从问题出发,通过分析和思考最终得到一个能解决问题的过程性描述的工作过程。实际应用问题千变万化,解决它们的算法的变现形式也多种多样。但是许多算法的设计思想有相似之处,相关工作也有规律可循。算法设计中一些常见的通用想法可以称为算法设计模式。


二、常见的算法设计模式

● 枚举法。根据具体问题枚举出各种可能,从中选出有用信息或者问题的解。这种方法利用计算机的速度优势,在解决简单问题时十分有效。

​● 贪心法。如前所述,根据问题的信息尽可能做出部分的解,并基于部分解逐步扩充得到完整的解。在解决复杂问题时,这种做法未必能得到最好的解。

​● 分治法。把复杂问题分解为相对简单的子问题,分别求解,最后通过组合起子问题的解的方式得到原问题的解。

​● 回溯法(搜索法)。专指通过探索的方式求解。如果问题很复杂,没有清晰的求解路径,可能就需要分步骤进行,而每一步骤又可能有多种选择。在这种情况下,只能采用试探的方式,根据实际情况选择一个可能方向。当后面的求解步骤无法继续时,就需要退回到前面的步骤,另行选择求解路径,这种动作称为回溯。

​● 动态规划法。在一些复杂情况下,问题求解很难直截了当地进行,因此需要在前面的步骤中积累信息,在后续步骤中根据已知信息,动态选择已知的最好求解路径(同时可能进一步积累信息)。这种算法模式被称为动态规划。

● 分支限界法。可以看作搜索方法的一种改良形式。如果在搜索过程中可以得到一些信息,确定某些可能的选择实际上并不真正有用,就可以及早将其删除,以缩小可能的求解空间,加速问题求解过程。


三、需要说明的地方

这里需要说明两点:首先,上述算法设计模式只是人们对经验的总结,只能借鉴,不应作为教条。其次,这些模式并不相互隔绝也不互相排斥。例如,一般而言复杂的问题都需要分解;而最简单的情况经常可能采用枚举和判断的方式处理。所以,在很多复杂算法中可以看到多种算法模式的身影,是多种模式的有机组合。还是应该强调,对于算法设计而言,并没有放之四海而皆准的设计理论或技术,只能借鉴和灵活运用前人经验。

算法是智力活动的产物,一个好算法至少等价于一个好的定理及其证明,因为算法不仅说明了一件事可以用计算机处理,而且还可以实现为程序,真正利用计算机去解决问题。
 
北大裘宗燕著《数据结构与算法 Python语言描述》,上海尚学堂大数据培训编辑整理。
推荐相关文章:《算法和程序的关系,概念和特征,懂这些,学编程得心应手_上海Python培训
需要了解上海尚学堂大数据培训相关信息或学习视频请联系客服小姐姐。
分享:0

电话咨询

客服热线服务时间

周一至周五 9:00-21:00

周六至周日 9:00-18:00

咨询电话

021-67690939
15201841284

微信扫一扫