跳转到内容

排序最佳化

编辑链接
维基百科，自由的百科全书

排序最佳化（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]。

相關條目

[编辑]

参考文献

[编辑]
  1. ^ Brenda L. Dietrich; Hoffman, A. J. On greedy algorithms, partially ordered sets, and submodular functions. IBM J. Res. Dev. 47 (2003), no. 1, 25–30.
  2. ^ Topkis, Donald M. Supermodularity and complementarity. Frontiers of Economic Research. Princeton University Press, Princeton, NJ, 1998. xii+272 pp. ISBN 0-691-03244-0
  3. ^ Singer, Ivan Abstract convex analysis. Canadian Mathematical Society Series of Monographs and Advanced Texts. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1997. xxii+491 pp. ISBN 0-471-16015-6
  4. ^ Björner, Anders; Ziegler, Günter M. Introduction to greedoids. Matroid applications, 284–357, Encyclopedia Math. Appl., 40, Cambridge Univ. Press, Cambridge, 1992,
  5. ^ Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 5.3.3: Minimum-Comparison Selection, pp.207–219.
  6. ^ Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 9: Medians and Order Statistics, pp.183–196. Section 14.1: Dynamic order statistics, pp.302–308.
  7. ^ Gibbons, Jean Dickinson; Olkin, Ingram, and Sobel, Milton, Selecting and Ordering of Populations, Wiley, (1977). (Republished as a Classic in Applied Mathematics by SIAM.)
  8. ^ Gupta, Shanti S.; Panchapakesan, S. Multiple decision procedures: Theory and methodology of selecting and ranking populations. Wiley Series in Probability and Mathematical Statistics. New York: John Wiley & Sons. 1979: xxv+573. ISBN 0-471-05177-2. MR 0555416.  (Republished as a Classic in Applied Mathematics by SIAM.)
  9. ^ Santner, Thomas J., and Tamhane, A. C., Design of Experiments: Ranking and Selection, M. Dekker, (1984).
  10. ^ Robert E. Bechhofer, Thomas J. Santner, David M. Goldsman. Design and Analysis of Experiments for Statistical Selection, Screening, and Multiple Comparisons. John Wiley & Sons, 1995.
  11. ^ Friedrich Liese, Klaus-J. Miescke. 2008. Statistical Decision Theory: Estimation, Testing, and Selection. Springer Verlag.
  12. ^ Glasserman, Paul; Yao, David D. Monotone structure in discrete-event systems. Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics. New York: John Wiley & Sons, Inc. 1994: xiv+297. ISBN 0-471-58041-4. MR 1266839. 
  13. ^ Baccelli, François Louis; Cohen, Guy; Olsder, Geert Jan; Quadrat, Jean-Pierre. Synchronization and linearity: An algebra for discrete event systems. Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics. Chichester: John Wiley & Sons, Ltd. 1992: xx+489. ISBN 0-471-93609-X. MR 1204266. 
  14. ^ Heidergott, Bernd; Oldser, Geert Jan; van der Woude, Jacob. Max plus at work: Modeling and analysis of synchronized systems, a course on max-plus algebra and its applications. Princeton Series in Applied Mathematics. Princeton, NJ: Princeton University Press. 2006: xii+213. ISBN 978-0-691-11763-8. MR 2188299. 

延伸閱讀

[编辑]
  • Fujishige, Satoru Submodular functions and optimization. Second edition. Annals of Discrete Mathematics, 58. Elsevier B. V., Amsterdam, 2005. xiv+395 pp. ISBN 0-444-52086-4
  • Gondran, Michel; Minoux, Michel Graphs, dioids and semirings. New models and algorithms. Operations Research/Computer Science Interfaces Series, 41. Springer, New York, 2008. xx+383 pp. ISBN 978-0-387-75449-9
  • Dietrich, B. L.; Hoffman, A. J. On greedy algorithms, partially ordered sets, and submodular functions. IBM J. Res. Dev. 47 (2003), no. 1, 25–30.
  • Murota, Kazuo Discrete convex analysis. SIAM Monographs on Discrete Mathematics and Applications. Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 2003. xxii+389 pp. ISBN 0-89871-540-7
  • Topkis, Donald M. Supermodularity and complementarity. Frontiers of Economic Research. Princeton University Press, Princeton, NJ, 1998. xii+272 pp. ISBN 0-691-03244-0
  • Singer, Ivan Abstract convex analysis. Canadian Mathematical Society Series of Monographs and Advanced Texts. A Wiley-Interscience Publication. John Wiley & Sons, Inc., New York, 1997. xxii+491 pp. ISBN 0-471-16015-6
  • Björner, Anders; Ziegler, Günter M. Introduction to greedoids. Matroid applications, 284–357, Encyclopedia Math. Appl., 40, Cambridge Univ. Press, Cambridge, 1992,
  • Zimmermann, U. Linear and combinatorial optimization in ordered algebraic structures. Ann. Discrete Math. 10 (1981), viii+380 pp.
  • Cuninghame-Green, Raymond Minimax algebra. Lecture Notes in Economics and Mathematical Systems, 166. Springer-Verlag, Berlin-New York, 1979. xi+258 pp. ISBN 3-540-09113-0
  • Baccelli, François Louis; Cohen, Guy; Olsder, Geert Jan; Quadrat, Jean-Pierre. Synchronization and linearity: An algebra for discrete event systems. Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics. Chichester: John Wiley & Sons, Ltd. 1992: xx+489. ISBN 0-471-93609-X. MR 1204266. 
  • Glasserman, Paul; Yao, David D. Monotone structure in discrete-event systems. Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics. New York: John Wiley & Sons, Inc. 1994: xiv+297. ISBN 0-471-58041-4. MR 1266839. 
  • Heidergott, Bernd; Oldser, Geert Jan; van der Woude, Jacob. Max plus at work: Modeling and analysis of synchronized systems, a course on max-plus algebra and its applications. Princeton Series in Applied Mathematics. Princeton, NJ: Princeton University Press. 2006: xii+213. ISBN 978-0-691-11763-8. MR 2188299. 
  • Ho, Y.C., Sreenivas, R., Vakili, P.,"Ordinal Optimization of Discrete Event Dynamic Systems", J. of DEDS 2(2), 61-88, (1992).
  • Allen, Eric, and Marija D. Ilic. Price-Based Commitment Decisions in the Electricity Market. Advances in industrial control. London: Springer, 1999. ISBN 978-1-85233-069-9

外部連結

[编辑]
检索自“https://zh.wikipedia.org/w/index.php?title=排序最佳化&oldid=80836852”