排序最佳化

排序最佳化（ordinal optimization）也称为序最佳化，是最优化中的一种，是针对在偏序集（poset）上取值函数的最佳化^[1][2][3][4]。排序最佳化可以应用在等候网络的理论中。

数学基础

参见：最优化、偏序关系、格_(数学)、组合优化和对偶_(数学) § 序逆对偶

偏序是指在集合P内的二元关系 "≤"，是自反关系、反对称关系及传递关系。针对集合P内的所有a, b及c，会有以下的关系：

• a ≤ a（自反关系）;
• 若 a ≤ b 且 b ≤ a ，则 a = b（反对称关系）;
• if a ≤ b and b ≤ c，则 a ≤ c（传递关系）.

偏序关系也可以说是预序关系。具有偏序关系的集合称为偏序集（poset）。

针对偏序集P内的两个相异元素a, b，若a ≤ b或b ≤ a，则a和b 是可比较的，否则是不可比较的。若偏序集中任两个元素都是可比较的，此偏序集称为全序关系或“chain”（也就是依顺序排列的自然数）。若任两个元素都是不可比较的，则称为反链。

以下是一些数学中偏序集的例子：

• 实数的偏序关系是标准的小于等于关系 ≤ ，也是全序集。
• 特定集合子集形成的集合（幂集），偏序关系是包含。
• 向量空间子空间的集合，偏序关系也是包含。

计算机科学及统计学中的排序最佳化

参见：选择算法

在许多领域都有排序最佳化的问题。计算机科学中会研究选择算法，这种算法比排序算法要简单^[5][6]

决策论会研究选择算法，会要识别出“最佳”的子群体，或是识别出“近乎最佳”的子群体^{[7][8][9][10][11]}。

应用

参见：网络流、等候理论和离散事件仿真

自1960年代起，排序最佳化在其理论及应用上都有许多的扩展。其中的antimatroid（英语：antimatroid）及max-plus代数（英语：max-plus algebra）已应用在网络分析及等候理论中，特别是在等候网络中。排序最佳化也应用在离散事件仿真上^[12][13][14]。

相关条目

• 随机最佳化（英语：Stochastic optimization）
• 计算复杂性理论
• 启发式搜索
• 测量尺度（Ordinal data）