APP下载

算法设计思维在人脑与电脑中的研究

2020-07-04刘家铭

现代信息科技 2020年3期
关键词:人脑电脑

摘  要:自第一台计算机诞生至今,计算机科学技术发展经历了数十载,期间取得了颇多成果,但目前还无法定义这门科学的边界。如今,大数据、云计算、人工智能、“互联网+”等新问题、新领域、新应用层出不穷,其中许多问题求解都离不开问题的建模和算法的设计与分析。文章就分治策略、动态规划、贪心法三大经典问题展开算法设计与分析,通过对经典问题的引入、求解、验证、结论这一完整过程,解析算法设计思维在人脑与电脑中的思维模式以及设计模式,对其差异性和同一性进行研究。

关键词:算法设计;算法思维;问题模型;人脑;电脑

中图分类号:TP312;TP18      文献标识码:A 文章编号:2096-4706(2020)03-0013-04

Abstract:Since the birth of the first computer in 1949,the development of computer science and technology has gone through several decades,during which a lot of achievements have been made,but still no scientist can define the boundaries of this science. Nowadays,big data,cloud computing,artificial intelligence,“internet plus” and other new problems,new fields and new applications keep emerging. In the process of tracing back to the source,many problems cannot be solved without problem modeling and algorithm design and analysis. In this paper,algorithm design and analysis are carried out for three classic problems:divide and conquer strategy,dynamic programming and greedy method. Through the whole process of introducing,solving,verifying and concluding classic problems,the thinking mode and design mode of algorithm design thinking in human brain and computer are analyzed,and the differences and identity are studied.

Keywords:algorithm design;algorithmic thinking;problem model;human brain;computer

0  引  言

清華大学出版社出版的《算法设计与分析》作为本校的任选课程教科书之一,是问题求解和程序设计的重要基础,对学生的逻辑思维和创造性有着重要的作用。本文将对其较为简单并且重要的内容进行归纳总结,再对算法设计学进行一定的深入讨论。

算法是指解题方案的完整而准确的描述,是一系列解决问题的清晰指令,这一系列指令在人脑与电脑中是可以同时存在的。不过,在解决问题时却有着截然不同的处理方式,人脑利用算法处理问题是通过思想建立模型求解问题,电脑利用算法处理问题是通过程序建立模型求解问题。在运算速度上,如今计算系统中的电脑可以做到每秒万亿次,一般情况下,人脑的计算速度也就勉强做到每秒一次。

但算法的设计不仅仅是依靠电脑进行的,因为完整的算法设计,不仅需要强大的运行速度、存储空间,更需要人脑的算法思维。这也正是一个算法的优劣可以用空间复杂度与时间复杂度来衡量,而一个算法的成败可以用人脑思维来控制的原因。

1  分治策略

分治策略是对于一个规模为K的问题,如果该问题较容易理解分析(如规模K较小)就直接解决,否则将其分解为k个规模较小的子问题,前提是这些子问题之间相互独立且与原问题形式相同,通过递归或非递归方法解这些子问题,最后将各子问题的解进行合并,模拟并且得到原问题的解。

1.1  问题引入

给定n个数,这些数已经按照递增顺序进行排序,要求输入一个数,如果输入的数存在于n个数中,返回这个数所在的位置,否则,返回-1状态码,表示该数不存在。

1.2  问题求解

对问题使用分治策略,可以分析出如下求解过程:

(1)将n个数的中位数(如果n为奇数,则向下取整求出中位数)与查找关键字比较,如果两者相等,则查找成功;

(2)若过程1不能匹配成功,则利用中位数所处位置将n个数分成前、后两半段,如果中位数大于查找关键字,则进一步查找前半段,此时后半段可抛弃,反之查找后半段,将前半段可抛弃;

(3)重复以上过程,直到找到满足条件的记录,查找成功,返回记录的关键字的位置,或直到无法分段,查找不成功,返回状态码-1。

使用C语言程序设计,关键代码如下:

1.3  问题验证

根据问题描述,可以进行用例测试。

