91欧美在线免费观看,漂亮的人妻中文字幕,国产精品免费在线观看视频,男女一起插插插视频,四虎国产精品久久久久,人妻精品有码一区二区三区,亚洲 欧美 你懂的,亚洲制服一区二区三区在线,高中女厕偷拍一区二区三区

數(shù)學(xué)技術(shù)之算法概述篇(8)

6.算法分類及其簡(jiǎn)介

對(duì)數(shù)學(xué)技術(shù)中的方法和算法進(jìn)行合理、有效與清晰的分類，很重要，但并不容易，也不簡(jiǎn)單，研究得到的結(jié)果甚多，因此也就有各種各樣的把方法和算法進(jìn)行分類的標(biāo)準(zhǔn)及分類結(jié)果。如把算法按結(jié)構(gòu)類型分為基本算法、數(shù)據(jù)結(jié)構(gòu)算法、數(shù)論與代數(shù)算法、計(jì)算幾何算法、圖論算法、動(dòng)態(tài)規(guī)劃以及數(shù)值分析算法、加密算法、排序算法、檢索算法、隨機(jī)化算法、并行算法等等。再如把算法按計(jì)算結(jié)果分為兩類：確定性算法，計(jì)算結(jié)果常取決于輸入值；非確定算法，對(duì)于一個(gè)或一組給定的輸入值，算法的結(jié)果并不是唯一的或確定的。又如把算法按計(jì)算類型分為數(shù)值型算法、非數(shù)值型算法和混合型算法三種：對(duì)一個(gè)數(shù)學(xué)問(wèn)題求數(shù)值解，屬數(shù)值型算法，如方程求根、矩陣計(jì)算、線代數(shù)方程組求解、數(shù)值積分、微分方程求解等；非數(shù)值型算法也不少，如數(shù)據(jù)排序算法、檢索查詢算法等。非數(shù)值型算法應(yīng)用十分廣泛，如圖書檢索、人事管理、文字處理、模式匹配等；混合型算法更多。實(shí)際上，解決實(shí)際問(wèn)題中利用的算法，既有數(shù)值型算法、又有非數(shù)值型算法，多是混合的。
在計(jì)算機(jī)程序設(shè)計(jì)中，數(shù)據(jù)形式的表示主要有兩大類：數(shù)值型和字符型(非數(shù)值型)。數(shù)值型數(shù)據(jù)是指定義成數(shù)值形式的數(shù)據(jù)。這種數(shù)據(jù)可以直接進(jìn)行加、減、乘、除等運(yùn)算，運(yùn)算的結(jié)果還是數(shù)值型的，所表達(dá)的是實(shí)數(shù)，具有計(jì)算上的意義。另一種數(shù)據(jù)形式為非數(shù)值型的數(shù)據(jù)，如字符型數(shù)據(jù)，所表達(dá)的是字符，如‘A’，‘B’，‘C‘等等，具有存儲(chǔ)意義。
在計(jì)算機(jī)中可以識(shí)別的字符，一般都對(duì)應(yīng)于一個(gè)ASII碼，ASII碼為數(shù)值型的數(shù)據(jù)。ASII碼值的改變，對(duì)應(yīng)的字符也會(huì)改變。所以，非數(shù)值型的數(shù)據(jù)，本質(zhì)上也是數(shù)值型的數(shù)據(jù)。為了接近人的思維習(xí)慣，方便程序的編寫，計(jì)算機(jī)高級(jí)語(yǔ)言，劃分了數(shù)據(jù)的類型：
數(shù)值型數(shù)據(jù)有：實(shí)型數(shù)（含整型數(shù)，定點(diǎn)數(shù)，浮點(diǎn)數(shù)，單精度和雙精度類數(shù)等）和復(fù)型數(shù)兩大類；非數(shù)值型數(shù)據(jù)類型更多，有：字符型，布爾型，字符串型等。
計(jì)算機(jī)上，可用的數(shù)值型算法很多。在求解方程的算法中，常用的算法之一是迭代法，也叫逐次逼近法。迭代法的計(jì)算比較簡(jiǎn)單，也比較容易在計(jì)算機(jī)上編程實(shí)現(xiàn)。求方程組的近似解要選擇適當(dāng)?shù)牡胶统踔?，使得收斂速度快、誤差小。在線代數(shù)方程組的解法中，常用的有塞德?tīng)柕?、共軛斜量法、超松弛迭代法等?
在計(jì)算方法中，數(shù)值逼近也是常用的基本算法，就是用簡(jiǎn)單的函數(shù)、在誤差允許范圍內(nèi)、代替比較復(fù)雜的函數(shù)，或者代替不能用解析表達(dá)式表示的函數(shù)。
微分方程的數(shù)值解法也是近似算法。常微分方程的算法有歐拉算法、龍格-庫(kù)塔方法、阿塔姆斯方法。偏微分方程的初值問(wèn)題或邊值問(wèn)題，目前常用的是有限差分法、有限元素法等。有限差分法的基本思想是用離散的、只含有限個(gè)未知數(shù)的差分方程去代替連續(xù)變量的微分方程和定解條件，求出差分方程的解作為所求偏微分方程的近似解。
蒙特卡羅方法，又稱統(tǒng)計(jì)模擬方法，是一類基于“隨機(jī)數(shù)”的計(jì)算方法，常用于高維非線性問(wèn)題的計(jì)算。
算法與計(jì)算機(jī)的發(fā)展相輔相成，相互促進(jìn)。大量數(shù)值計(jì)算的需要，促使計(jì)算機(jī)體系結(jié)構(gòu)及性能不斷更新，而計(jì)算機(jī)的發(fā)展又推動(dòng)著算法的發(fā)展，如并行機(jī)和并行算法就是其中的一例。為適應(yīng)現(xiàn)代計(jì)算機(jī)的飛速發(fā)展，對(duì)算法提出了新的要求，對(duì)原有算法提出了重新評(píng)價(jià)、篩選、改造和創(chuàng)新。與此同時(shí)，也涌現(xiàn)了許多新概念、新方法，它們技巧性強(qiáng)，在時(shí)間復(fù)雜度、空間復(fù)雜度和計(jì)算精度等方面各占一定優(yōu)勢(shì)，應(yīng)用廣泛，效果顯著，如快速傅立葉變換算法FFT等。
算法和不同學(xué)科結(jié)合，出現(xiàn)了不少具有學(xué)科特點(diǎn)的算法，如計(jì)算力學(xué)、計(jì)算物理、計(jì)算化學(xué)、計(jì)算經(jīng)濟(jì)學(xué)等。
因此如何簡(jiǎn)單、方便、有效地介紹算法就成為一個(gè)問(wèn)題。下面擬以三個(gè)方面向大家介紹算法：① 按照算法思路分類進(jìn)行介紹，② 按常用算法逐一進(jìn)行介紹，③ ？按算法應(yīng)用領(lǐng)域進(jìn)行解釋，供參考。
下面按算法的基本思路進(jìn)行分類并對(duì)其進(jìn)行一些簡(jiǎn)單介紹。
1？迭代法
迭代法是用計(jì)算機(jī)解決問(wèn)題的一種基本方法。它利用計(jì)算機(jī)運(yùn)算速度快、適合做重復(fù)性操作的特點(diǎn)，讓計(jì)算機(jī)對(duì)一組指令（或一定步驟）進(jìn)行重復(fù)執(zhí)行，在每次執(zhí)行這組指令（或這些步驟）時(shí)，都從變量的原值推出它的一個(gè)新值。迭代法常用于求方程或方程組根的近似求解。
2？遞推法
遞推法是根據(jù)具體問(wèn)題，建立遞推關(guān)系，再通過(guò)遞推關(guān)系求解的方法。其中遞推關(guān)系是表示關(guān)于正整數(shù)參變量的一類特殊關(guān)系，從給定的初值出發(fā)，通過(guò)這種關(guān)系一步一步地通過(guò)遞推獲得所需結(jié)果。這種遞推通常采用循環(huán)迭代的方法，如循環(huán)累乘、循環(huán)累加等。
3？遞歸法
程序調(diào)用自身的編程技巧稱為遞歸（recursion）。一個(gè)過(guò)程或函數(shù)在其定義或說(shuō)明中又直接或間接調(diào)用自身的一種方法，它通常把一個(gè)大型復(fù)雜的問(wèn)題層層轉(zhuǎn)化為一個(gè)與原問(wèn)題相似的規(guī)模較小的問(wèn)題來(lái)求解，遞歸策略只需少量的程序就可描述出解題過(guò)程所需要的多次重復(fù)計(jì)算，大大地減少了程序的代碼量。
遞歸算法解題通常很簡(jiǎn)潔，但是由于遞歸引起一系列的函數(shù)調(diào)用，并且可能會(huì)有一系列的重復(fù)計(jì)算，所以遞歸算法的執(zhí)行效率相對(duì)較低。一般來(lái)說(shuō)，遞歸要有邊界條件、遞歸前進(jìn)段和遞歸返回段。當(dāng)邊界條件不滿足時(shí)，遞歸前進(jìn)；當(dāng)邊界條件滿足時(shí)，遞歸返回。
4？窮舉法
窮舉法是編程中常用到的一種方法，通常在找不到解決問(wèn)題的規(guī)律時(shí)對(duì)可能是解的眾多候選解按某種順序進(jìn)行逐一枚舉和檢驗(yàn)，并從中找出那些符合要求的候選解作為問(wèn)題的解。
5？回溯法
回溯法是一種選優(yōu)的搜索方法，按照選優(yōu)的條件向前搜索，以達(dá)到目標(biāo)，但是當(dāng)搜索到某一步的時(shí)候，發(fā)現(xiàn)原先的選擇并不優(yōu)或者達(dá)不到目標(biāo)，就退回一步重新選擇，這種走不通就退回再走的技術(shù)就是回溯法。
6？貪心法
貪心法總是作出在當(dāng)前看來(lái)最好的選擇。也就是說(shuō)貪心算法并不從整體最優(yōu)考慮，它所作出的選擇只是在某種意義上的局部最優(yōu)選擇。
實(shí)現(xiàn)該算法的過(guò)程：1)？從問(wèn)題的某一初始解出發(fā)；2)？當(dāng)能朝給定總目標(biāo)前進(jìn)一步執(zhí)行；3)？求出可行解的一個(gè)解元素；4)？由所有解元素組合成問(wèn)題的一個(gè)可行解。
7 分支界限法
分枝界限法是一個(gè)用途十分廣泛的算法，運(yùn)用這種算法的技巧性很強(qiáng)，不同類型的問(wèn)題解法也各不相同。
分支界限法的基本思想是對(duì)有約束條件的最優(yōu)化問(wèn)題的所有可行解（數(shù)目有限）空間進(jìn)行搜索。該算法在具體執(zhí)行時(shí)，把全部可行的解空間不斷分割為越來(lái)越小的子集（稱為分支），并為每個(gè)子集內(nèi)的解的值計(jì)算一個(gè)下界或上界（稱為定界）。在每次分支后，對(duì)凡是界限超出已知可行解值那些子集不再做進(jìn)一步分支，這樣，解的許多子集（即搜索樹上的許多結(jié)點(diǎn)）就可以不予考慮了，從而縮小了搜索范圍。這一過(guò)程一直進(jìn)行到找出可行解為止，該可行解的值不大于任何子集的界限。因此這種算法一般可以求得最優(yōu)解。
與貪心算法一樣，這種方法也是用來(lái)為組合優(yōu)化問(wèn)題設(shè)計(jì)求解算法的，所不同的是它在問(wèn)題的整個(gè)可能解空間搜索，所設(shè)計(jì)出來(lái)的算法雖其時(shí)間復(fù)雜度比貪婪算法高，但它的優(yōu)點(diǎn)是與窮舉法類似，都能保證求出問(wèn)題的最佳解，而且這種方法不是盲目的窮舉搜索，而是在搜索過(guò)程中通過(guò)限界，可以中途停止對(duì)某些不可能得到最優(yōu)解的子空間進(jìn)一步搜索（類似于人工智能中的剪枝），故它比窮舉法效率更高。
8 分治法
分治法就是把一個(gè)復(fù)雜的問(wèn)題分成兩個(gè)或更多的相同或相似的子問(wèn)題，再把子問(wèn)題分成更小的子問(wèn)題……直到最后子問(wèn)題可以簡(jiǎn)單的直接求解，原問(wèn)題的解就是諸子問(wèn)題的解的合并。分治法的基本步驟：
1）分解：將原問(wèn)題分解為若干個(gè)規(guī)模較小，相互獨(dú)立，與原問(wèn)題形式相同的子問(wèn)題；
2）解決：若子問(wèn)題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個(gè)子問(wèn)題；
3）合并：將各個(gè)子問(wèn)題的解合并為原問(wèn)題的解。
分治法的合并步驟是算法的關(guān)鍵所在。有些問(wèn)題的合并方法比較明顯，有些問(wèn)題合并方法比較復(fù)雜，或者是有多種合并方案；或者是合并方案不明顯。究竟應(yīng)該怎樣合并，沒(méi)有統(tǒng)一的模式，需要具體問(wèn)題具體分析。
9 動(dòng)態(tài)規(guī)劃法
動(dòng)態(tài)規(guī)劃是一種在數(shù)學(xué)和計(jì)算機(jī)科學(xué)中使用的、用于求解包含重疊子問(wèn)題的最優(yōu)化問(wèn)題的方法。其基本思想是，將原問(wèn)題分解為相似的子問(wèn)題，在求解的過(guò)程中通過(guò)子問(wèn)題的解求出原問(wèn)題的解。動(dòng)態(tài)規(guī)劃的思想是多種算法的基礎(chǔ)，被廣泛應(yīng)用于計(jì)算機(jī)科學(xué)和工程領(lǐng)域。
動(dòng)態(tài)規(guī)劃程序設(shè)計(jì)是對(duì)解最優(yōu)化問(wèn)題的一種途徑、一種方法，而不是一種特殊算法。不象前面所述的那些搜索或數(shù)值計(jì)算那樣，具有一個(gè)標(biāo)準(zhǔn)的數(shù)學(xué)表達(dá)式和明確清晰的解題方法。動(dòng)態(tài)規(guī)劃程序設(shè)計(jì)往往是針對(duì)一種最優(yōu)化問(wèn)題，由于各種問(wèn)題的性質(zhì)不同，確定最優(yōu)解的條件也互不相同，因而動(dòng)態(tài)規(guī)劃的設(shè)計(jì)方法對(duì)不同的問(wèn)題，有各具特色的解題方法，而不存在一種萬(wàn)能的動(dòng)態(tài)規(guī)劃算法，可以解決各類最優(yōu)化問(wèn)題。因此讀者在學(xué)習(xí)時(shí)，除了要對(duì)基本概念和方法正確理解外，必須具體問(wèn)題具體分析處理，以豐富的想象力去建立模型，用創(chuàng)造性的技巧去求解。