常用的算法设计策略有哪些

夏浩同学_7044

夏浩同学_7044

2020-03-18

13935人浏览

原创

常见的算法设计策略:

1、分治

分治法的设计思想是,将一个难以直接解决的大问题,分割成k个规模较小的子问题,这些子问题相互独立,且与原问题相同,然后各个击破,分而治之。

分治法常常与递归结合使用:通过反复应用分治,可以使子问题与原问题类型一致而规模不断缩小,最终使子问题缩小到很容易求出其解,由此自然导致递归算法。

2、动态规划

动态规划法与分治法类似,其基本思想也是将原问题分解成若干个子问题。与分治法不同的是,其分解出的子问题往往不是相互独立的。这种情况下若用分治法会对一些子问题进行多次求解,这显然是不必要的。动态规划法在求解过程中把所有已解决的子问题的答案保存起来,从而避免对子问题重复求解。

动态规划常用于解决最优化问题。对一个最优化问题可否应用动态规划法,取决于该问题是否具有如下两个性质:

最优子结构性质:

当问题的最优解包含其子问题的最优解时,称该问题具有最优子结构性质。

九歌
九歌

一款专注于中文诗歌创作的人工智能写作系统,可围绕主题和表达需求辅助生成具有诗歌形式的中文文本。

下载

子问题重叠性质:

子问题重叠性质是指由原问题分解出的子问题不是相互独立的,存在重叠现象。

3、贪心

当一个问题具有最优子结构性质时,可用动态规划法求解。但有时会有比动态规划更简单更直接效率更高的算法——贪心法。贪心法总是做出在当前看来最好的选择,也就是说贪心法并不从整体最优考虑,它所做出的选择只是在某种意义上的局部最优选择。

4、回溯

回溯法是对问题的解空间树进行深度优先搜索 ,但是在对每个节点进行DFS之前,要先判断该节点是否有可能包含问题的解。如果肯定不包含,则跳过对以该节点为根的子树的搜索,逐层向其祖先节点回溯。如果有可能包含,则进入该子树,进行DFS。  

5、分支限界

分支限界法的搜索策略是,在当前节点处,先生成其所有的子节点(分支),并为每个满足约束条件的子节点计算一个函数值(限界),再将满足约束条件的子节点全部加入解空间树的活结点优先队列。然后再从当前的活节点优先队列中选择优先级最大的节点(节点的优先级由其限界函数的值来确定) 作为新的当前节点。重复这一过程,直到到达一个叶节点为止。所到达的叶节点就是最优解。                                                           

相关文章

PHP速学视频免费教程(入门到精通)
PHP速学视频免费教程(入门到精通)

PHP怎么学习?PHP怎么入门?PHP在哪学?PHP怎么学才快?不用担心,这里为大家提供了PHP速学教程(入门到精通),有需要的小伙伴保存下载就能学习啦!

下载

相关标签:

本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn

相关专题

更多
GoFrame框架Web开发与路由中间件
GoFrame框架Web开发与路由中间件

本专题聚焦GoFrame框架的Web开发,拆解路由注册与匹配规则、请求参数获取、参数校验与中间件执行顺序,说明统一响应、JWT鉴权、文件上传与接口文档生成的落地方式,并补充优雅重启与测试实践。

2026.11.17

0

15

GoFrame框架安装与gf命令行工具
GoFrame框架安装与gf命令行工具

本专题围绕GoFrame框架的安装与工具链配置展开,讲清Go版本要求、gf命令行的安装方式、代理镜像与依赖准备,说明项目初始化、热编译、交叉编译打包的做法,并整理安装阶段的常见报错与验证步骤。

2026.11.17

0

15

GoFrame框架零基础入门
GoFrame框架零基础入门

本专题整理GoFrame框架的入门知识,从模块化设计理念、环境准备到跑通第一个Web服务,讲清目录分层、配置加载、日志与中间件的用法,并对比Gin、Go-Zero的差异,帮助Go开发者建立整体认知。

2026.11.17

0

15

SQLAlchemy 一对多关系怎么建立
SQLAlchemy 一对多关系怎么建立

SQLAlchemy 一对多关系怎么建立?本专题整理父子表外键、relationship 双向映射、关联查询、级联删除和加载优化等相关文章,帮助你理解并实现常见的 ORM 关系建模。

2026.11.17

0

10

SQLAlchemy 如何增删改查
SQLAlchemy 如何增删改查

SQLAlchemy 如何增删改查?本专题整理 ORM 新增记录、条件查询、更新和删除、Session 事务提交与批量处理等实用文章,帮助你掌握 Python 数据库操作流程。

2026.11.17

0

11

SQLAlchemy ORM 模型怎么写
SQLAlchemy ORM 模型怎么写

SQLAlchemy ORM 模型怎么写?本专题整理模型类定义、Mapped 字段映射、主键与约束、表结构创建和常见报错的相关文章,帮助你从基础配置到实际建模逐步掌握 SQLAlchemy。

2026.11.17

0

16

Go-Zero API开发使用教程
Go-Zero API开发使用教程

本专题聚焦Go-Zero的API开发,拆解.api描述文件的语法结构、路由与分组定义、参数绑定与校验规则,说明统一响应体、JWT鉴权、跨域与接口文档生成的落地方式,并给出网关聚合与接口测试的实践建议。

2026.11.12

160

15

Go-Zero安装与goctl环境配置教程
Go-Zero安装与goctl环境配置教程

本专题围绕Go-Zero的安装与工具链配置展开,讲清Go版本要求、goctl安装方式、代理镜像、protoc依赖与环境变量设置,说明多版本共存、升级回退与CI流水线安装的做法,并整理安装阶段的常见报错与验证步骤。

2026.11.12

120

15

Go-Zero零基础入门教程
Go-Zero零基础入门教程

本专题整理Go-Zero的入门知识,从框架定位、环境准备到跑通第一个API服务,讲清目录分层、配置加载、日志与中间件的基本用法,并对比Gin、Kratos的差异,帮助Go开发者建立整体认知,判断它是否适合当前项目。

2026.11.12

100

15

热门下载

更多
网站特效
/
网站源码
/
网站素材
/
前端模板

精品课程

更多
热门推荐
/
最新课程
phpStudy极速入门视频教程
phpStudy极速入门视频教程

共6课时 | 54.7万人学习

独孤九贱(4)_PHP视频教程
独孤九贱(4)_PHP视频教程

共89课时 | 134.3万人学习