输入格式:第一行包括数n,接下来一行是n个递增的数,最后一行是查找的关键字。

输出格式:关键词的下标。

问题验证过程如表1所示。

1.4  问题结论

处理分治问题前,需要判断出其问题性质,判断其是否符合分治思想的范畴。对于分治策略问题,应该优先考虑下面这么因素:

(1)将原问题的规模缩小到一定程度就可以较为容易地解决;

(2)将规模较大的原问题分解为若干个规模较小的相同问题;

(3)问题所分解出的各个子问题是相互独立的,即子问题不可再进行分解为新的子问题;

(4)原问题分解出的子问题的解可以合并为原问题的解。

2  动态规划

动态规划从动态性质和规划性质来说,是Operational Research(简称OR)的一个分支,将OR引入时以“运筹帷幄之中,决胜千里之外”为基础,更名为运筹学。动态规划实质上是求解决策过程最优化的数学方法。动态规划也正是为了实现最优化原理,把多阶段过程转化为一系列单阶段问题,利用各阶段之间的关系,逐个求解。

2.1  问题引入

设A和B是两个字符串。下列有3种字符操作,分别是字符的插入、删除、修改,利用这3种操作将字符串A变为B,求所需要的最少的字符操作次数。

2.2  问题求解

对问题进行动态规划,可以分析出如下求解过程:首先建立一个状态来表示两个字符串之间的操作情况,假设数组下标从0开始,dp[i][j]表示处理字符串A中的第i+1个与字符串B中的第j+1个字符所需要的步骤,对于每一种操作,都有着对应的模型建立:

(1)插入字符:假设字符串A为ac,字符串B为abc,现在需要在A中插入一个字符b,转化为处理状态即为dp[2][2]=dp[2][1]+1,对应的处理情形就是将字符串A变为abc;

(2)删除字符:假设字符串A为ac,字符串B为abc,现在需要在B中删除一个字符b,转化为处理状态即为dp[2][2]=dp[1][2]+1,对应的处理情形就是将字符串B变为ac;

(3)修改字符:假设字符串A为adc,字符串B为abc,现在需要在A中修改字符d为b,转化为处理状态即为dp[2][2]=dp[1][1]+1,对应的处理情形就是将字符串A变为abc;

(4)不做更改:假设字符串A为abc,字符串B为abc,转化为处理状态即为dp[2][2]=dp[1][1]=dp[0][0]。

不过首先应该对其进行初始化,将dp[i][0]=i,dp[0][j]=j,最后得到的操作次数应为dp[a][b],其中a,b分别代表字符串A,B最后一位字符表示的下标加1,初始化时将dp[][]的范围在字符串A或字符串B的最大长度加1。

2.3  问题验证

根据问题描述,可以进行用例测试。

输入格式:输入两个字符串。

输出格式:输出一个数值,表示最小的变化次数。

问题验证过程如表2所示。

2.4  问题结论

处理动态规划问题前,需要判断出其问题性质,判断其是否符合动态规划思想的范畴。对于分治策略问题,应该优先考虑以下因素:

(1)问题中的状态满足最优化原理:无论其初始状态和初始选择如何,对前面的决策所形成的状态而言,剩下的诸决策接着构成最优策略,即一个最优化策略的子策略也要达到最优化;

(2)问题中的状态满足无后效性:下一步骤的状态只与当前状态有关,而和之前产生的状态无关,每个状态都是过去历史的一个完整总结;

(3)子问题的重叠性:动态规划是一种以空间复杂度换时间复杂度的技术,在实现的过程中将存储产生过程中的各种状态,所以需要更多的空间,处理过程中会不可避免地将子问题重叠。

3  贪心算法

贪心算法是指在对问题求解时,放弃从整体最优角度考虑,做出在当前判断是最好的选择,最后得到的结果是在某种意义上的局部最優解。

3.1  问题引入

给一个n个点m条边的无向图,求点s到点t的最短路径的大小,并且将路径打印出来。

3.2  问题求解

