組合算法

組合算法單純形法

單純形法是G.B.Dantzig在1947年提出的一種線性規(guī)劃算法，他本人以及其他學(xué)者后來又提出多種形式的變形和改進(jìn)。實踐表明，單純形法及其變形和改進(jìn)是非常行之有效的，在市場上已經(jīng)形成許多可以有效解央大型線性規(guī)劃問題的軟件包。線性規(guī)劃研究線性目標(biāo)函數(shù)在一組線性等式與線性不等式約束下的極值問題。這本來是連續(xù)問題，Dantzig發(fā)現(xiàn)線性規(guī)劃問題的可行解集(即滿足約束條件的點的全體)是一個超多面體。 如果它的最優(yōu)解存在，那么最優(yōu)解一定可以在這個超多面體的某個頂點取到。由于超多面體的頂點只有有限個，從而使線性規(guī)劃成為一個組合優(yōu)化問題。單純形法是按照一定的規(guī)劃，從可行解集的一個頂點轉(zhuǎn)移到另一個頂點，使得目標(biāo)函數(shù)的值不斷地得到改進(jìn)，最后達(dá)到最優(yōu)。盡管單純形法一直使用得很好，但在最壞情況下它需要指數(shù)運(yùn)行時間，從而使線性規(guī)劃問題是否屬于P類一度成為人們關(guān)心的問題。1979年前一位蘇聯(lián)數(shù)學(xué)家提出一個多項式時間的線性規(guī)劃算法——橢球算法， 從而解決了這個問題。1984年印度數(shù)學(xué)家N.Karmarkar又提出一個新的更好的多項式時間算法——投影算法。

組合算法排序和檢索

將給定的元素序列按照某種順序關(guān)系重新排列成有序序列稱作排序。例如將n個數(shù)組成的序列按照從小到大的順序重新排列；將n個英語單詞組成的序列按照字典順序重新排列。在給定的集合中查找某個特定的元素稱作檢索。例如從給定的n個數(shù)中找到最大的數(shù)。排序和檢索算法已經(jīng)成為數(shù)據(jù)結(jié)構(gòu)中不可缺少的部分，是計算機(jī)科學(xué)技術(shù)中最基本、使用最頻繁的算法。正因為如此，它們也是研究得最細(xì)致的一類組合算法(參見排序算法)。

組合算法圖與網(wǎng)絡(luò)優(yōu)化算法

圖與網(wǎng)絡(luò)優(yōu)化算法是組合算法中內(nèi)容最豐富的部分。圖論中的計算問題包括圖的搜索路徑問題、連通性問題可平面性檢驗、著色問題、網(wǎng)絡(luò)優(yōu)化等。圖論中的著名算法有求最小生成樹的Kruskal算法、求最短路的Dijkstra算法和Floyd算法、求二部圖最大匹配(指派問題)的匈牙利算法、求一般圖最大匹配的Edmonds"花”算法、求網(wǎng)絡(luò)最大流和最小割的標(biāo)號法等。

組合算法貪心法與擬陣

貪心法是求解關(guān)于獨立系統(tǒng)組合優(yōu)化問題的一種簡單算法，求最小生成樹的Kruskal算法就是一種貪心法。但是，貪心法并不總能找到最優(yōu)獨立集，貪心法能求得最優(yōu)獨立集的充分必要條件是L為一個擬陣。事實上，求最大生成樹是關(guān)于擬陣的組合優(yōu)化問題，而二部圖的所有匹配構(gòu)成的獨立系統(tǒng)U不是擬陣。

組合算法窮舉搜索

組合算法要解決的問題只有有限種可能，在沒有更好辦法時總可以用窮舉搜索的辦法來解決，即逐個檢查所有可能的情況。當(dāng)情況較多時這樣做是很費(fèi)時的。實際上，并不需要機(jī)械地檢查每一種情況，常常有可能提前判斷出某些情況不可能取到最優(yōu)解，從而可以提前舍棄這些情況。這樣使“隱含地”檢查了所有情況，既減少了搜索量，又保證不漏掉最優(yōu)解。參見回溯法。

組合算法分支限界法

分支限界法是一種用于求解組合優(yōu)化問題的排除非解的搜索方法。它的基本思想是：把問題分成若干個子問題，估計子問題的目標(biāo)函數(shù)值的上界或下界。對于最大值問題，子問題的下界也是原問題的下界。 當(dāng)子問題的上界小于原問題的下界時，不可能在這個子問題中取得原問題的最優(yōu)解，舍去這個子問題。否則將這個子問題再劃分成若干更小的子問題，重復(fù)上述過程，直到?jīng)]有需要檢查的子問題為止。

其他組合算法還有動態(tài)規(guī)劃，快速傳里葉變換等 。2100433B

