算法 | hbut期末复习笔记

贪心选择策略:所求问题的整体最优解可以通过一系列局部最优的选择(贪心选择)得到

最优子结构:问题的最优解包括了其子问题的最优解

回溯法:具有限界函数的深度优先搜索法

回溯法的解空间:子集树&排列数算法框架

单源最短路径:

 渐进上界大O:

回溯法的搜索特点是什么

在解空间树上跳跃地深度优先搜索 ,即用判断函数判断x[k],如果正确,就遍历以x[k]为根节点的子树,如果x[k]取完了所有的值,就退回到x[k-1]

贪心算法的基本思想

贪心算法是一种在每一步选择中都采取在当前状态下最好或最优(即最有利)的选择,从而希望导致结果是全局最好或最优的算法。这种策略并不保证一定能得到全局最优解,但它通常可以在复杂问题中找到局部最优解,而且在某些情况下能得到全局最优解。

贪心算法的基本思想可以总结为以下几个步骤:
1. 局部最优:每次决策都是基于当前状态下的最佳选择,不考虑后续可能的影响。
2. 迭代进行:算法通常是自底向上的,从问题的简单部分开始,逐步构建解决方案。
3. 没有后见之明:算法不会回溯前面的决策,一旦做出选择,就不再改变。

虽然贪心算法简单直接,但它的有效性取决于问题的结构和特性。对于一些具有“贪心性质”的问题(即满足最优子结构和贪心选择引理),贪心算法能够得到解决方案。不过,如果问题不满足这些条件,贪心算法可能不会得到全局最优解。

 

 

阐述归并排序的分治思路。

讲数组一分为二,分别对每个集合单独排序,然后将已排序的两个序列归并成一个 含 n 个元素的分好类的序列。如果分割后子问题还很大,则继续分治,直到一个元素。

快速排序的基本思想是什么

快速排序的基本思想是在待排序的 N 个记录中任意取一个记录,把该记录放在最终 位置后,数据序列被此记录分成两部分。所有关键字比该记录关键字小的放在前一部分,所 有比它大的放置在后一部分,并把该记录排在这两部分的中间,这个过程称作一次快速排序。 之后重复上述过程,直到每一部分内只有一个记录为止。 

 什么是直接递归和间接递归消除递归一般要用到什么数据结构

 快速排序的基本思想是在待排序的 N 个记录中任意取一个记录,把该记录放在最终 位置后,数据序列被此记录分成两部分。所有关键字比该记录关键字小的放在前一部分,所 有比它大的放置在后一部分,并把该记录排在这两部分的中间,这个过程称作一次快速排序。 之后重复上述过程,直到每一部分内只有一个记录为止。

请写出 prim 算法的基本思想 

思路是:最初生成树 T 为空,依次向内加入与树有最小邻接边的 n-1 条边。处理过 程:首先加入最小代价的一条边到 T,根据各节点到 T 的邻接边排序,选择最小边加入,新 边加入后,修改由于新边所改变的邻接边排序,再选择下一条边加入,直至加入 n-1 条边

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/681667.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

自动控制:自治系统与非自治系统的稳定性分析

自动控制:自治系统与非自治系统的稳定性分析 在自动控制领域,理解自治系统和非自治系统的区别对于分析系统稳定性至关重要。自治系统的运动方程只与系统的状态有关,而非自治系统的运动方程则与系统的状态和时间都有关系。本文将探讨非自治系…

低代码/无代码可以降低程序员哪些门槛

低代码/无代码开发平台是一种新兴的软件开发模式,它通过图形化界面、拖拽式操作等方式,快速构建应用程序,从而降低了开发者的准入门槛。这种模式对程序员来说,不仅可以提高开发效率,还可以在某些情况下促进业务人员成为…

mysql引入表名称的注意事项

1、遇到问题 mapper中的文件是这样的 解析出来的sql是这样的 sql显示为:select * from ‘tableName’ 2、解决方法 mapper文件种使用${tableName}而不是#{tableName}

mysql高级刷题-01-求项目子任务分组计算

这条 SQL 查询用于从 Tasks 表中计算项目的相关信息,并根据项目的总时长进行排序。具体来看,这段查询的目的是将连续的任务分组为一个项目,并计算每个项目的总天数、子任务 ID 列表、项目的开始日期和结束日期。下面是对这条 SQL 查询的详细分…

java版MES系统全套源码,支持 SaaS 多租户,管理后台的 Vue3 版本采用 :vue-element-plus-admin

MES生产制造执行系统源码,有演示,自主研发,多个项目应用案例,成熟稳定。支持二次开发,商业授权后可商用。 MES系统是面向制造企业车间执行层的生产信息化管理系统,能实时监控生产过程、管理制造数据、优化生…

K8S——安全机制

目录 机制说明: 一、认证(Authentication) 1、三种认证方式 ①HTTP Token 认证:通过一个 Token 来识别合法用户 ②HTTP Base 认证:通过用户名密码的方式认证 ③HTTPS 证书认证(最严格)&am…

