Комбинаторная оптимизация — Википедия
Комбинаторная оптимизация — область теории оптимизации в прикладной математике, связанная с исследованием операций, теорией алгоритмов и теорией вычислительной сложности. Комбинаторная оптимизация заключается в поиске оптимального объекта в конечном множестве объектов[1], чем очень похожа на дискретное программирование. Некоторые источники [2] под дискретным программированием понимают целочисленное программирование, противопоставляя ему комбинаторную оптимизацию, имеющую дело с графами, матроидами и похожими структурами. Однако оба термина очень близко связаны и в литературе часто переплетаются. Комбинаторная оптимизация часто сводится к определению эффективного распределения ресурсов, используемых для поиска оптимального решения.
Во многих задачах комбинаторной оптимизации полный перебор нереален. Комбинаторная оптимизация включает в себя задачи оптимизации, в которых множество допустимых решений дискретно или может быть сведено к дискретному множеству.
Приложения
[править | править код]Комбинаторная оптимизация используется при:
- определении оптимальной сети аэрофлота;
- определении, какая машина из парка такси подберёт пассажиров;
- определении оптимального пути доставки посылок;
- определении правильных атрибутов перед тестированием концепций.
Однако этими примерами приложение комбинаторной оптимизации не ограничивается.
Методы
[править | править код]Имеется большое число литературы по полиномиальным по времени алгоритмам, работающим на некоторых классах задач дискретного программирования и существенная часть этих алгоритмов принадлежит теории линейного программирования. Некоторые примеры комбинаторной оптимизации, попадающие в эту область — это задача поиска кратчайшего пути и дерева кратчайших путей, определение максимального потока, нахождение остовных деревьев, нахождение паросочетаний, задачи с матроидами.
Задачи комбинаторной оптимизации можно рассматривать как поиск лучшего элемента в некотором дискретном множестве, поэтому, в принципе, могут быть использованы любые алгоритмы поиска или метаэвристические алгоритмы. Однако общие алгоритмы поиска не гарантируют ни оптимального решения, ни быстрого решения (за полиномиальное время). Поскольку некоторые задачи дискретной оптимизации NP-полны, как, например, задача о коммивояжёре, это же следует ожидать и для других задач (если не P=NP).
Конкретные проблемы
[править | править код]![](http://upload.wikimedia.org/wikipedia/commons/thumb/c/c4/TSP_Deutschland_3.png/200px-TSP_Deutschland_3.png)
- Задача выбора маршрута
- Задача коммивояжёра
- Минимальное остовное дерево
- Линейное программирование (в части выбора переменной, которую следует вводить в базис)
- Целочисленное программирование
- Задача о восьми ферзях — задача удовлетворения ограничений. Если использовать стандартные методы комбинаторной оптимизации для этой задачи, в качестве целевой функции используется число невыполненных ограничений (то есть число атак).
- Задача о ранце
- Задача раскроя
- Задача о назначениях
- Задача о назначении целей
См. также
[править | править код]Примечания
[править | править код]- ↑ Alexander Schrijver. Algorithms and Combinatorics // Combinatorial Optimization: Polyhedra and Efficiency. — Springer. — С. 1.
- ↑ Discrete Optimization . Elsevier. Дата обращения: 8 июня 2009. Архивировано 24 июня 2013 года.
Литература
[править | править код]- Schrijver, Alexander. Combinatorial Optimization: Polyhedra and Efficiency (англ.). — Springer. — Vol. 24. — (Algorithms and Combinatorics).
- Glover F., Kochenberger G. A. Handbook of Metaheuristics. New York: Kluwer Academic Publishers, 2003. 560 p.
- Ватутин Э. И., Титов В. С., Емельянов С. Г. Основы дискретной комбинаторной оптимизации. М.: Аргамак-Медиа, 2016. 270 с. ISBN 978-5-00-024057-1
- Карпенко А. П. Современные алгоритмы поисковой оптимизации. Алгоритмы, вдохновленные природой. М.: МГТУ им. Н. Э. Баумана, 2014. 446 с. ISBN 978-5-7038-3949-2
Для улучшения этой статьи желательно:
|