算法設(shè)計(jì)思維在人腦與電腦中的研究

摘? 要：自第一臺(tái)計(jì)算機(jī)誕生至今，計(jì)算機(jī)科學(xué)技術(shù)發(fā)展經(jīng)歷了數(shù)十載，期間取得了頗多成果，但目前還無法定義這門科學(xué)的邊界。如今，大數(shù)據(jù)、云計(jì)算、人工智能、“互聯(lián)網(wǎng)+”等新問題、新領(lǐng)域、新應(yīng)用層出不窮，其中許多問題求解都離不開問題的建模和算法的設(shè)計(jì)與分析。文章就分治策略、動(dòng)態(tài)規(guī)劃、貪心法三大經(jīng)典問題展開算法設(shè)計(jì)與分析，通過對(duì)經(jīng)典問題的引入、求解、驗(yàn)證、結(jié)論這一完整過程，解析算法設(shè)計(jì)思維在人腦與電腦中的思維模式以及設(shè)計(jì)模式，對(duì)其差異性和同一性進(jìn)行研究。

關(guān)鍵詞：算法設(shè)計(jì);算法思維;問題模型;人腦;電腦

中圖分類號(hào)：TP312;TP18 ? ? ?文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：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? 引? 言

清華大學(xué)出版社出版的《算法設(shè)計(jì)與分析》作為本校的任選課程教科書之一，是問題求解和程序設(shè)計(jì)的重要基礎(chǔ)，對(duì)學(xué)生的邏輯思維和創(chuàng)造性有著重要的作用。本文將對(duì)其較為簡單并且重要的內(nèi)容進(jìn)行歸納總結(jié)，再對(duì)算法設(shè)計(jì)學(xué)進(jìn)行一定的深入討論。

算法是指解題方案的完整而準(zhǔn)確的描述，是一系列解決問題的清晰指令，這一系列指令在人腦與電腦中是可以同時(shí)存在的。不過，在解決問題時(shí)卻有著截然不同的處理方式，人腦利用算法處理問題是通過思想建立模型求解問題，電腦利用算法處理問題是通過程序建立模型求解問題。在運(yùn)算速度上，如今計(jì)算系統(tǒng)中的電腦可以做到每秒萬億次，一般情況下，人腦的計(jì)算速度也就勉強(qiáng)做到每秒一次。

但算法的設(shè)計(jì)不僅僅是依靠電腦進(jìn)行的，因?yàn)橥暾乃惴ㄔO(shè)計(jì)，不僅需要強(qiáng)大的運(yùn)行速度、存儲(chǔ)空間，更需要人腦的算法思維。這也正是一個(gè)算法的優(yōu)劣可以用空間復(fù)雜度與時(shí)間復(fù)雜度來衡量，而一個(gè)算法的成敗可以用人腦思維來控制的原因。

1? 分治策略

分治策略是對(duì)于一個(gè)規(guī)模為K的問題，如果該問題較容易理解分析（如規(guī)模K較小）就直接解決，否則將其分解為k個(gè)規(guī)模較小的子問題，前提是這些子問題之間相互獨(dú)立且與原問題形式相同，通過遞歸或非遞歸方法解這些子問題，最后將各子問題的解進(jìn)行合并，模擬并且得到原問題的解。

1.1? 問題引入

給定n個(gè)數(shù)，這些數(shù)已經(jīng)按照遞增順序進(jìn)行排序，要求輸入一個(gè)數(shù)，如果輸入的數(shù)存在于n個(gè)數(shù)中，返回這個(gè)數(shù)所在的位置，否則，返回-1狀態(tài)碼，表示該數(shù)不存在。

1.2? 問題求解

對(duì)問題使用分治策略，可以分析出如下求解過程：

（1）將n個(gè)數(shù)的中位數(shù)（如果n為奇數(shù)，則向下取整求出中位數(shù)）與查找關(guān)鍵字比較，如果兩者相等，則查找成功;

