Комбинаторная оптимизация

Комбинаторная оптимизация — область теории оптимизации в прикладной математике, связанная с исследованием операций, теорией алгоритмов и теорией вычислительной сложности. Комбинаторная оптимизация заключается в поиске оптимального объекта в конечном множестве объектов[1], чем очень похожа на дискретное программирование. Некоторые источники [2] под дискретным программированием понимают целочисленное программирование, противопоставляя ему комбинаторную оптимизацию, имеющую дело с графами, матроидами и похожими структурами. Однако оба термина очень близко связаны и в литературе часто переплетаются. Комбинаторная оптимизация часто сводится к определению эффективного распределения ресурсов, используемых для поиска оптимального решения.

Во многих задачах комбинаторной оптимизации полный перебор нереален. Комбинаторная оптимизация включает в себя задачи оптимизации, в которых множество допустимых решений дискретно или может быть сведено к дискретному множеству.

ПриложенияПравить

Комбинаторная оптимизация используется при:

  • Определении оптимальной сети аэрофлота;
  • Определении, какая машина из парка такси подберёт пассажиров;
  • Определении оптимального пути доставки посылок;
  • Определении правильных атрибутов перед тестированием концепций.

Однако этими примерами приложение комбинаторной оптимизации не ограничивается.

МетодыПравить

Имеется большое число литературы по полиномиальным по времени алгоритмам, работающим на некоторых классах задач дискретного программирования и существенная часть этих алгоритмов принадлежит теории линейного программирования. Некоторые примеры комбинаторной оптимизации, попадающие в эту область — это задача поиска кратчайшего пути и дерева кратчайших путей, определение максимального потока, нахождение остовных деревьев, нахождение паросочетаний, задачи с матроидами.

Задачи комбинаторной оптимизации можно рассматривать как поиск лучшего элемента в некотором дискретном множестве, поэтому, в принципе, могут быть использованы любые алгоритмы поиска или метаэвристические алгоритмы. Однако общие алгоритмы поиска не гарантируют ни оптимального решения, ни быстрого решения (за полиномиальное время). Поскольку некоторые задачи дискретной оптимизации NP-полны, как, например, задача о коммивояжёре, это же следует ожидать и для других задач (если не P=NP).

Частные задачиПравить

 
Оптимальный путь коммивояжёра по крупнейшим 15 городам Германии. Это кратчайший путь из 43.589.145.600 = 14!/2 возможных.

См. такжеПравить

ЛитератураПравить

ПримечанияПравить

  1. Alexander Schrijver. Algorithms and Combinatorics // Combinatorial Optimization: Polyhedra and Efficiency. — Springer. — С. 1.
  2. Discrete Optimization. Elsevier. Дата обращения: 8 июня 2009. Архивировано 24 июня 2013 года.