組合算法指計算對象是離散的、有限的數(shù)學(xué)結(jié)構(gòu)的組合學(xué)問題的算法。組合算法的用途十分廣泛。從方法學(xué)的角度，組合算法包括算法設(shè)計和算法分析兩個方面，關(guān)于算法設(shè)計，已經(jīng)總結(jié)出若干帶有普遍意義的方法和技術(shù)，包括動態(tài)規(guī)劃、回溯法、分枝限界法、分治法、貪心法等。盡管如此，組合算法的設(shè)計仍然是一門藝術(shù)需要高度的技巧和靈感。算法分析的任務(wù)是分析算法的優(yōu)劣，主要是討論算法的時間復(fù)雜性和空間復(fù)雜性。它的理論基礎(chǔ)是組合分析，包括計數(shù)和枚舉。計算復(fù)雜性理論，特別是NP完全性理論，與組合算法是緊密相關(guān)的。NP完全性概念的提出，正是為了刻畫包括旅行商問題、圖著色問題、整數(shù)規(guī)劃等在內(nèi)的一大批組合問題的計算難度。計算復(fù)雜性理論研究算法在時間和空間限制下的能力以及問題的難度，使組合算法的研究有了更加清晰的框架，將組合算法的研究提高到一個新水平 。

第1章 緒論

1.1 組合導(dǎo)航概述

1.1.1 組合導(dǎo)航基本概念

1.1.2 組合導(dǎo)航系統(tǒng)發(fā)展概況

1.2 濾波理論的研究概況

1.2.1 濾波算法的基本知識

1.2.2 線性濾波算法

1.2.3 非線性濾波算法

1.3 組合導(dǎo)航非線性濾波算法的應(yīng)用現(xiàn)狀

第2章 卡爾曼濾波及擴(kuò)展卡爾曼濾波

2.1 卡爾曼濾波的性質(zhì)

2.2 離散卡爾曼濾波算法

2.3 連續(xù)卡爾曼濾波算法

2.3.1 過程噪聲

2.3.2 量測噪聲

2.3.3 連續(xù)卡爾曼濾波推導(dǎo)

2.4 改進(jìn)的卡爾曼濾波算法

2.4.1 魯棒卡爾曼濾波

2.4.2 交互式多模型卡爾曼濾波

2.4.3 Sage-Husa卡爾曼濾波

2.5 擴(kuò)展卡爾曼濾波

2.5.1 線性化方法

2.5.2 離散擴(kuò)展卡爾曼濾波

2.5.3 連續(xù)擴(kuò)展卡爾曼濾波

第3章 無跡卡爾曼濾波

3.1 無跡變換與采樣策略

3.1.1 無跡變換原理

3.1.2 無跡變換的精度分析

3.1.3 無跡變換的采樣策略

3.2 無跡卡爾曼濾波算法

第4章 優(yōu)化的無跡卡爾曼濾波及其應(yīng)用

4.1 改進(jìn)的強(qiáng)跟蹤無跡卡爾曼濾波及其應(yīng)用

4.1.1 改進(jìn)的強(qiáng)跟蹤無跡卡爾曼濾波算法

4.1.2 改進(jìn)的強(qiáng)跟蹤無跡卡爾曼濾波算法在INS/GNSS組合導(dǎo)航系統(tǒng)中的應(yīng)用

4.2 約束無跡卡爾曼濾波及其在車輛組合導(dǎo)航中的應(yīng)用

4.2.1 約束方程

4.2.2 約束無跡卡爾曼濾波算法

4.2.3 約束無跡卡爾曼濾波統(tǒng)計特性

4.2.4 約束無跡卡爾曼濾波算法在GPS/DR組合導(dǎo)航中的應(yīng)用

4.3 抗差模型預(yù)測無跡卡爾曼濾波

4.3.1 抗差模型預(yù)測無跡卡爾曼濾波算法

4.3.2 抗差模型預(yù)測無跡卡爾曼濾波在SINS/BDS/CNS組合導(dǎo)航中的應(yīng)用

第5章 粒子濾波概述

5.1 粒子濾波算法

5.1.1 貝葉斯濾波

5.1.2 蒙特卡羅采樣

5.1.3 序貫重要性采樣

5.1.4 重采樣

5.1.5 標(biāo)準(zhǔn)粒子濾波算法

5.1.6 粒子濾波存在的問題

5.2 粒子濾波優(yōu)化算法

5.2.1 避免粒子貧化

5.2.2 降低計算復(fù)雜度

5.2.3 優(yōu)選重要性密度函數(shù)

第6章 優(yōu)化的粒子濾波

6.1 抗差自適應(yīng)中心差分粒子濾波

