数据结构和算法专题---2、算法思想

news/2025/6/6 11:48:36

上文讲到算法的概念、复杂度,本文给大家介绍具体的算法思想,让大家对算法设计理念有个认识,后续再分别介绍各种算法。

算法思想

算法是解决问题的一种思想和方法,其基本思想是将一个复杂问题分解为多个简单的子问题,然后通过一定的逻辑和操作方法将这些子问题的解组合成原问题的解。

分而治之

把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题,直到最后子问题小到可以简单的直接求解,原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础,如排序算法(快速排序,归并排序),傅立叶变换(快速傅立叶变换),大数据中的MR,现实中如汉诺塔游戏。

分治法对问题有一定的要求:

  • 该问题缩小到一定程度后,就可以轻松解决
  • 问题具有可拆解性,不是一团无法拆分的乱麻
  • 拆解后的答案具有可合并性。能组装成最终结果
  • 拆解的子问题要相互独立,互相之间不存在或者很少有依赖关系

动态规划

基本思想与分治法类似,也是将待求解的问题分解为若干个子问题(阶段),按顺序求解子阶段,前一子问题的解,为后一子问题的求解提供了有用的信息。在求解任一子问题时,列出各种可能的局部解,通过决策保留那些有可能达到最优的局部解,丢弃其他。依次解决各子问题,最后一个子问题就是初始问题的解。

与分治法最大的不同在于,分治法的思想是并发,动态规划的思想是分步。该方法经分解后得到的子问题往往不是互相独立的,其下一个子阶段的求解往往是建立在上一个子阶段的解的基础上。动态规划算法同样有一定的适用性场景要求:

  • 最优化解:拆解后的子阶段具备最优化解,且该最优化解与追踪答案方向一致
  • 流程向前,无后效性:上一阶段的解决方案一旦确定,状态就确定,只会影响下一步,而不会反向影响
  • 阶段关联:上下阶段不是独立的,上一阶段会对下一阶段的行动提供决策性指导。这不是必须的,但是如果具备该特征,动态规划算法的意义才能更大的得到体现

贪心算法

同样对问题要求作出拆解,但是每一步,以当前局部为目标,求得该局部的最优解。那么最终问题解决时,得到完整的最优解。也就是说,在对问题求解时,总是做出在当前看来是最好的选择,而不去从整体最优上加以考虑。从这一角度来讲,该算法具有一定的场景局限性。

  • 要求问题可拆解,并且拆解后每一步的状态无后效性(与动态规划算法类似)
  • 要求问题每一步的局部最优,与整体最优解方向一致。至少会导向正确的主方向。

回溯算法

回溯算法实际上是一个类似枚举的搜索尝试过程,在每一步的问题下,列举可能的解决方式。选择某个方案往深度探究,寻找问题的解,当发现已不满足求解条件,或深度达到一定数量时,就返回,尝试别的路径。回溯法一般适用于比较复杂的,规模较大的问题。有“通用解题法”之称。

  • 问题的解决方案具备可列举性,数量有限
  • 界定回溯点的深度。达到一定程度后,折返

分支限界

与回溯法类似,也是一种在空间上枚举寻找最优解的方式。但是回溯法策略为深度优先。分支法为广度优先。分支法一般找到所有相邻结点,先采取淘汰策略,抛弃不满足约束条件的结点,其余结点加入活结点表。然后从存活表中选择一个结点作为下一个操作对象

文章来源:https://blog.csdn.net/u014526891/article/details/134778544
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:https://dhexx.cn/news/show-5177746.html

相关文章

构建高效预约系统:预约系统源码的设计与实现

随着社会的不断进步,预约系统在各个领域的应用愈发广泛。为了满足不同行业的需求,设计高效的预约系统源码至关重要。在本文中,我们将深入研究预约系统的设计原则,并提供一些关键的技术代码示例,帮助读者更好地理解如何…

micro_ros静态库

我觉得这个静态库也就是一个普通的库啊,调用就可以了,把这个库编译好,然后调用就可以了, 至于stm32我们当然是使用了STM32CubeMX以后使用keil arm了。 所以我觉得编写stm32包含micro_ros的部分完全实在Windows上面开发的&#x…

数据表记录的操作

一、数据添加 1、打开SSMS,附加数据库(数据库文件在自己的文件夹下面),并进行下面的设置: (1)设置“部门信息”表中的“编号”为主键(SSMS) 首先建立好所需的数据库库…

【Jeecg Boot 3 - 保姆级】第1节 docker + redis + nginx + redis一键安装启动

一、前言 ▶ JEECG-BOOT 开源版难以吃透的原因 ▶ 为了针对上面痛点,笔者做了如下安排 ▶ 你能收获什么 二、效果(第一节效果) ▶ 启动后端 > 日志 > 接口文档 ▶ 启动前端 三、准备工作 四、实战 ▶ 1、服务器安装 Stag…

【11】Qt Designer

目录 VSCode添加外部工具 QtDesigner PyUIC PyRCC 加载UI文件模板代码 QMainWindow QWidget 常用知识点 1. 修改标题图标 2. 图片资源管理 3. 图片按钮 4. 加载对话框 5. 动态加载Widget 6. 修改主题 其他注意事项 事件被多次触发 PyQt5提供了一个可视化图形工…

机器学习算法(9)——集成技术(Bagging——随机森林分类器和回归)

一、说明 在这篇文章,我将向您解释集成技术和著名的集成技术之一,它属于装袋技术,称为随机森林分类器和回归。 集成技术是机器学习技术,它结合多个基本模块和模型来创建最佳预测模型。为了更好地理解这个定义,我们需要…

Python中函数的递归调用

函数调用自己的编程方式被称为函数的递归调用。递归通常能够将一个大型的复杂问题的递归条件,一层一层的回溯到终止条件,然后再根据终止条件的运算结果,一层一层的递进运算到满足全部的递归条件。它能够使用少量程序描述出解题过程中的重复运…

visual studio code 好用的插件

vscode-icons Better comments 该插件对不同类型的注释会附加了不同的颜色,更加方便区分,帮助我们在代码中创建更人性化的注释。 Error Lens Error Lens插件是一款可以检测你编写的代码的语法错误,并且会显示出对语法错误的诊断信息…

最简单的基于 FFmpeg 的音频解码器

最简单的基于 FFmpeg 的音频解码器 最简单的基于 FFmpeg 的音频解码器正文参考工程文件下载 参考雷霄骅博士的文章,链接:最简单的基于FFMPEGSDL的音频播放器:拆分-解码器和播放器 最简单的基于 FFmpeg 的音频解码器 正文 FFmpeg 音频解码器…

华为数据之道学习笔记】3-5 规则数据治理

在业务规则管理方面,华为经常面对“各种业务场景业务规则不同,记不住,找不到”“大量规则在政策、流程等文件中承载,难以遵守”“各国规则均不同,IT能否一国一策、快速上线”等问题。 规则数据是结构化描述业务规则变量…