智能科學(xué)技術(shù)導(dǎo)論-周昌樂-第03講 算法設(shè)計(jì)
《智能科學(xué)技術(shù)導(dǎo)論-周昌樂-第03講 算法設(shè)計(jì)》由會(huì)員分享,可在線閱讀,更多相關(guān)《智能科學(xué)技術(shù)導(dǎo)論-周昌樂-第03講 算法設(shè)計(jì)(12頁(yè)珍藏版)》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。
1、第03講算法設(shè)計(jì) 導(dǎo)語(yǔ) 算法是智能計(jì)算領(lǐng)域最核心的概念之一。當(dāng)你擁有 了一臺(tái)機(jī)器,希望機(jī)器系統(tǒng)能夠?yàn)槟惴?wù),解決你需要 解決的某個(gè)智能計(jì)算任務(wù),那你首先要給出完成這項(xiàng)任 務(wù)的算法步驟。比如,你希望具備猜?lián)淇伺祁伾@樣一 個(gè)魔術(shù)游戲的能力,那么你就需要為機(jī)器編制完成這樣 任務(wù)的算法。如果說對(duì)于計(jì)算機(jī)科學(xué)技術(shù)的學(xué)生而言, 玩的就是算法,那么對(duì)于智能科學(xué)技術(shù)的學(xué)生而言,玩 的就是智能算法! 正是通過使用算法,可以將智慧編進(jìn)機(jī)器系統(tǒng)中, 從而來構(gòu)建能夠表現(xiàn)智能行為的機(jī)器。因此,你編制的 算法越有智慧,那么所構(gòu)建的機(jī)器也就越能夠具有更智 慧的行為表現(xiàn)。從某中意義上講,機(jī)器智能的限度就是 能否找到算
2、法的限度。那些能夠找到算法的智能任務(wù)范 圍,也就是智能機(jī)器的能力范圍。 智能科學(xué)技術(shù)研究的目的,就是要找出盡可能多的 智能算法,使我們的機(jī)器擁有盡可能多的智慧能力。由 此可見,算法在智能科學(xué)與技術(shù)領(lǐng)域中的重要地位,掌 握算法設(shè)計(jì)的原理,也就成為學(xué)習(xí)這一專業(yè)的最基本技 能。 第3.1節(jié)算法概述 一般而言,所謂算法就是給出解決一個(gè)(智能)計(jì) 算問題具體步驟的集合。我們?cè)谇懊?機(jī)器系統(tǒng)〃一講中 已經(jīng)遇到過一些簡(jiǎn)單的指令執(zhí)行算法。比如中央處理機(jī) 常規(guī)處理''算法〃就是,只要未發(fā)出停機(jī)指令就執(zhí)行以下 步驟: (1)獲得指令;(2)指令解碼;(3)執(zhí)行指令。 “煮雞蛋吃”算法如下:(1)從冰箱里
3、取一枚雞 蛋;(2)將雞蛋放進(jìn)煮鍋;(3)鍋里加水直到蓋滿雞 蛋;(4)持續(xù)給鍋加溫直到沸騰為止;(5)停止加溫 取出雞蛋;(6)將雞蛋放入涼水浸泡1分鐘;(7)敲 破雞蛋殼,去除全部蛋殼;(8)將去殼后的雞蛋一口 一口吃掉。 “遛小狗”算法:(1)給小狗套上狗繩,(2) 出門上路;(3)如果遇到樹小狗在逗留,則等待小狗 尿尿;(4)繼續(xù)前進(jìn),如果遛狗時(shí)間沒有達(dá)到規(guī)定的 時(shí)間,則繼續(xù)遛狗轉(zhuǎn)(3),否則返回。 “擺蓍成卦”算法:探蓍,古代問卜的一種方式, 用手抽點(diǎn)蓍草莖的數(shù)目,以決定吉兇禍福。其法為,大 衍之?dāng)?shù)五十,其用四十有九,分而為二以象兩,掛一以 象三,探之以四以象四時(shí),歸奇于劫以象閏
4、,五歲再閏, 故再營(yíng)而后卦。是故四營(yíng)而成易(爻),十有八變而成 卦。八卦而小成,引而伸之,觸類而長(zhǎng)探,天下之能事 畢矣。 如果強(qiáng)調(diào)精確性,那么實(shí)際卦象生成算法如下(重 精品文檔 復(fù)如下三變步驟之六遍,共計(jì)十八變): (1) 大衍之?dāng)?shù)50,其用49: 50根蓍草,去其1而不用, 令可用之?dāng)?shù)s=49,余數(shù)之和t=0,循環(huán)如下操作三變: (2) 分二(分而為二以象兩):余49根隨意分為左右 兩堆(天意) (3) 掛一(掛一以象三):從右堆中取出1根 (4) 探四(探之以四以象四時(shí)):對(duì)左右兩堆均以四 根一組數(shù)之,令其為新的可用之?dāng)?shù)s (5) 歸奇(歸奇于執(zhí)以象閏):t=t+兩堆得出的余
5、數(shù) 之和 (6) (故四營(yíng)而成易):不到三變轉(zhuǎn)(2) (7) 根據(jù)y= (49-t)/4來決定一個(gè)爻畫:y=7 (少陽(yáng))、 8 (少陰)、9 (老陽(yáng))、6 (老陰) 通過上述幾個(gè)算法例子,我們不難了解算法的一些 特點(diǎn)。但作為機(jī)器系統(tǒng)能夠嚴(yán)格精確執(zhí)行的操作步驟集 合,我們必須對(duì)算法下一個(gè)嚴(yán)格的定義:算法是一組明 確的、可以直接執(zhí)行之步驟的有限有序集合。 (1) 有序性:算法中所有步驟均規(guī)定有執(zhí)行順序的; (2) 有限性:算法中的步驟是有限的; (3) 明確性:集合中的每條指令均是明確的、可以直 接執(zhí)行的步驟。 有時(shí)候,我們還會(huì)要求每一個(gè)算法不但構(gòu)成步驟是 有限的,而且還要求這些步
6、驟的動(dòng)態(tài)執(zhí)行也是在有限時(shí) 間中能夠結(jié)束的,即所謂(4)終止性。不過,對(duì)于特 殊算法,有時(shí)候我們卻需要永不終止,如操作系統(tǒng)。關(guān) 于這個(gè)話題,更多地涉及到計(jì)算理論的內(nèi)容,并跟算法 效率的討論有關(guān)。我們不做展開了。 對(duì)于算法而言,還有一個(gè)重要的方面就是一定區(qū)分 算法內(nèi)涵與算法描述之間的區(qū)別。算法的內(nèi)涵是指一個(gè) 算法所固有的功能本質(zhì),完成某一任務(wù)的具體步驟及其 內(nèi)在聯(lián)系。而算法的描述則是具體給出的一種表示方式。 一個(gè)算法可以有不同的描述文本,這些描述文本完成的 任務(wù)完全一致,因此代表著一個(gè)相同的抽象本質(zhì)。 就好像一本書與一個(gè)故事的區(qū)別,一個(gè)故事可以寫 成不同版本的書,而這不同版本的書卻講述的是同一
7、個(gè) 故事。算法的抽象本質(zhì),是任務(wù)固有的復(fù)雜本性所決定 的,而算法的表示只是完成這一任務(wù)之算法的一種具體 描述。如果我們考慮到算法的執(zhí)行問題,還需要區(qū)分程 序、算法與進(jìn)程三者的關(guān)系。程序是算法的描述,進(jìn)程 是執(zhí)行程序的活動(dòng),而執(zhí)行一個(gè)程序就是執(zhí)行這個(gè)程序 所表達(dá)的算法,因此進(jìn)程是算法執(zhí)行活動(dòng)。 最后,對(duì)于算法,還要考慮算法的效率與正確性問 題。效率是指執(zhí)行一個(gè)算法所要花費(fèi)的時(shí)空代價(jià)。時(shí)間 代價(jià)是指算法執(zhí)行中花消的時(shí)間,而空間代價(jià)是指算法 執(zhí)行中花消的內(nèi)存。當(dāng)然,一般我們僅僅從理論上來討 論算法的效率,并不考慮具體的機(jī)器系統(tǒng),加上空間代 (活動(dòng)1) 精品文檔 價(jià)可以轉(zhuǎn)化為時(shí)間代價(jià)。因此
8、,在考慮算法的效率時(shí), 主要查看對(duì)于給定的輸入數(shù)據(jù)規(guī)模,一個(gè)算法需要?jiǎng)討B(tài) 執(zhí)行多少個(gè)計(jì)算步驟,稱為算法的計(jì)算復(fù)雜性。 算法的計(jì)算復(fù)雜性是由算法所解決的問題本身的 復(fù)雜本性所決定的,這是算法問題的計(jì)算復(fù)雜性。不過, 同樣的問題可以有不同的算法來解決,這些不同算法的 計(jì)算復(fù)雜性才是反映算法效率的關(guān)鍵。我們希望,對(duì)于 給定的問題,都能夠找到最低計(jì)算復(fù)雜性的那個(gè)算法, 剛好反映了問題本身的計(jì)算復(fù)雜性。 衡量算法計(jì)算復(fù)雜性一般用輸入數(shù)據(jù)的規(guī)模來比 照,也即算法計(jì)算復(fù)雜性是其輸入數(shù)據(jù)規(guī)模的函數(shù),通 常記為: O (f (n)) 其中n為算法輸入數(shù)據(jù)的規(guī)模,f()為算法的計(jì)算 復(fù)雜性函數(shù),O()為復(fù)
9、雜性當(dāng)量。從理論上講,可以 將算法按照計(jì)算復(fù)雜性函數(shù)類別來進(jìn)行分類,比如函數(shù) 為對(duì)數(shù)函數(shù)的就稱為對(duì)數(shù)復(fù)雜性,多項(xiàng)式的就稱多項(xiàng)式 復(fù)雜性(又分為k次多項(xiàng)式)、指數(shù)的稱為指數(shù)復(fù)雜性。 至于算法的正確性,則是要確保算法確實(shí)解決了給 定的問題。目前,證明算法正確性的方法主要有兩種途 徑:一是軟件測(cè)試途徑,就是具體地運(yùn)行算法的程序, 采用各種選擇測(cè)試數(shù)據(jù)的方法來系統(tǒng)地測(cè)試軟件,分析 算法的結(jié)果是否符合規(guī)定的(中間環(huán)節(jié)或最終結(jié)果)輸 出要求;另一種是程序正確性證明方法,主要是從理論 上分析證明算法的正確性。 當(dāng)然我們希望所構(gòu)造的算法都是正確的,即確實(shí)剛 好解決了所要解決的問題,不多也不少。但實(shí)際上,當(dāng)
10、 需要解決的問題足夠復(fù)雜時(shí),很難保證構(gòu)造的算法是正 確的,往往或存在許多漏洞(bug),常常會(huì)給各種智 能系統(tǒng)帶來災(zāi)難性的后果,比如航天飛機(jī)的發(fā)射失敗, 往往就是因?yàn)檐浖惴ㄉ系囊稽c(diǎn)點(diǎn)小問題導(dǎo)致的。因此, 算法設(shè)計(jì)也是大事,不可不慎! 第3.2節(jié)算法構(gòu)造 構(gòu)造算法的前提,首先是要給出某種算法表示的方 式。盡管算法功能是超越具體的表達(dá)形式的,但功能總 是要通過一定的形式來呈現(xiàn)的。日常生活中我們一般采 用自然語(yǔ)言來發(fā)表我們的思想,也常常采用某圖式來表 達(dá)事物及其關(guān)系。但對(duì)于算法而言,由于明確性的要求, 因此往往需要某中精確的形式語(yǔ)言來作為算法表達(dá)的 語(yǔ)言,這種可以精確描述算法的形式語(yǔ)言就成為原
11、語(yǔ)。 定義原語(yǔ)一般包括兩個(gè)方面的考慮,語(yǔ)法和語(yǔ)義。 語(yǔ)法規(guī)定原語(yǔ)中符號(hào)組合的規(guī)則,語(yǔ)義則說明原語(yǔ)中符 號(hào)及其組塊的含義。為了既兼顧機(jī)器算法執(zhí)行的精確可 行性,又兼顧人們算法描述的直觀方便性,并且具有某 種通用性,因而可以忽略實(shí)現(xiàn)某種程序設(shè)計(jì)語(yǔ)言的細(xì)節(jié), 一般采用一種稱為偽碼的符號(hào)系統(tǒng)來作為描述算法的 精品文檔 原語(yǔ)。 所謂偽碼(psudocode)是一種重在表達(dá)算法思想 的非正式符號(hào)系統(tǒng),常常用在算法的開發(fā)進(jìn)程之中。與 一般高級(jí)程序設(shè)計(jì)語(yǔ)言相比較,偽碼的主要特點(diǎn)是,既 具有直觀方便性的優(yōu)點(diǎn),又忽略了嚴(yán)格語(yǔ)法的規(guī)范性。 由于算法思想主要是通過各種遞歸語(yǔ)義結(jié)構(gòu)來描述的, 因此與所有描述算法的
12、語(yǔ)言符號(hào)系統(tǒng)一樣,偽碼必須要 能夠給出各種遞歸語(yǔ)義結(jié)構(gòu)的表達(dá)方法。有時(shí)為了直觀 表達(dá)算法的思想,也常采用一種稱為流程圖的圖式來對(duì) 偽碼描述的算法作補(bǔ)充說明。]— '起/止點(diǎn)輸入/輸出一處理 準(zhǔn)備預(yù)定義處理 ——0 C ? 判斷 控制流 外接 內(nèi)接 流程圖的基本符號(hào) 上圖給出了流程圖的基本符號(hào),下面我們針對(duì)主要 的遞歸語(yǔ)義結(jié)構(gòu),結(jié)合流程圖表示,來給出一種算法原 語(yǔ)具體規(guī)范。 (1)賦值語(yǔ)義結(jié)構(gòu):如果用name表示變量名稱,用 expression表示與name有關(guān)的數(shù)值表達(dá),那么我們稱: name—expression 為一個(gè)賦值語(yǔ)義結(jié)構(gòu),其含義表示“ 把expression 的
13、值賦給name”。比如: x—3+4y 就表示將3+4y表達(dá)式計(jì)算結(jié)果的值賦給x。一旦這一計(jì) 算結(jié)束后,變量x的值,就變成“3+4y” 了,但注意變 量y的值保持不變。 i 賦值語(yǔ)句流程圖 name—expression (2)條件語(yǔ)義結(jié)構(gòu):根據(jù)某個(gè)條件式的是否成立,來 決定采取進(jìn)一步的計(jì)算活動(dòng)。表示這樣算法步驟的語(yǔ)義 結(jié)構(gòu),就稱為條件語(yǔ)義結(jié)構(gòu)。一般采用如下的描述形式: if (條件)then (活動(dòng)1) else (活動(dòng)2) 或者 if (條件)then (活動(dòng)) 其中if、then、else這些關(guān)鍵詞稱為保留詞(不允許算 法設(shè)計(jì)者用做命名變量名稱的詞,稱為保留詞),用
14、于 界定一個(gè)條件語(yǔ)義結(jié)構(gòu)不同部分(內(nèi)部)和作用范圍(外 部)。 在上述條件語(yǔ)義結(jié)構(gòu)中,第一個(gè)式子的含義表示“如 果(條件)成立,就執(zhí)行 否則執(zhí)行(活動(dòng)2) ”, 第二個(gè)式子的含義 表示"如果(條件)成立, 就執(zhí)行(活動(dòng))”。比如, 精品文檔 if (xW6) then (y—x+2) else (y—x+6) 就是一個(gè)條件語(yǔ)義結(jié)構(gòu)。 條件語(yǔ)句流程圖 (3) 循環(huán)語(yǔ)義結(jié)構(gòu):用來表示只要某個(gè)條件式保持為 真就繼續(xù)規(guī)定的計(jì)算活動(dòng),表示這樣的算法步驟的語(yǔ)義 結(jié)構(gòu),就稱為循環(huán)語(yǔ)義結(jié)構(gòu)。一般采用如下的描述形式: while (條件)do (活動(dòng)) 其中while和do也是保留詞。循環(huán)語(yǔ)義結(jié)
15、構(gòu)的含義是 “檢查(條件)是否滿足,如果其為真就執(zhí)行(活動(dòng)),
并返回再次檢查(條件)。只有當(dāng)某次檢查(條件)不
滿足時(shí),才結(jié)束算法步驟?!?W 木
比如*初始值假定 2 16、使 得這樣的偽碼表示更加具有可讀性,一般規(guī)定語(yǔ)句之間 用分號(hào)隔開,如果一個(gè)語(yǔ)句內(nèi)部嵌有另一個(gè)語(yǔ)句,則采 用縮進(jìn)格式。
比如語(yǔ)句
if (xW6) then (y—x+2) else (if (xW6) then ( y—x+2) else (y—x+6))
寫成縮進(jìn)格式就是
if (xW6)
then (y—x+2)
else (if (xW6)
then (y—x+2)
else (y—x+6)
)
進(jìn)一步,對(duì)于重復(fù)出現(xiàn)的偽碼段或者相對(duì)獨(dú)立的一 段代碼,可以用固定名稱加以命名定義,稱為過程,然 后在需要出現(xiàn)的地方直接用該名稱替代這段偽瑪。一般 過程的定義方式為
proc 17、edure name (參量)
偽瑪段
引用之處直接用語(yǔ)句"procedure name”來替代所定義 的
這段“偽瑪段”。
過程語(yǔ)句流程圖L , name (參量) 精品文檔
比如下面就定義了一個(gè)稱為greetings的過程: procedure greetings (y)
x—y;
while (xW6) do
(print ("hello”);
x—x+1)
此時(shí),在其他需要完成這一過程功能的地方,只需 要直接調(diào)用這一過程名即可,比如
if (xW10) then (procedure greetings (3))
有時(shí)候,為了使得偽碼可讀性更高,在嵌套的語(yǔ)句 中 18、,每一層語(yǔ)句的結(jié)束,都用明顯的標(biāo)識(shí)來醒目地加以 標(biāo)記,比如end while、end if等,使得偽碼的嵌套 層次更加一目了然。當(dāng)然,這種做法并非是強(qiáng)制性的, 依賴于個(gè)人偏好。作為中國(guó)人,有時(shí)也可以用漢語(yǔ)保留 詞來替換英語(yǔ)保留詞,以及只要不影響算法思想的表達(dá), 可以采用你自己認(rèn)為的習(xí)慣方式來規(guī)定你的偽碼表達(dá) 習(xí)慣,前提是要讓別人能夠理解可讀。
有了表示算法的偽碼原語(yǔ),現(xiàn)在我們可以來介紹如 何編寫解決具體問題的算法了,即所謂的算法構(gòu)造。針 對(duì)某個(gè)具體需要解決的問題,算法構(gòu)造可以分為兩個(gè)階 段:發(fā)現(xiàn)解決該問題的算法,以及用偽碼將發(fā)現(xiàn)的算法 表達(dá)出來。如果你已經(jīng)熟練掌握了偽碼的使用,那么很 顯然, 19、構(gòu)造算法的重點(diǎn)在于發(fā)現(xiàn)算法。其實(shí),發(fā)現(xiàn)算法 就是一個(gè)理解解決問題的過程。
從算法發(fā)現(xiàn)的角度看,可以將解決問題的一般原理 對(duì)應(yīng)到如下這樣四個(gè)階段上:
階段1理解問題
階段2尋找一個(gè)可能解決問題的算法過程(思路)
階段3闡明算法并且用程序?qū)⑵浔磉_(dá)出來
階段4從準(zhǔn)確度以及作為解決其他問題的一個(gè)工 具的潛力這兩個(gè)方面來評(píng)估這個(gè)程序。
舉個(gè)例子來說?;鸩窆饔螒?,由17跟火柴棍構(gòu)成的 一幅2X3個(gè)小方格的圖案,請(qǐng)你去掉其中的5跟火柴, 使得剩余的火柴棍剛好形成相互獨(dú)立的、兩兩之間沒有 公共邊的3個(gè)小方格。
火柴棍游戲
具體解決問題的思路有許多,比如正向思維、逆向 思維(均舉撲克牌游戲)、混 20、合思維以及靈機(jī)一動(dòng)(三
0+1=1
a.重復(fù)地進(jìn)行相加運(yùn)算
1+2=3
b.本次的和作為下一次
3+=6
相加運(yùn)算的被加數(shù)
a.令s表示被加數(shù)(初始值為
0 ),令I(lǐng)表示加數(shù)(初始
值為1 )
根火柴問題)等等。但對(duì)于算法發(fā)現(xiàn)而言,主要的難點(diǎn) 不在于去解決一個(gè)問題的特定實(shí)例,而是要找出一種適 合一個(gè)問題所有實(shí)例的一般算法。比如要給出加法運(yùn)算 的一般算法,而不是僅僅解決1+1這一個(gè)加法運(yùn)算的特 定實(shí)例。這時(shí),你就會(huì)發(fā)現(xiàn),對(duì)于給定問題,發(fā)現(xiàn)其解 決算法并非是一個(gè)容易的問題。甚至對(duì)于許多問題,根 本就不存在可以加以解決的算法,比如整數(shù)方程解的問 題。
舉例 1:計(jì)算 1 21、+2+...+100(n)
6+4=10 c?加數(shù)有規(guī)律地變化著
10+5=1
5...
4851+99=4950
4950+100=5050
b.進(jìn)行100次加法后結(jié)束,或
者當(dāng)加數(shù)大于100時(shí)結(jié)束
c.S中存放計(jì)算結(jié)果
舉例 1:計(jì)算 1+2+...+100
下面的算法中S表示被加數(shù),也表示累加和,I表示 加數(shù)
步驟 1: S - 0; I - 1
步驟2:若I小于等于100,則轉(zhuǎn)向步驟3;否則,轉(zhuǎn)
向步驟6; \
步驟3: S - S + I;
步驟4: I - I + 1;
步驟5:轉(zhuǎn)向步驟2; \
步驟6: S的值就是計(jì)算結(jié)果,算法結(jié)束。
―推廣該 22、算法,即修改算法中步驟2的100為n,可得
到計(jì)算1+2+???+n的算法。
計(jì)算1+2+…+100的流程圖
S - 0
I -1+1 I
S—S+I
個(gè)—Y*100?
W N
輸出S的值
L £ I
■結(jié)束
計(jì)算1+2+…+n的流程圖
舉例1:計(jì)算1+2+???+n
構(gòu)造算法另一種思想:例如,計(jì)算1+2+...+10 0時(shí) 先計(jì)算 1 + 100, 2+99, ..., 49+52, 50+51,然后用101 X50即可得到運(yùn)算結(jié)果。類推,要計(jì)算1+2+...+n,只 要知道有多少個(gè)n+1,就可以得到計(jì)算結(jié)果。
步驟 1: S — n+1
步驟2:若n 23、是偶數(shù),則S — (S X n) :2;
否則,S — SX ( n_1) :2 + (n + 1) :2
步驟3: S的值就是計(jì)算結(jié)果,算法結(jié)束。
同一個(gè)問題可用不同的方法解決,即用不同算法解 決同一個(gè)問題。因此,就存在一個(gè)算法的比較(分析)和 選擇問題,比較的依據(jù)是算法的效率。
舉例2:判斷閏年問題,給定一個(gè)年號(hào),判斷是否是閏 年。
問題分析:能被4整除,但是不能被100整除的年份 是閏年;能同時(shí)被100和400整除的年份是閏年。
步驟1:令y表示年份,給y一個(gè)年份值;
步驟2:若y能被4整除并且不能被100整除,則轉(zhuǎn)向 步驟5;否則,轉(zhuǎn)向步驟3;
步驟3:若y能被100整 24、除并且能被400整除,則轉(zhuǎn)向 步驟5;否則,轉(zhuǎn)向步驟4;
步驟4:輸出y不是閏年,算法結(jié)束;
步驟5:輸出y是閏年,算法結(jié)束。
判斷閏年的流程圖
開始
用情況語(yǔ)句(選擇結(jié)構(gòu)2)。選擇結(jié)構(gòu)本身不會(huì)增加計(jì)
對(duì)于一個(gè)可以存在解決算法的問題,為了能夠找到
算復(fù)雜性,但是確實(shí)算法實(shí)現(xiàn)中非常重要的表達(dá)方式, 可以有效地解決人們思維中的選擇機(jī)制問題。
a
成立 p 不成立
A B
b
選擇結(jié)構(gòu)1
成立 p 不成立
A B
N-S盒圖表示
情況語(yǔ)句(選擇結(jié)構(gòu)2)的偽碼原語(yǔ),一般定義如下:
解決的算法思路,可以通過逐步求精(stepwise refinement)方法來進(jìn)行 25、。逐步求精就是通過把復(fù)雜問 題不斷分解為子問題,直到分解的子問題能夠直接給出 解決思路為止;然后再逐步將子問題的解決思路一層一 層的整合起來,最終給出總問題的解決思路。問題不斷 分解的過程稱為自上而下的分析方法,將思路不斷整合
switch (變量)(
case ''取值1〃(活動(dòng)1)
case ''取值2〃(活動(dòng)2)
case ''取值n〃(活動(dòng)n) )
的過程稱為自下而上的綜合方法。這也是編制復(fù)雜軟件其中switch、case均為保留詞。
系統(tǒng)最為常用的兩種策略,非常重要。
當(dāng)然,逐步求精不是求解問題的全部,對(duì)于給定問 題如何發(fā)現(xiàn)解決的算法,永遠(yuǎn)是一個(gè)開放的科學(xué)難題, 26、 需要人們不斷地去探索和發(fā)展新的方法。
總之,算法發(fā)現(xiàn)是一項(xiàng)富有挑戰(zhàn)性的技巧性工作, 也是你們聰明才智得以展現(xiàn)的最佳場(chǎng)所。
算法是計(jì)算步驟的有序集合,自然構(gòu)成算法是按照 一定順序排列的語(yǔ)句集合(順序結(jié)構(gòu))。在算法的語(yǔ)句 集合中,反映算法復(fù)雜性的主要體現(xiàn)在構(gòu)成算法的具體 語(yǔ)句結(jié)構(gòu)之中,主要包括選擇結(jié)構(gòu)、迭代結(jié)構(gòu)和遞歸結(jié) 構(gòu),也是分析計(jì)算復(fù)雜性的重點(diǎn)所在。(N-S盒圖表示 是由美國(guó)學(xué)者Nassi和Shneiderman于1973年提出地一 種新的流程圖。)
首先是選擇結(jié)構(gòu),在算法實(shí)現(xiàn)中需要考慮多種可能 情況的不同處理策略時(shí),就會(huì)采用算法的選擇結(jié)構(gòu),具 體表示一般采用條件語(yǔ)句(選擇結(jié)構(gòu)1) 27、,有時(shí)也會(huì)采
a
情況1 v 情況n
情況2
A B C
b
選擇結(jié)構(gòu)2
比如對(duì)于給定的一個(gè)數(shù)據(jù)和一張數(shù)據(jù)表,要確定該 數(shù)據(jù)是否在這張表中,就需要構(gòu)造一個(gè)算法來解決這個(gè) 問題,這樣的算法就是數(shù)據(jù)查找算法。比如查找某個(gè)人 的姓名是否出現(xiàn)在給定的名單中,就屬于這樣一種數(shù)據(jù) 查找問題。一般實(shí)現(xiàn)這一過程的偽碼可以采取選擇結(jié)構(gòu) 來構(gòu)建。具體算法表示如下頁(yè)所示。
Procedure Search (list, TargetValue)
if(list為空)then (返回失敗)
else(
TestEntry—在lis t中選擇第一個(gè)表項(xiàng);
while (TargetVa 28、lue/TestEntry 且
TestEntry不是最后一個(gè)表項(xiàng))
do (TestEntry—在list中選擇下一個(gè)表項(xiàng));
if (TargetValue=TestEntry) then (返回成功) else (返回失敗)
)end if
其次就是迭代結(jié)構(gòu)。在算法的迭代結(jié)構(gòu)中,一組指
精品文檔
令以循環(huán)方式重復(fù)執(zhí)行。當(dāng)然,除了 while語(yǔ)句外(循 環(huán)結(jié)構(gòu)1),也可以采用repeat語(yǔ)句(循環(huán)結(jié)構(gòu)2)來實(shí) 現(xiàn)循環(huán)控制過程。
a
p 不成立 成立
A
b
循環(huán)結(jié)構(gòu)1
當(dāng)?成立
A
N-S盒圖表示
跟while語(yǔ)句不同采用repea t語(yǔ)句來實(shí)現(xiàn)循環(huán)控制 29、 過程,其偽碼原語(yǔ)的使用規(guī)定如下:
repeat (活動(dòng))until (條件)
其中repeat、until都是保留詞。repeat語(yǔ)句的含義如 圖所示,跟while語(yǔ)句不同之處是先執(zhí)行循環(huán)體,然后 進(jìn)行條件檢查。
活動(dòng)
條件 N
Y
repea t語(yǔ)句流程圖
開始
輸入正整數(shù)m和n
r^m被n除的余數(shù)
r不等于0? N
Y
m — n; n — r
r^m被n除的余數(shù)
輸出n的值
結(jié)束
求最大公約數(shù)流程圖
輸入正整數(shù)m和n
r—m被n除的余數(shù)
當(dāng)r不等于0
m — n; n — r
r—m被n除的余數(shù)
輸出n的值
N-S盒圖表示
為了更好地理解 30、這種迭代結(jié)構(gòu),我們?cè)僖陨鲜鰯?shù)據(jù) 查找算法為例,來詳細(xì)分析迭代結(jié)構(gòu)算法的特點(diǎn)。在上 述算法中,為了解決姓名查找問題,我們是從名單首列 開始依次逐一將待查姓名與名單中出現(xiàn)的姓名進(jìn)行比 較,找到了就查找成功;如果名單結(jié)束也沒有找到,則 查找失敗。現(xiàn)在,如果名單是按照字母順序排列的,那 么只須按照字母順序查找即可,不必比較所有的表項(xiàng)。 這樣,實(shí)現(xiàn)這一過程的偽碼可以表示如下頁(yè)所示。
Procedure Search (list, TargetValue)
if (list為空)then (返回失敗)
else(
TestEntry—在lis t中選擇第一個(gè)表項(xiàng);
while (TargetVa 31、lue>TestEntry 且
TestEntry不是最后一個(gè)表項(xiàng))
do (TestEntry—在list中選擇下一個(gè)表項(xiàng));
if (TargetValue=TestEntry)
then (返回成功)
else (返回失?。?
)end if
上述算法是按照字母排列順序來查找的,因此稱其 為順序查找(sequential search)算法,簡(jiǎn)單分析可 知,計(jì)算代價(jià)主要體現(xiàn)在while語(yǔ)句,如果表的長(zhǎng)度為 n的話,那么平均需要計(jì)算n/2計(jì)算步,因此算法的計(jì)算 復(fù)雜性為O (n)。實(shí)際上,該算法中while語(yǔ)句就是 一個(gè)迭代結(jié)構(gòu),而其中的指令“TestEntry—在list中選 32、 擇下一個(gè)表項(xiàng)〃是以重復(fù)的方式被執(zhí)行的。
一般,循環(huán)控制由狀態(tài)初始化、條件檢查和狀態(tài)修 改三個(gè)環(huán)節(jié)部分組成,其中每個(gè)環(huán)節(jié)都決定著循環(huán)的成 功與否。其中狀態(tài)初始化設(shè)置一個(gè)初始狀態(tài),并且這一 狀態(tài)是可以被修改的,直到滿足終止條件;條件檢查是 將當(dāng)前狀態(tài)與終止條件比較,如果符合就終止循環(huán);狀 態(tài)修改就是對(duì)當(dāng)前狀態(tài)進(jìn)行有規(guī)律地改變,使其朝著終 止條件發(fā)展。
最后就是遞歸結(jié)構(gòu)。比循環(huán)結(jié)構(gòu)還要復(fù)雜的算法結(jié) 構(gòu)是遞歸結(jié)構(gòu),也可以實(shí)現(xiàn)重復(fù)計(jì)算任務(wù)。如果說循環(huán) 是通過重復(fù)執(zhí)行同樣一組指令的方式來進(jìn)行的,那么遞 歸則是通過將一組指令當(dāng)作自身的一個(gè)子程序進(jìn)行調(diào) 用來進(jìn)行的。
開始指示代詞量詞形容詞名詞結(jié)束
33、“花哨名詞”遞歸遷移網(wǎng)(RTN)
為了直觀起見,我們下面通過一個(gè)名叫折半查找 (binary search)算法來說明算法中的遞歸結(jié)構(gòu)。對(duì) 于同樣的名字查找問題,除了順序依次比較方法外,為
了提高查找的效率,也可以采取折半查找方法來查找。 通過問題的分析,具體構(gòu)造的算法如下頁(yè)所示。注意, 算法中引入了新的語(yǔ)句Switch case語(yǔ)句,即分情況 語(yǔ)句,屬于條件語(yǔ)句的一種變形形式,其中Switch、 case均為保留詞。
procedure Search(List, TargetValue)
if(list) then (返回失敗)
else(
TestEntry—選擇List的“中 34、間”值; Switch(TargetValue)(
case(TargetValue=TestEntry)(返 回成功) case(TargetValue>TestEntry)(
BList—位于 TestEntry 前半部分 List; 返回? rocedure Search(BList,
TargetValue)的返回值)
case(TargetValue 35、身調(diào)用的情況,這便是 遞歸結(jié)構(gòu)。遞歸過程的控制主要是通過過程調(diào)用參數(shù)的 變化來進(jìn)行的。在上述算法中這樣的參數(shù)就是列表本身。 如果追蹤某個(gè)遞歸過程,那么就會(huì)發(fā)現(xiàn),其計(jì)算過程是 一層一層遞進(jìn)的,然后再一層一層返回。對(duì)于遞歸結(jié)構(gòu) 而言,在動(dòng)態(tài)執(zhí)行過程中,遞進(jìn)的最大層數(shù)就稱為該遞 歸結(jié)果的遞歸深度。對(duì)上述折半算法分析可知,遞歸算 法的計(jì)算復(fù)雜性與遞歸深度密切關(guān)聯(lián),如果表的長(zhǎng)度為 n的話,那么平均需要計(jì)算的遞歸深度為log2n,因此算 法的計(jì)算復(fù)雜性為O (log2n)。顯然,折半查找算法的 效率要高于順序查找算法的效率。
另一個(gè)需要運(yùn)用遞歸結(jié)構(gòu)來設(shè)計(jì)求解算法的就是 著名的漢諾塔問題:將A柱子上的n個(gè) 36、圓盤借助于B柱子 移到C柱子上去,問如何移動(dòng)圓盤?約束規(guī)則是(1)每 次只能移動(dòng)一張圓盤;(2)圓盤只能在這三個(gè)柱上存 放;(3)大盤不能壓在小盤上面。
A(源) B(輔助) 。(目的)
漢諾塔問題示意圖
(0) (1)
ABC ABC
初始狀態(tài)借 助C,將A上方的三個(gè)盤移
到B
精品文檔
(2) (3)
ABC ABC
將A上的最后一個(gè)盤直接移到C借助A,將B上的三個(gè)盤 移到C
漢諾塔問題遞歸解法思路(設(shè)n=4)
根據(jù)上面的分析,對(duì)于任意n,求解的方法是:將入 柱子上的n個(gè)圓盤分成兩部分:1個(gè)園盤和n-1個(gè)園盤, 然后按照如下移動(dòng)園盤步驟:
第一步:將A柱子的上面n 37、-1個(gè)園盤移動(dòng)到B柱子上面; 第二步:將A柱子上剩下的那個(gè)園盤移動(dòng)到C柱子上面; 第三步:將B柱子上的n-1個(gè)園盤移動(dòng)到C柱子上面。
第一步:將A柱子的上面n-1個(gè)園盤移動(dòng)到B柱子上面 n-1
1
A(源) B(輔助) C(目的)
漢諾塔問題示意圖
n-1
1
A(源) B(輔助) C(目的)
n-1
1
AB C
第二步:將A柱子上的1個(gè)園盤移動(dòng)到C柱子上
n-1
1 ABC n-1
1
ABC
第三步:將B柱子上的n-1個(gè)園盤移動(dòng)到C柱子上
n-1
1
ABC
n-1
1
ABC
這樣,剩下的問題就是n-1個(gè)盤子的漢諾塔問題, 可以通過遞歸來求 38、解,直道n=1為止。因此,整個(gè)遞歸 算法如下:
procedure hanoi(int n, char A ,char B,char C) if(n=1) then printf("%c-->%c\n", A, C); //輸出 else (
精品文檔
hanoi(n-1,A,C,B); //左向遞歸
printf("%c-->%c\n", A, C); //輸出
hanoi(n-1, B, A, C); //右向遞歸
)
其中“左向遞歸”是借助C,將A柱上方的n-1個(gè)盤 子移到B柱;“右向遞歸”則是借助入,將B柱上n-1個(gè)盤 子移到C柱。
1,A,B,C
A C
Hano 39、i(3,A,B,C)
左向遞歸 輸 出 右向遞歸
2,A,C,B A C 2,B,A,C
④
A B 1,C,A,B 1,B,C,A B C
② ⑥
CB BA
1,A,B,C
AC
①
③ ⑤
⑦
本講介紹了智能計(jì)算中最為核心,也是最為基礎(chǔ)的 內(nèi)容,即算法設(shè)計(jì)。人類的智能是否都可以用算法來表 示,這是一個(gè)開放問題,我們不得而知。但是起碼目前 來說,算法是實(shí)現(xiàn)機(jī)器智能的唯一手段,也是最為重要 的手段。因此,我們必須對(duì)這里介紹的有關(guān)算法的概念、 結(jié)構(gòu)、效率、以及構(gòu)造原語(yǔ)、偽碼及原則有基本的了解, 并掌握其中的核心內(nèi)容與思想,為智能系統(tǒng)的構(gòu)建,奠 定基礎(chǔ)。
練習(xí)題
40、
1、 對(duì)于給定的一個(gè)由0—9十個(gè)數(shù)字組成的數(shù)列,請(qǐng)?jiān)O(shè) 計(jì)一個(gè)算法,能夠?qū)υ摂?shù)列作重排,使得結(jié)果數(shù)列剛好 比給定的數(shù)列大。
2、 如何構(gòu)造一個(gè)能夠計(jì)算一個(gè)字符串在另一個(gè)字符串 中出現(xiàn)次數(shù)的算法,請(qǐng)用偽碼來表示所給出的算法,并 分析算法的計(jì)算復(fù)雜性。
3、 設(shè)有兩個(gè)正整數(shù)口和n,如何求其最大公約數(shù)?請(qǐng)使 用遞歸結(jié)構(gòu),設(shè)計(jì)一個(gè)能夠解決該問題的算法。
算法的運(yùn)行圖解(設(shè)n=3)
對(duì)于遞歸算法,保證遞歸過程終止的條件也是需要 考慮的問題。比如上述折半查找算法中表列為空或者找 到目標(biāo),可以保證遞歸過程的終止。而在漢諾塔問題中, 盤子數(shù)降到1,算法也會(huì)終止。與循環(huán)終止條件的顯式 表示不同, 41、遞歸終止條件往往是隱含表示的,因此在設(shè) 計(jì)遞歸算法時(shí)需要格外注意。因?yàn)?,有時(shí)不恰當(dāng)?shù)倪f歸 也會(huì)產(chǎn)生悖論,使計(jì)算無(wú)法終止。
最后,我們強(qiáng)調(diào)指出,從理論上講,所有算法的結(jié) 構(gòu),都可以看作是并化解為遞歸結(jié)構(gòu),關(guān)鍵在于遞歸的 深度。其中作為計(jì)算理論的之一遞歸函數(shù)論,就是以遞 歸的思想,建立起完整的計(jì)算理論模型的。這就是為什 么,我們?cè)谒惴?gòu)造的原語(yǔ)介紹中,一開始就將各種算 法步驟的描述方式為遞歸語(yǔ)義結(jié)構(gòu)的原因所在。
在算法中,遞歸的思想非常重要,如果說對(duì)于計(jì)算 學(xué)科而言,玩的就是算法,那么對(duì)于算法而言,玩的就 是遞歸。從更為廣泛的視野講,遞歸也是大自然的一種 普遍現(xiàn)象,從自然界的分形,到語(yǔ)言、音樂、繪畫中的 嵌套結(jié)構(gòu),無(wú)不體現(xiàn)著遞歸的本性。正是從這個(gè)意義上 講,通過遞歸,算法的方法可以被應(yīng)用到自然與人文的 各個(gè)方面,特別是可以應(yīng)用到解決我們的智能機(jī)智仿造 之中。
第03講小結(jié)
- 溫馨提示:
1: 本站所有資源如無(wú)特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 火力發(fā)電廠各設(shè)備的主要作用大全
- 3.高壓電工考試判斷練習(xí)題含答案
- 企業(yè)電氣防爆知識(shí)
- 13 低壓電工電工作業(yè)模擬考試題庫(kù)試卷含答案
- 電氣設(shè)備維修的十項(xiàng)原則
- 2.電氣電纜與直流模擬考試復(fù)習(xí)題含答案
- 電氣節(jié)能措施總結(jié)
- 2.電氣電機(jī)(一)模擬考試復(fù)習(xí)題含答案
- 接地電阻測(cè)量原理與測(cè)量方法
- 3.高壓電工作業(yè)模擬考試題庫(kù)試卷含答案
- 礦山維修電工安全技術(shù)操作規(guī)程
- 電工基礎(chǔ)口訣總結(jié)
- 3.某電廠值長(zhǎng)面試題含答案解析
- 電工基礎(chǔ)知識(shí)順口溜
- 配電系統(tǒng)詳解