6.1.1 中心差分算法

6.1.2 抗差自適應(yīng)濾波

6.1.3 抗差自適應(yīng)中心差分粒子濾波算法

6.1.4 SINS/CNS組合導(dǎo)航系統(tǒng)仿真計算與分析

6.2 抗差自適應(yīng)高斯混合Sigma點粒子濾波

6.2.1 高斯粒子濾波

6.2.2 抗差自適應(yīng)高斯混合Sigma點粒子濾波算法

6.2.3 SINS/SAR/CNS組合導(dǎo)航系統(tǒng)直接法濾波中的應(yīng)用

第7章 改進(jìn)的無跡粒子濾波算法及其應(yīng)用

7.1 抗差自適應(yīng)無跡粒子濾波

7.1.1 抗差自適應(yīng)無跡粒子濾波算法

7.1.2 仿真計算與分析

7.1.3 抗差自適應(yīng)無跡粒子濾波在SINS/SAR組合導(dǎo)航系統(tǒng)中的應(yīng)用

7.2 非線性模型預(yù)測無跡粒子濾波

7.2.1 模型預(yù)測濾波

7.2.2 非線性模型預(yù)測無跡粒子濾波算法

7.2.3 非線性模型無跡粒子濾波算法在SINS/SAR組合導(dǎo)航系統(tǒng)中的應(yīng)用

7.3 衰減記憶平方根無跡粒子濾波

7.3.1 衰減記憶濾波

7.3.2 平方根濾波

7.3.3 衰減記憶平方根無跡粒子濾波算法

7.3.4 SINS/SAR組合導(dǎo)航系統(tǒng)直接法濾波中的應(yīng)用

7.4 基于似然分布的樣本數(shù)自適應(yīng)無跡粒子濾波

7.4.1 樣本數(shù)可自適應(yīng)調(diào)整的粒子濾波

7.4.2 基于似然分布的樣本數(shù)自適應(yīng)無跡粒子濾波算法

7.4.2 SINS/SAR組合導(dǎo)航系統(tǒng)直接法濾波中的應(yīng)用

第8章 基于隨機(jī)加權(quán)的濾波算法及其應(yīng)用

8.1 隨機(jī)加權(quán)估計的基本思想

8.2 動態(tài)導(dǎo)航定位中的隨機(jī)加權(quán)估計

8.2.1 觀測殘差向量與新息向量的協(xié)方差陣

8.2.2 觀測噪聲協(xié)方差矩陣的隨機(jī)加權(quán)開窗估計

8.2.3 仿真實驗與分析

8.3 動力學(xué)模型誤差的Sage隨機(jī)加權(quán)自適應(yīng)濾波

8.3.1 動力學(xué)模型系統(tǒng)誤差

8.3.2 動力學(xué)模型誤差的Sage隨機(jī)加權(quán)自適應(yīng)濾波算法

8.3.3 仿真計算與分析

8.4 基于移動開窗與隨機(jī)加權(quán)估計的自適應(yīng)無跡卡爾曼濾波及其應(yīng)用

8.4.1 無跡卡爾曼濾波的非重采樣形式

8.4.2 隨機(jī)加權(quán)因子的確定

8.4.3 基于移動開窗與隨機(jī)加權(quán)估計的自適應(yīng)無跡卡爾曼濾波算法

8.4.3 INS/GNSS組合導(dǎo)航系統(tǒng)直接法濾波中的應(yīng)用

參考文獻(xiàn) 2100433B

組合導(dǎo)航已成為一個必然趨勢，而濾波算法是實現(xiàn)組合導(dǎo)航的關(guān)鍵技術(shù)，高精度的濾波解算方法能提高組合導(dǎo)航系統(tǒng)的解算精度。本書介紹了組合導(dǎo)航濾波理論的新思想，分析和闡述了各種濾波器的特點，針對目前濾波器存在的問題和理論局限性，提出了優(yōu)化的線性濾波算法和非線性濾波方法，適用于不同的組合導(dǎo)航系統(tǒng)狀態(tài)。本書融入了作者近年來在組合導(dǎo)航線性濾波領(lǐng)域取得的最新研究成果。本書可為從事相關(guān)研究的科研人員提供理論參考和借鑒，也可作為工科類特別是控制學(xué)科本科生、研究生的參考資料。

先求出每個振型下的結(jié)構(gòu)的內(nèi)力或位移，

然后將它們兩兩的絕對值及相關(guān)系數(shù)相乘之后再相加，

最后求平方根得到的值,就是振型組合后的結(jié)構(gòu)效應(yīng)。

基于假定輸入地震為平穩(wěn)隨機(jī)過程,各振型反應(yīng)之間相互獨立.2100433B