1,068
个编辑
更改
无编辑摘要
'''组合优化'''主要是从一个有限的对象[[集合]]中寻找一个最佳对象。<ref>{{harvnb|Schrijver|2003|p=1}}.</ref>在许多这样的问题中，'''穷举搜索 exhaustive search '''是不易处理的。如果这些优化问题可行解集是离散的，或者可行解集可以化为离散的，那么可以在问题范围内进行运算，其目标是找到最优解。典型的问题是'''旅行商问题 Traveling Salesman Problem'''(“ TSP”)、最小[[生成树]]问题(“ MST”)和'''背包问题 Knapsack Problem'''。
'''组合优化'''主要是从一个有限的对象集合中寻找一个最佳对象。<ref>{{harvnb|Schrijver|2003|p=1}}.</ref>在许多这样的问题中，'''穷举搜索 exhaustive search '''是不易处理的。如果这些优化问题可行解集是离散的，或者可行解集可以化为离散的，那么可以在问题范围内进行运算，其目标是找到最优解。典型的问题是'''旅行商问题 Traveling Salesman Problem'''(“ TSP”)、最小[[生成树]]问题(“ MST”)和'''背包问题 Knapsack Problem'''。
==参考文献==
==参考文献==
*{{Cite web
*{{Cite web
| url = http://people.brunel.ac.uk/~mastjjb/jeb/or/ip.html
| url = http://people.brunel.ac.uk/~mastjjb/jeb/or/ip.html
| title = Integer programming
| title = Integer programming
| last = Beasley
| last = Beasley
| first = J. E.
| first = J. E.
| type = lecture notes
| type = lecture notes
}}
}}
*{{Cite book
*{{Cite book
| first1 = William J.
| first1 = William J.
| last1 = Cook
| last1 = Cook
| author1-link = William J. Cook
| author1-link = William J. Cook
| first2 = William H.
| first2 = William H.
| last2 = Cunningham
| last2 = Cunningham
| first3 = William R.
| first3 = William R.
| last3 = Pulleyblank
| last3 = Pulleyblank
| author3-link = William R. Pulleyblank
| author3-link = William R. Pulleyblank
| last4 = Schrijver
| last4 = Schrijver
| first4 = Alexander
| first4 = Alexander
| author4-link = Alexander Schrijver
| author4-link = Alexander Schrijver
| title = Combinatorial Optimization
| title = Combinatorial Optimization
| publisher = Wiley
| publisher = Wiley
| year = 1997
| year = 1997
| isbn = 0-471-55894-X
| isbn = 0-471-55894-X
}}
}}
*{{Cite web
*{{Cite web
| title = Optimal TSP Tours
| title = Optimal TSP Tours
| url = http://www.tsp.gatech.edu/optimal/index.html
| url = http://www.tsp.gatech.edu/optimal/index.html
| last = Cook
| last = Cook
| first = William
| first = William
| publisher = [[University of Waterloo]]
| publisher = [[University of Waterloo]]
| year = 2016
| year = 2016
}} ''(Information on the largest TSP instances solved to date.)''
}} ''(Information on the largest TSP instances solved to date.)''
*{{Cite web
*{{Cite web
| editor-last1 = Crescenzi
| editor-last1 = Crescenzi
| editor-first1 = Pierluigi
| editor-first1 = Pierluigi
| editor-last2 = Kann
| editor-last2 = Kann
| editor-first2 = Viggo
| editor-first2 = Viggo
| editor-last3 = Halldórsson
| editor-last3 = Halldórsson
| editor-first3 = Magnús
| editor-first3 = Magnús
| editor-last4 = Karpinski
| editor-last4 = Karpinski
| editor-first4 = Marek
| editor-first4 = Marek
| editor4-link = Marek Karpinski
| editor4-link = Marek Karpinski
| editor-last5 = Woeginger
| editor-last5 = Woeginger
| editor-first5 = Gerhard
| editor-first5 = Gerhard
| editor5-link = Gerhard J. Woeginger
| editor5-link = Gerhard J. Woeginger
| url = http://www.nada.kth.se/%7Eviggo/wwwcompendium/
| url = http://www.nada.kth.se/%7Eviggo/wwwcompendium/
| title = A Compendium of NP Optimization Problems
| title = A Compendium of NP Optimization Problems
}} ''(This is a continuously updated catalog of approximability results for NP optimization problems.)''
}} ''(This is a continuously updated catalog of approximability results for NP optimization problems.)''
*{{Cite book
*{{Cite book
| editor-last1 = Das
| editor-last1 = Das
| editor-first1 = Arnab
| editor-first1 = Arnab
| editor-last2 = Chakrabarti
| editor-last2 = Chakrabarti
| editor-first2 = Bikas K
| editor-first2 = Bikas K
| editor2-link = Bikas K Chakrabarti
| editor2-link = Bikas K Chakrabarti
| title = Quantum Annealing and Related Optimization Methods
| title = Quantum Annealing and Related Optimization Methods
| series = Lecture Notes in Physics
| series = Lecture Notes in Physics
| volume = 679
| volume = 679
| publisher = Springer
| publisher = Springer
| year = 2005
| year = 2005
| bibcode = 2005qnro.book.....D
| bibcode = 2005qnro.book.....D
}}
}}
*{{Cite journal
*{{Cite journal
| last1 = Das
| last1 = Das
| first1 = Arnab
| first1 = Arnab
| last2 = Chakrabarti
| last2 = Chakrabarti
| first2 = Bikas K
| first2 = Bikas K
| s2cid = 14255125
| title = Colloquium: Quantum annealing and analog quantum computation
| title = Colloquium: Quantum annealing and analog quantum computation
| title = Colloquium: Quantum annealing and analog quantum computation
| journal = Rev. Mod. Phys.
| journal = Rev. Mod. Phys.
| volume = 80
| volume = 80
| issue = 3
| issue = 3
| page = 1061
| page = 1061
| year = 2008
| year = 2008
| doi = 10.1103/RevModPhys.80.1061
| doi = 10.1103/RevModPhys.80.1061
| citeseerx = 10.1.1.563.9990
| citeseerx = 10.1.1.563.9990
| bibcode = 2008RvMP...80.1061D
| bibcode = 2008RvMP...80.1061D
| arxiv = 0801.2193
| arxiv = 0801.2193
}}
}}
*{{Cite book
*{{Cite book
| last = Lawler
| last = Lawler
| first = Eugene
| first = Eugene
| author-link = Eugene Lawler
| author-link = Eugene Lawler
| title = Combinatorial Optimization: Networks and Matroids
| title = Combinatorial Optimization: Networks and Matroids
| year = 2001
| year = 2001
| publisher = Dover
| publisher = Dover
| isbn = 0-486-41453-1 <!-- pages = 117–120 -->
| isbn = 0-486-41453-1
}}
}}
*{{Cite book
*{{Cite book
| first = Jon
| first = Jon
| last = Lee
| last = Lee
| author-link = Jon Lee (mathematician)
| author-link = Jon Lee (mathematician)
| url = https://books.google.com/books?id=3pL1B7WVYnAC
| url = https://books.google.com/books?id=3pL1B7WVYnAC
| title = A First Course in Combinatorial Optimization
| title = A First Course in Combinatorial Optimization
| publisher = Cambridge University Press
| publisher = Cambridge University Press
| year = 2004
| year = 2004
| isbn = 0-521-01012-8
| isbn = 0-521-01012-8
}}
}}
*{{Cite book
*{{Cite book
| last1 = Papadimitriou
| last1 = Papadimitriou
| first1 = Christos H.
| first1 = Christos H.
| last2 = Steiglitz
| last2 = Steiglitz
| first2 = Kenneth
| first2 = Kenneth
| author2-link = Kenneth Steiglitz
| author2-link = Kenneth Steiglitz
| title = Combinatorial Optimization : Algorithms and Complexity
| title = Combinatorial Optimization : Algorithms and Complexity
| publisher = Dover
| publisher = Dover
| date = July 1998
| date = July 1998
| isbn = 0-486-40258-4
| isbn = 0-486-40258-4
}}
}}
*{{Cite book
*{{Cite book
| last = Schrijver
| last = Schrijver
| first = Alexander
| first = Alexander
| title = Combinatorial Optimization: Polyhedra and Efficiency
| title = Combinatorial Optimization: Polyhedra and Efficiency
| publisher = Springer
| publisher = Springer
| series = Algorithms and Combinatorics
| series = Algorithms and Combinatorics
| volume = 24
| volume = 24
| year = 2003
| year = 2003
| url = https://books.google.com/books?id=mqGeSQ6dJycC
| url = https://books.google.com/books?id=mqGeSQ6dJycC
| isbn = 9783540443896
| isbn = 9783540443896
}}
}}
*{{Cite book
*{{Cite book
| last = Schrijver
| last = Schrijver
| first = Alexander
| first = Alexander
| chapter = On the history of combinatorial optimization (till 1960)
| chapter = On the history of combinatorial optimization (till 1960)
| title = Handbook of Discrete Optimization
| title = Handbook of Discrete Optimization
| editor-last1 = Aardal
| editor-last1 = Aardal
| editor-first1 = K.|editor1-link=Karen Aardal
| editor-first1 = K.|editor1-link=Karen Aardal
| editor-last2 = Nemhauser
| editor-last2 = Nemhauser
| editor-first2 = G.L.
| editor-first2 = G.L.
| editor-last3 = Weismantel
| editor-last3 = Weismantel
| editor-first3 = R.
| editor-first3 = R.
| publisher = Elsevier
| publisher = Elsevier
| year = 2005
| year = 2005
| pages = 1–68
| pages = 1–68
| chapter-url = http://homepages.cwi.nl/~lex/files/histco.pdf
| chapter-url = http://homepages.cwi.nl/~lex/files/histco.pdf
}}
}}
*{{Cite book
*{{Cite book
| last = Schrijver
| last = Schrijver
| first = Alexander
| first = Alexander
| title = A Course in Combinatorial Optimization
| title = A Course in Combinatorial Optimization
| url = http://homepages.cwi.nl/~lex/files/dict.pdf
| url = http://homepages.cwi.nl/~lex/files/dict.pdf
| date = February 1, 2006
| date = February 1, 2006
}}
}}
*{{Cite book
*{{Cite book
| last1 = Sierksma
| last1 = Sierksma
| first1 = Gerard
| first1 = Gerard
| last2 = Ghosh
| last2 = Ghosh
| first2 = Diptesh
| first2 = Diptesh
| author1-link = Gerard Sierksma
| author1-link = Gerard Sierksma
| title = Networks in Action; Text and Computer Exercises in Network Optimization
| title = Networks in Action; Text and Computer Exercises in Network Optimization
| publisher = Springer
| publisher = Springer
| date = 2010
| date = 2010
| isbn = 978-1-4419-5512-8
| isbn = 978-1-4419-5512-8
}}
}}
*{{Cite book
*{{Cite book
| author1=Gerard Sierksma
| author1=Gerard Sierksma
| author2=Yori Zwols
| author2=Yori Zwols
| title=Linear and Integer Optimization: Theory and Practice
| title=Linear and Integer Optimization: Theory and Practice
| year=2015
| year=2015
| publisher=CRC Press
| publisher=CRC Press
| isbn=978-1-498-71016-9
| isbn=978-1-498-71016-9
}}
}}
*{{Cite book
*{{Cite book
| last = Pintea
| last = Pintea
| first = C-M.
| first = C-M.
| title = Advances in Bio-inspired Computing for Combinatorial Optimization Problem
| title = Advances in Bio-inspired Computing for Combinatorial Optimization Problem
| url = https://www.springer.com/la/book/9783642401787
| url = https://www.springer.com/la/book/9783642401787
| publisher = Springer
| publisher = Springer
| year = 2014
| year = 2014
| isbn = 978-3-642-40178-7
| isbn = 978-3-642-40178-7
| series = Intelligent Systems Reference Library
| series = Intelligent Systems Reference Library
}}
}}