（2）若過程1不能匹配成功，則利用中位數(shù)所處位置將n個(gè)數(shù)分成前、后兩半段，如果中位數(shù)大于查找關(guān)鍵字，則進(jìn)一步查找前半段，此時(shí)后半段可拋棄，反之查找后半段，將前半段可拋棄;

（3）重復(fù)以上過程，直到找到滿足條件的記錄，查找成功，返回記錄的關(guān)鍵字的位置，或直到無法分段，查找不成功，返回狀態(tài)碼-1。

使用C語言程序設(shè)計(jì)，關(guān)鍵代碼如下：

1.3? 問題驗(yàn)證

根據(jù)問題描述，可以進(jìn)行用例測試。

輸入格式：第一行包括數(shù)n，接下來一行是n個(gè)遞增的數(shù)，最后一行是查找的關(guān)鍵字。

輸出格式：關(guān)鍵詞的下標(biāo)。

問題驗(yàn)證過程如表1所示。

1.4? 問題結(jié)論

處理分治問題前，需要判斷出其問題性質(zhì)，判斷其是否符合分治思想的范疇。對(duì)于分治策略問題，應(yīng)該優(yōu)先考慮下面這么因素：

（1）將原問題的規(guī)模縮小到一定程度就可以較為容易地解決;

（2）將規(guī)模較大的原問題分解為若干個(gè)規(guī)模較小的相同問題;

（3）問題所分解出的各個(gè)子問題是相互獨(dú)立的，即子問題不可再進(jìn)行分解為新的子問題;

（4）原問題分解出的子問題的解可以合并為原問題的解。

2? 動(dòng)態(tài)規(guī)劃

動(dòng)態(tài)規(guī)劃從動(dòng)態(tài)性質(zhì)和規(guī)劃性質(zhì)來說，是Operational Research（簡稱OR）的一個(gè)分支，將OR引入時(shí)以“運(yùn)籌帷幄之中，決勝千里之外”為基礎(chǔ)，更名為運(yùn)籌學(xué)。動(dòng)態(tài)規(guī)劃實(shí)質(zhì)上是求解決策過程最優(yōu)化的數(shù)學(xué)方法。動(dòng)態(tài)規(guī)劃也正是為了實(shí)現(xiàn)最優(yōu)化原理，把多階段過程轉(zhuǎn)化為一系列單階段問題，利用各階段之間的關(guān)系，逐個(gè)求解。

2.1? 問題引入

設(shè)A和B是兩個(gè)字符串。下列有3種字符操作，分別是字符的插入、刪除、修改，利用這3種操作將字符串A變?yōu)锽，求所需要的最少的字符操作次數(shù)。

2.2? 問題求解

對(duì)問題進(jìn)行動(dòng)態(tài)規(guī)劃，可以分析出如下求解過程：首先建立一個(gè)狀態(tài)來表示兩個(gè)字符串之間的操作情況，假設(shè)數(shù)組下標(biāo)從0開始，dp[i][j]表示處理字符串A中的第i+1個(gè)與字符串B中的第j+1個(gè)字符所需要的步驟，對(duì)于每一種操作，都有著對(duì)應(yīng)的模型建立：

（1）插入字符：假設(shè)字符串A為ac，字符串B為abc，現(xiàn)在需要在A中插入一個(gè)字符b，轉(zhuǎn)化為處理狀態(tài)即為dp[2][2]=dp[2][1]+1，對(duì)應(yīng)的處理情形就是將字符串A變?yōu)閍bc;

（2）刪除字符：假設(shè)字符串A為ac，字符串B為abc，現(xiàn)在需要在B中刪除一個(gè)字符b，轉(zhuǎn)化為處理狀態(tài)即為dp[2][2]=dp[1][2]+1，對(duì)應(yīng)的處理情形就是將字符串B變?yōu)閍c;

（3）修改字符：假設(shè)字符串A為adc，字符串B為abc，現(xiàn)在需要在A中修改字符d為b，轉(zhuǎn)化為處理狀態(tài)即為dp[2][2]=dp[1][1]+1，對(duì)應(yīng)的處理情形就是將字符串A變?yōu)閍bc;