对问题进行贪心算法(又称Dijkstra算法),该算法能达到整体意义上的最优解,也方便对其进行理解,可以分析出如下求解过程:

(1)引入一个辅助动态数组(vector)V,它的每个元素V[i]表示当前所找到的从源点v到其他每个顶点vi的长度;

(2)V的初始状态为:若从v到vi存在连通边,则V[i]为从v到vi的边的权值;否则置D[i]为∞;

(3)从源点v到下一个顶点的最短路径长度所对应的顶点,且这条最短路径长度仅次于从源点v到顶点vj的最短路径长度;

(4)V为已求得的从源点v出发的最短路径长度的顶点的集合,则可证明:下一条次最短路径(设其终点为e)要么是从顶点v到顶点e,或者是从源点v出发,中间经过V中的顶点而最后到达顶点e的路径。

使用C语言程序设计,关键代码如下:

3.3  问题验证

根据问题描述,可以进行用例测试。

输入格式:第一行包括数n,m,s,e,分别表示为图的顶点数、边数、开始点、结束点,后m行,由n1,n2,l组成,表示n1,n2两点之间存在路径,长度为l。

输出格式:第一行输出从开始点到结束点的距离,第二行显示路径。

问题验证过程如表3所示。

3.4  问题结论

处理贪心问题前,需要判断出其问题性质,判断其是否符合贪心思想的范畴。对于贪心问题,应该优先考虑以下因素:

(1)贪心算法适用于求解最优化问题;

(2)算法的正确性证明方法包括数学归纳法和交换论证法;

(3)求解过程是自顶向下,先做贪心选择,然后将规模较大的子问题归约为规模更小的子问题;

(4)如果贪心算法得不到最优解,可以对问题的输入进行分析或者估计算法的近似比;

(5)通常对原始数据排序之后,贪心算法是一轮处理,时间复杂度和空间复杂度低。

4  算法、人脑、电脑间的关系

如果将三者结合在一起运用,可以解决目前已知的任何难题,因为在自然科学中,问题的产生其实就是这一过程。其中,先从人脑开始讨论,人脑的功能主要可概括为记录、整合、分析、传播,理论上人脑的功能是无上限的,但是存在的弊端就是被现实所阻挡。此时,可以将这一过程交付给电脑,人脑依靠思想架构,电脑也是如此,在人脑与电脑的关系上做到有机的整合。这种整合就又涉及到算法,算法即模型,通过摩尔定律可知,未来的算法价值将会更大。

正如上文所写的内容一样,人们在规范问题时,不是以人脑某种思考角度直接命名,也不是以电脑某种程序角度直接命名,而是将其归结为算法命名。其实还有更多的算法,如回溯法、线性规劃、网络流算法、近似算法、随机算法、量子算法等,这些已经存在的算法内容更为复杂,也是人脑和电脑共同编译产生的结果。

5  结  论

人脑思维的模型构建,为算法设计提供了清晰的指令,而电脑软硬件的更新迭代,为算法实现提供了更大的运行空间。但随之而来的是三者的同步问题,为此有必要以一种有效的连接方法将人脑、电脑、算法进行整合,防止不同步骤下会产生失败的结果,以此保证问题得以正确解决。至此,本文仅介绍了几种算法模型,给出了人脑的思维过程和电脑的编码过程,在后期随着知识的积累将对其进行进一步的深入研究。

参考文献:

[1] 屈婉玲,王捍贫,段莉华.面向软件工程学科的算法课程建设 [J].中国大学教学,2012(12):55-57.

[2] 刘家铭.基于大数据背景下的数据安全分析 [J].现代信息科技,2019,3(18):129-130.

作者简介:刘家铭(1999-),男,汉族,江西南昌人,本科在读,研究方向:软件工程。

猜你喜欢

人脑电脑
人脑拥有独特的纹路
自己买电脑
让人脑洞大开的建筑
秘鲁医院收集近3000人脑供公众参观
创意无限的另类汉堡
脑筋急转弯
电脑子变学霸
逻辑
The Apple of Temptation
LG与Philips分道扬镳进军电脑LCD市场等