組合算法單純形法

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

組合算法排序和檢索

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

組合算法圖與網絡優化算法

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

組合算法貪心法與擬陣

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

組合算法窮舉搜索

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

組合算法分支限界法

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

其他組合算法還有動態規劃，快速傳里葉變換等 。2100433B

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

第1章 緒論

1.1 組合導航概述

1.1.1 組合導航基本概念

1.1.2 組合導航系統發展概況

1.2 濾波理論的研究概況

1.2.1 濾波算法的基本知識

1.2.2 線性濾波算法

1.2.3 非線性濾波算法

1.3 組合導航非線性濾波算法的應用現狀

第2章 卡爾曼濾波及擴展卡爾曼濾波

2.1 卡爾曼濾波的性質

2.2 離散卡爾曼濾波算法

2.3 連續卡爾曼濾波算法

2.3.1 過程噪聲

2.3.2 量測噪聲

2.3.3 連續卡爾曼濾波推導

2.4 改進的卡爾曼濾波算法

2.4.1 魯棒卡爾曼濾波

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

2.4.3 Sage-Husa卡爾曼濾波

2.5 擴展卡爾曼濾波

2.5.1 線性化方法

2.5.2 離散擴展卡爾曼濾波

2.5.3 連續擴展卡爾曼濾波

第3章 無跡卡爾曼濾波

3.1 無跡變換與采樣策略

3.1.1 無跡變換原理

3.1.2 無跡變換的精度分析

3.1.3 無跡變換的采樣策略

3.2 無跡卡爾曼濾波算法

第4章 優化的無跡卡爾曼濾波及其應用

4.1 改進的強跟蹤無跡卡爾曼濾波及其應用

4.1.1 改進的強跟蹤無跡卡爾曼濾波算法

4.1.2 改進的強跟蹤無跡卡爾曼濾波算法在INS/GNSS組合導航系統中的應用

4.2 約束無跡卡爾曼濾波及其在車輛組合導航中的應用

4.2.1 約束方程

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

4.2.3 約束無跡卡爾曼濾波統計特性

4.2.4 約束無跡卡爾曼濾波算法在GPS/DR組合導航中的應用

4.3 抗差模型預測無跡卡爾曼濾波

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

4.3.2 抗差模型預測無跡卡爾曼濾波在SINS/BDS/CNS組合導航中的應用

第5章 粒子濾波概述

5.1 粒子濾波算法

5.1.1 貝葉斯濾波

5.1.2 蒙特卡羅采樣

5.1.3 序貫重要性采樣

5.1.4 重采樣

5.1.5 標準粒子濾波算法

5.1.6 粒子濾波存在的問題

5.2 粒子濾波優化算法

5.2.1 避免粒子貧化

5.2.2 降低計算復雜度

5.2.3 優選重要性密度函數

第6章 優化的粒子濾波

6.1 抗差自適應中心差分粒子濾波

6.1.1 中心差分算法

6.1.2 抗差自適應濾波

6.1.3 抗差自適應中心差分粒子濾波算法

6.1.4 SINS/CNS組合導航系統仿真計算與分析

6.2 抗差自適應高斯混合Sigma點粒子濾波

6.2.1 高斯粒子濾波

6.2.2 抗差自適應高斯混合Sigma點粒子濾波算法

6.2.3 SINS/SAR/CNS組合導航系統直接法濾波中的應用

第7章 改進的無跡粒子濾波算法及其應用

7.1 抗差自適應無跡粒子濾波

7.1.1 抗差自適應無跡粒子濾波算法

7.1.2 仿真計算與分析

7.1.3 抗差自適應無跡粒子濾波在SINS/SAR組合導航系統中的應用

7.2 非線性模型預測無跡粒子濾波

7.2.1 模型預測濾波

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

7.2.3 非線性模型無跡粒子濾波算法在SINS/SAR組合導航系統中的應用

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

7.3.1 衰減記憶濾波

7.3.2 平方根濾波

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

7.3.4 SINS/SAR組合導航系統直接法濾波中的應用

7.4 基于似然分布的樣本數自適應無跡粒子濾波

7.4.1 樣本數可自適應調整的粒子濾波

7.4.2 基于似然分布的樣本數自適應無跡粒子濾波算法

7.4.2 SINS/SAR組合導航系統直接法濾波中的應用

第8章 基于隨機加權的濾波算法及其應用

8.1 隨機加權估計的基本思想

8.2 動態導航定位中的隨機加權估計

8.2.1 觀測殘差向量與新息向量的協方差陣

8.2.2 觀測噪聲協方差矩陣的隨機加權開窗估計

8.2.3 仿真實驗與分析

8.3 動力學模型誤差的Sage隨機加權自適應濾波

8.3.1 動力學模型系統誤差

8.3.2 動力學模型誤差的Sage隨機加權自適應濾波算法

8.3.3 仿真計算與分析

8.4 基于移動開窗與隨機加權估計的自適應無跡卡爾曼濾波及其應用

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

8.4.2 隨機加權因子的確定

8.4.3 基于移動開窗與隨機加權估計的自適應無跡卡爾曼濾波算法

8.4.3 INS/GNSS組合導航系統直接法濾波中的應用

參考文獻 2100433B

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

先求出每個振型下的結構的內力或位移，

然后將它們兩兩的絕對值及相關系數相乘之后再相加，

最后求平方根得到的值,就是振型組合后的結構效應。

基于假定輸入地震為平穩隨機過程,各振型反應之間相互獨立.2100433B