（4）不做更改：假設(shè)字符串A為abc，字符串B為abc，轉(zhuǎn)化為處理狀態(tài)即為dp[2][2]=dp[1][1]=dp[0][0]。

不過首先應(yīng)該對(duì)其進(jìn)行初始化，將dp[i][0]=i，dp[0][j]=j，最后得到的操作次數(shù)應(yīng)為dp[a][b]，其中a，b分別代表字符串A，B最后一位字符表示的下標(biāo)加1，初始化時(shí)將dp[][]的范圍在字符串A或字符串B的最大長度加1。

2.3? 問題驗(yàn)證

根據(jù)問題描述，可以進(jìn)行用例測試。

輸入格式：輸入兩個(gè)字符串。

輸出格式：輸出一個(gè)數(shù)值，表示最小的變化次數(shù)。

問題驗(yàn)證過程如表2所示。

2.4? 問題結(jié)論

處理動(dòng)態(tài)規(guī)劃問題前，需要判斷出其問題性質(zhì)，判斷其是否符合動(dòng)態(tài)規(guī)劃思想的范疇。對(duì)于分治策略問題，應(yīng)該優(yōu)先考慮以下因素：

（1）問題中的狀態(tài)滿足最優(yōu)化原理：無論其初始狀態(tài)和初始選擇如何，對(duì)前面的決策所形成的狀態(tài)而言，剩下的諸決策接著構(gòu)成最優(yōu)策略，即一個(gè)最優(yōu)化策略的子策略也要達(dá)到最優(yōu)化;

（2）問題中的狀態(tài)滿足無后效性：下一步驟的狀態(tài)只與當(dāng)前狀態(tài)有關(guān)，而和之前產(chǎn)生的狀態(tài)無關(guān)，每個(gè)狀態(tài)都是過去歷史的一個(gè)完整總結(jié);

（3）子問題的重疊性：動(dòng)態(tài)規(guī)劃是一種以空間復(fù)雜度換時(shí)間復(fù)雜度的技術(shù)，在實(shí)現(xiàn)的過程中將存儲(chǔ)產(chǎn)生過程中的各種狀態(tài)，所以需要更多的空間，處理過程中會(huì)不可避免地將子問題重疊。

3? 貪心算法

貪心算法是指在對(duì)問題求解時(shí)，放棄從整體最優(yōu)角度考慮，做出在當(dāng)前判斷是最好的選擇，最后得到的結(jié)果是在某種意義上的局部最優(yōu)解。

3.1? 問題引入

給一個(gè)n個(gè)點(diǎn)m條邊的無向圖，求點(diǎn)s到點(diǎn)t的最短路徑的大小，并且將路徑打印出來。

3.2? 問題求解

對(duì)問題進(jìn)行貪心算法（又稱Dijkstra算法），該算法能達(dá)到整體意義上的最優(yōu)解，也方便對(duì)其進(jìn)行理解，可以分析出如下求解過程：

（1）引入一個(gè)輔助動(dòng)態(tài)數(shù)組（vector）V，它的每個(gè)元素V[i]表示當(dāng)前所找到的從源點(diǎn)v到其他每個(gè)頂點(diǎn)vi的長度;

（2）V的初始狀態(tài)為：若從v到vi存在連通邊，則V[i]為從v到vi的邊的權(quán)值;否則置D[i]為∞;

（3）從源點(diǎn)v到下一個(gè)頂點(diǎn)的最短路徑長度所對(duì)應(yīng)的頂點(diǎn)，且這條最短路徑長度僅次于從源點(diǎn)v到頂點(diǎn)vj的最短路徑長度;

（4）V為已求得的從源點(diǎn)v出發(fā)的最短路徑長度的頂點(diǎn)的集合，則可證明：下一條次最短路徑（設(shè)其終點(diǎn)為e）要么是從頂點(diǎn)v到頂點(diǎn)e，或者是從源點(diǎn)v出發(fā)，中間經(jīng)過V中的頂點(diǎn)而最后到達(dá)頂點(diǎn)e的路徑。

