Відкрити головне меню

Комбінаторна оптимізація (англ. Combinatorial optimization) — розділ теорії оптимізації. Розглядає задачі оптимізації множина розв'язків яких дискретна або може бути зведена до дискретної.

ВизначенняРедагувати

Задача дискретної оптимізації визначається як четвірка  , де:

  •   — формальна мова над множиною   розв'язна за поліноміальний час;
  •   — підмножина   для кожного  ; існує поліном   такий, що   для всіх   та всіх  , та мови   та   розв'язні за поліноміальний час;
  •   є функцією, обчислюваною за поліноміальний час;
  •  

Елементи   називають екземплярами  . Для кожного екземпляру   елементи   називають припустимими розв'язками  .

ПрикладиРедагувати

Задача комівояжераРедагувати

В задачі комівояжера задане ціле   та відстані між всіма парами   міст у вигляді   матриці  , де  . Обхід — це замкнений маршрут, що проходить через кожне місто один раз. Задача полягає у відшуканні обходу з найменшою довжиною.[1]

Можна взяти F={всі перестановки   з   об'єктів}. Кожна перестановка   є обходом, якщо інтерпретувати   як місто, відвідуване після міста  ,  . Тоді вартість   відображає   в  

ПриміткиРедагувати

  1. Х. Пападимитриу, К. Стайглиц. Комбинаторная оптимизация, алгоритмы и сложность. Мир. 

ЛітератураРедагувати

Див. такожРедагувати