演算法綜述

⑴ 免疫克隆演算法綜述

自己用網路找

⑵ floyd-warshall演算法的演算法概述

單獨一條邊的路徑也不一定是最佳路徑。 從任意一條單邊路徑開始。所有兩點之間的距離是邊的權的和，(如果兩點之間沒有邊相連, 則為無窮大）。 對於每一對頂點 u 和 v，看看是否存在一個頂點 w 使得從 u 到 w 再到 v 比己知的路徑更短。如果是更新它。 不可思議的是，只要按排適當，就能得到結果。// dist(i,j) 為從節點i到節點j的最短距離
For i←1to n do
For j←1to n do
dist(i,j) = weight(i,j)
For k←1to n do// k為「媒介節點」{一定要先枚舉媒介節點}
For i←1to n do
For j←1to n do
if(dist(i,k) + dist(k,j) < dist(i,j))then// 是否是更短的路徑？
dist(i,j) = dist(i,k) + dist(k,j)
這個演算法的效率是O(V^3)。它需要鄰接矩陣來儲存圖。
這個演算法很容易實現，只要幾行。
即使問題是求單源最短路徑，還是推薦使用這個演算法，如果時間和空間允許(只要有放的下鄰接矩陣的空間，時間上就沒問題)。
計算每一對頂點間的最短路徑（floyd演算法）

⑶ 哈夫曼演算法的概述

1.初始化： 根據給定的n個權值{w1,w2,…wn}構成n棵二叉樹的集合F={T1,T2,..,Tn}，其中每棵二叉樹Ti中只有一個帶權wi的根結點，左右子樹均空。
2. 找最小樹：在F中選擇兩棵根結點權值最小的樹作為左右子樹構造一棵新的二叉樹，且至新的二叉樹的根結點的權值為其左右子樹上根結點的權值之和。
3. 刪除與加入：在F中刪除這兩棵樹，並將新的二叉樹加入F中。
4. 判斷：重復前兩步（2和3），直到F中只含有一棵樹為止。該樹即為哈夫曼樹

⑷ 陰影貼圖的演算法綜述

對於陰影場景的渲染需要兩個步驟來完成。第一步是產生陰影圖本身，第二步是將陰影圖應用到場景中。根據實現方式以及光源數目的不同，陰影場景渲染過程可能需要兩個或者更多的繪制過程。 第一步是從光源的視角渲染場景。對於點光源來說，視場是一個視角足夠寬的透視投影。對於象太陽光這樣的定向光來說，需要使用正投影。
根據這個渲染結果提取、保存深度緩沖。因為只與深度信息相關，因此通常避免更改顏色緩沖區，並且不對光線及紋理進行計算以及節省時間。這個深度圖經常在圖形卡的內存中保存為紋理。
一旦場景中的光源或者物體發生變動，就必須重新更新深度圖，但是在其它場合下也可以重復使用深度圖，例如只有照相機運動的場合。如果場景中有多個光源，必須針對每個光源分別生成深度圖。
在許多實現方法中為了節省重繪深度圖所花費的時間，可以只對場景中的一部分物體進行渲染來生成陰影圖。另外，為了解決當前深度值與下一步繪制的表面深度太接近產生的深度沖突問題（Z-fighting），也可能在陰影圖渲染過程中對物體的照明深度添加一個偏移。實現這種效果的另外一種可選方法是裁剪掉前面的物體，僅對後面的物體進行渲染生成陰影圖。 第二步就是使用陰影圖按照普通的透視投影繪制場景。這個過程分為三個主要的部分，第一是找出物體在光照視景中的坐標，第二是將這個坐標與深度圖中的對應值進行比較，最後就是根據處於陰影或者光照下的位置將物體繪制出來。
光照空間坐標
為了將物體點與深度圖進行比較，物體在場景坐標系中的位置必須要轉換到光照空間中的對應位置，這個變換可以用矩陣乘法實現。物體在屏幕上的位置可以通過普通的坐標變換確定，但是必須要生成第二套坐標來定位物體在光照空間中的位置。
將世界坐標系變換到光照空間坐標系的變換矩陣與第一步中用於渲染陰影圖的變換矩陣相同，在OpenGL中它是模型視圖與投影矩陣之積。這樣就生成一組齊次坐標，如果可見的話經過透視除法（perspective division）轉換成歸一化設備坐標，每個分量（x、y、z）都落在 -1 到 1 之間。有許多的實現方法要進行另外的縮放及偏移矩陣乘法將 -1 到 1 之間的數值轉換到深度圖或紋理圖中更常用的 0 到 1 之間的數值。這個縮放過程也可以在透視除法之前完成
如果使用shader或者其它的圖形硬體擴展完成這項工作的話，那麼通常在頂點級進行這樣的變換，生成的數值在其它定點之間進行插值，然後傳遞到片斷處理的部分。

⑸ 智能演算法的智能演算法概述

智能優化演算法要解決的一般是最優化問題。最優化問題可以分為（1）求解一個函數中，使得函數值最小的自變數取值的函數優化問題和（2）在一個解空間裡面，尋找最優解，使目標函數值最小的組合優化問題。典型的組合優化問題有：旅行商問題（Traveling Salesman Problem，TSP），加工調度問題（Scheling Problem），0－1背包問題（Knapsack Problem），以及裝箱問題（Bin Packing Problem）等。
優化演算法有很多，經典演算法包括：有線性規劃，動態規劃等；改進型局部搜索演算法包括爬山法，最速下降法等，本文介紹的模擬退火、遺傳演算法以及禁忌搜索稱作指導性搜索法。而神經網路，混沌搜索則屬於系統動態演化方法。
優化思想裡面經常提到鄰域函數，它的作用是指出如何由當前解得到一個（組）新解。其具體實現方式要根據具體問題分析來定。
一般而言，局部搜索就是基於貪婪思想利用鄰域函數進行搜索，若找到一個比現有值更優的解就棄前者而取後者。但是，它一般只可以得到「局部極小解」，就是說，可能這只兔子登「登泰山而小天下」，但是卻沒有找到珠穆朗瑪峰。而模擬退火，遺傳演算法，禁忌搜索，神經網路等從不同的角度和策略實現了改進，取得較好的「全局最小解」。

⑹ 演算法分析與設計這門課程第一章演算法概述的知識點有哪些

演算法分析與設計這門課第一章演算法概述的知識點包含章節導引,內容講解,課後練習,。

⑺ 道格拉斯-普克演算法的概述說明

道格拉斯-普克演算法 (Douglas–Peucker algorithm，亦稱為拉默-道格拉斯-普克演算法、迭代適應點演算法、分裂與合並演算法)是將曲線近似表示為一系列點，並減少點的數量的一種演算法。該演算法的原始類型分別由烏爾斯·拉默（Urs Ramer）於1972年以及大衛·道格拉斯（David Douglas）和托馬斯·普克（Thomas Peucker）於1973年提出，並在之後的數十年中由其他學者予以完善。
演算法的基本思路是:對每一條曲線的首末點虛連一條直線,求所有點與直線的距離,並找出最大距離值dmax ,用dmax與限差D相比:若dmax <D,這條曲線上的中間點全部捨去;若dmax ≥D,保留dmax 對應的坐標點,並以該點為界,把曲線分為兩部分,對這兩部分重復使用該方法。

⑻ Lanczos演算法的概述

Lanczos演算法實際上是Arnoldi演算法對於對稱矩陣的特殊形式，可應用於對稱矩陣線性方程組求解的Krylov子空間方法以及對稱矩陣的特徵值問題。