【并发】Synchronized的底层原理

基本概念 Synchronized【对象锁】采用互斥的方式让同一时刻最多只有一个线程能够持有【对象锁】,如果其他线程想要获取这个【对象锁】就会被阻塞住 底层实现原理 我们可能听过,synchronized底层是通过Monitor来实现的,但如何直观的观察呢&…

一起来露营吧!2024COSP上海国际户外展带您逃离城市,尽享夏日美好~

夏日,清空,微风 宜在湖畔撒欢,宜在山野放松 宜露营、听音乐、感受自然 初夏时节,微风不燥,最适合露营啦! 一块绿地,一顶帐篷,一片安静的湖 在如茵绿地上,躺进初夏里 …

同一浏览器不同用户登录覆盖问题

同一浏览器使用的 Cookie 是相同的,第二个用户登录时,将会覆盖第一个用户的登录信息。不能存放在 Cookie 内,这样不能唯一区分用户,所以将Cookies改成localStorage import Cookies from js-cookieconst TokenKey Admin-Tokenexp…

DNS域名

DNS域名 DNS是域名系统的简称 域名和ip地址之间的映射关系 互联网中,ip地址是通信的唯一标识 访问网站,域名,ip地址不好记,域名朗朗上口,好记。 域名解析的目的就是为了实现,访问域名就等于访问ip地址…

代码随想录算法训练营Day15|102.二叉树的层序遍历 226.翻转二叉树 101.对称二叉树

102.二叉树的层序遍历 /*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val val; }* TreeNode(int val, TreeNode left, TreeNode right)…

企业建设数字工厂管理系统该如何选择供应商

随着信息技术的飞速发展,数字化转型已成为企业提升竞争力的关键。在制造业领域,建设数字工厂管理系统更是实现智能化生产、优化资源配置、提高生产效率的重要途径。然而,面对市场上琳琅满目的数字工厂管理系统供应商,企业改如何选…

TCP协议的核心机制

TCP协议的核心机制 一:确认应答机制1.2:超时重传接收缓冲区 超时重传时间重置连接 一:确认应答机制 对于TCP协议来说,要解决的一个很重要的问题,就是可靠传输 可靠传输,不是指发送方能够100%的把数据发送给接收方,而是尽可能. 尤其是让发送方知道,接收方是否收到. 举个例子: …

Spring Boot 应用打 WAR 包后无法注册到 Nacos怎么办

你好,我是柳岸花开。 在微服务架构中,服务注册与发现是至关重要的一环。Nacos 作为阿里巴巴开源的注册中心,能够很好地满足这一需求。然而,在将 Spring Boot 应用打包成 WAR 部署到外部服务器时,可能会遇到服务无法注册…

实用软件分享---- i茅台 在windows上自动预约和自动获取小茅运的软件

专栏介绍:本专栏主要分享一些实用的软件(Po Jie版); 声明1:软件不保证时效性;只能保证在写本文时,该软件是可用的;不保证后续时间该软件能一直正常运行;不保证没有bug;如果软件不可用了,我知道后会第一时间在题目上注明(已失效)。介意者请勿订阅。 声明2:本专栏的…

基于JS实现《国家基本比例尺地形图分幅和编号》标准

1、标准 GB T 13989-2012国家基本比例尺地形图分幅和编号 地址:【高清版】GB T 13989-2012国家基本比例尺地形图分幅和编号 - 道客巴巴 2、1:100万比例尺 2.1 说明 2.2 计算公式 2.3 计算代码 2.3.1 元素数据定义 由于中国只到N层,所以只定义到O. …

自动控制:控制系统的灵敏度分析

自动控制:控制系统的灵敏度分析 引言 灵敏度问题在控制系统设计中至关重要。灵敏度衡量的是系统对参数变化和扰动的响应程度。本文将详细探讨灵敏度函数的概念,并推导出开环和闭环控制系统在前向路径和反馈路径元素扰动下的灵敏度表达式。 灵敏度概念…

8款监控电脑屏幕的软件排名(屏幕监控软件TOP8)

8款监控电脑屏幕的软件排名(屏幕监控软件TOP8) 作为企业管理者都想对企业的员工和电脑设备了如指掌,毕竟日防夜防家贼难防,利用电脑泄密者数不胜数,为此需要对电脑屏幕实施监控,小编为你推荐几个屏幕监控软…

vue3中 window绑定scroll事件滚动页面获取不到e.target.scrollTop

遇到的问题 vue3项目 onMounted(() > {window.addEventListener(scroll, (e) > {console.log(e.target.scrollTop)}) })想要监听页面中的滚动,然后获取滚动距离实现一些功能,发现event参数中获取不到e.target.scrollTop(印象中以前使…

Java Web学习笔记2——Web开发介绍

什么是Web? Web:全球广域网,也称为万维网(WWW World Wide Web),能够通过浏览器访问的网站。 1)淘宝、京东、唯品会等电商系统; 2)CRM、OA、ERP企业管理系统&#xff1…