排序与时序系统最优化引论

书籍简介:

组合最优化可以概括为集合上状态模式的最优化。其中状态模式依赖于时间进程的问题形成一个分支学科---时序系统最优化，简称时序优化。特别当时间进程离散化时，问题归结求一个最优的排列或序列，这就是狭义的”排序”优化。本书从结构性质与方法途径的观点来论述时序优化的基本理论。一阶可解性是指线性生成的贪婪算法。其内在依据是独立性，从可分离系数的排序规则到梯度递增的凸性，再到拟阵与独立系统，可概括一大类经典问题。二阶可解性是藉助限位结构，将众多模型纳入组合最优化中的二部图匹配型算法。可解性的另一线索是从局部的偏序关系扩张为整体的全序关系，即偏序集的线性扩张方法。进而，一旦遇到划分结构，便进入难解性境地。证明NP-困难性的方法，是运用模拟、强迫及变尺度的技巧，构造时序问题的划分模型。在判定问题的NP-困难性之后，精确算法只有动态规划与分枝定界。运用动态规划建立伪多项式时间算法，为近似算法做准备。难解性问题的最终归宿是近似算法设计与分析。其中性能比分析的主导思想是运用均值下界及关键工件进行结构松弛。任意精度逼近是运用伸缩尺度方法。最后，概述空间模式的顺序优化，包括车行路线、电路布线、矩阵运算、DNA基因序列重构等等。

书籍规格:

书籍信息归属:

排序与时序系统最优化引论是科学出版社于2019.11出版的中图分类号为 O224 的主题关于 最优化算法－研究 的书籍。