组合优化

组合最优化（英語：），在应用数学和理论计算机科学的领域中，组合优化是在一个有限的对象集中找出最优对象的一类问题。[1]在很多组合优化的问题中，穷举搜索／枚举法是不可行的。组合优化的问题的特征是可行解的集是离散或者可以简化到离散的，并且目标是找到最优解。常见的例子有旅行商问题和最小生成樹。二维的例子，比如服装厂做衣服，衣服分成很多块，这些块需要从布料上切下来。怎么切，剩下的废布料最少？三维的例子，如集装优化。

组合优化的难处，主要是加进来拓扑分析，不同的拓扑形态下，不同部分的约束关系便不同，算法也就要调整。如果给定一个拓扑形态，组合优化往往就退化成一个整数优化的问题了。

應用

参考文献
  1. Schrijver 2003，第1頁.
  2. Sbihi, Abdelkader; Eglese, Richard W. (PDF). 4OR. 2007, 5 (2): 99–116 [2019-12-26]. S2CID 207070217. doi:10.1007/s10288-007-0047-3. （原始内容存档 (PDF)于2019-12-26）.
  3. Eskandarpour, Majid; Dejax, Pierre; Miemczyk, Joe; Péton, Olivier. (PDF). Omega. 2015, 54: 11–32 [2019-12-26]. doi:10.1016/j.omega.2015.01.006. （原始内容存档 (PDF)于2019-12-26）.

引注
  • Beasley, J. E. (lecture notes). [2022-10-16]. （原始内容存档于2022-10-16）.
  • Cook, William J.; Cunningham, William H.; Pulleyblank, William R.; Schrijver, Alexander. . Wiley. 1997. ISBN 0-471-55894-X.
  • Cook, William. . University of Waterloo. 2016 [2022-10-16]. （原始内容存档于2012-07-22）. (Information on the largest TSP instances solved to date.)
  • Crescenzi, Pierluigi; Kann, Viggo; Halldórsson, Magnús; Karpinski, Marek; Woeginger, Gerhard (编). . [2022-10-16]. （原始内容存档于2007-04-05）. (This is a continuously updated catalog of approximability results for NP optimization problems.)
  • Das, Arnab; Chakrabarti, Bikas K (编). . Lecture Notes in Physics 679. Springer. 2005. Bibcode:2005qnro.book.....D.
  • Das, Arnab; Chakrabarti, Bikas K. . Rev. Mod. Phys. 2008, 80 (3): 1061. Bibcode:2008RvMP...80.1061D. CiteSeerX 10.1.1.563.9990 可免费查阅. S2CID 14255125. arXiv:0801.2193 可免费查阅. doi:10.1103/RevModPhys.80.1061.
  • Lawler, Eugene. . Dover. 2001. ISBN 0-486-41453-1.
  • Lee, Jon. . Cambridge University Press. 2004. ISBN 0-521-01012-8.
  • Papadimitriou, Christos H.; Steiglitz, Kenneth. . Dover. July 1998. ISBN 0-486-40258-4.
  • Schrijver, Alexander. . Algorithms and Combinatorics 24. Springer. 2003. ISBN 9783540443896.
  • Schrijver, Alexander. (PDF). Aardal, K.; Nemhauser, G.L.; Weismantel, R. (编). . Elsevier. 2005: 1–68 [2022-10-16]. （原始内容存档 (PDF)于2020-11-24）.
  • Schrijver, Alexander. (PDF). February 1, 2006 [2022-10-16]. （原始内容存档 (PDF)于2022-12-02）.
  • Sierksma, Gerard; Ghosh, Diptesh. . Springer. 2010. ISBN 978-1-4419-5512-8.
  • Gerard Sierksma; Yori Zwols. . CRC Press. 2015. ISBN 978-1-498-71016-9.
  • Pintea, C-M. . Intelligent Systems Reference Library. Springer. 2014 [2022-10-16]. ISBN 978-3-642-40178-7. （原始内容存档于2021-04-27）.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.