组合算法

组合算法单纯形法

单纯形法是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