使用C語言程序設(shè)計(jì)，關(guān)鍵代碼如下：

3.3? 問題驗(yàn)證

根據(jù)問題描述，可以進(jìn)行用例測試。

輸入格式：第一行包括數(shù)n，m，s，e，分別表示為圖的頂點(diǎn)數(shù)、邊數(shù)、開始點(diǎn)、結(jié)束點(diǎn)，后m行，由n1，n2，l組成，表示n1，n2兩點(diǎn)之間存在路徑，長度為l。

輸出格式：第一行輸出從開始點(diǎn)到結(jié)束點(diǎn)的距離，第二行顯示路徑。

問題驗(yàn)證過程如表3所示。

3.4? 問題結(jié)論

處理貪心問題前，需要判斷出其問題性質(zhì)，判斷其是否符合貪心思想的范疇。對(duì)于貪心問題，應(yīng)該優(yōu)先考慮以下因素：

（1）貪心算法適用于求解最優(yōu)化問題;

（2）算法的正確性證明方法包括數(shù)學(xué)歸納法和交換論證法;

（3）求解過程是自頂向下，先做貪心選擇，然后將規(guī)模較大的子問題歸約為規(guī)模更小的子問題;

（4）如果貪心算法得不到最優(yōu)解，可以對(duì)問題的輸入進(jìn)行分析或者估計(jì)算法的近似比;

（5）通常對(duì)原始數(shù)據(jù)排序之后，貪心算法是一輪處理，時(shí)間復(fù)雜度和空間復(fù)雜度低。

4? 算法、人腦、電腦間的關(guān)系

如果將三者結(jié)合在一起運(yùn)用，可以解決目前已知的任何難題，因?yàn)樵谧匀豢茖W(xué)中，問題的產(chǎn)生其實(shí)就是這一過程。其中，先從人腦開始討論，人腦的功能主要可概括為記錄、整合、分析、傳播，理論上人腦的功能是無上限的，但是存在的弊端就是被現(xiàn)實(shí)所阻擋。此時(shí)，可以將這一過程交付給電腦，人腦依靠思想架構(gòu)，電腦也是如此，在人腦與電腦的關(guān)系上做到有機(jī)的整合。這種整合就又涉及到算法，算法即模型，通過摩爾定律可知，未來的算法價(jià)值將會(huì)更大。

正如上文所寫的內(nèi)容一樣，人們在規(guī)范問題時(shí)，不是以人腦某種思考角度直接命名，也不是以電腦某種程序角度直接命名，而是將其歸結(jié)為算法命名。其實(shí)還有更多的算法，如回溯法、線性規(guī)劃、網(wǎng)絡(luò)流算法、近似算法、隨機(jī)算法、量子算法等，這些已經(jīng)存在的算法內(nèi)容更為復(fù)雜，也是人腦和電腦共同編譯產(chǎn)生的結(jié)果。

5? 結(jié)? 論

人腦思維的模型構(gòu)建，為算法設(shè)計(jì)提供了清晰的指令，而電腦軟硬件的更新迭代，為算法實(shí)現(xiàn)提供了更大的運(yùn)行空間。但隨之而來的是三者的同步問題，為此有必要以一種有效的連接方法將人腦、電腦、算法進(jìn)行整合，防止不同步驟下會(huì)產(chǎn)生失敗的結(jié)果，以此保證問題得以正確解決。至此，本文僅介紹了幾種算法模型，給出了人腦的思維過程和電腦的編碼過程，在后期隨著知識(shí)的積累將對(duì)其進(jìn)行進(jìn)一步的深入研究。

參考文獻(xiàn)：

[1] 屈婉玲，王捍貧，段莉華.面向軟件工程學(xué)科的算法課程建設(shè) [J].中國大學(xué)教學(xué)，2012（12）：55-57.

[2] 劉家銘.基于大數(shù)據(jù)背景下的數(shù)據(jù)安全分析 [J].現(xiàn)代信息科技，2019，3（18）：129-130.

作者簡介：劉家銘（1999-），男，漢族，江西南昌人，本科在讀，研究方向：軟件工程。