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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до навігації Перейти до пошуку

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

Визначення[ред. | ред. код]

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

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

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

Приклади[ред. | ред. код]

Задача комівояжера[ред. | ред. код]

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

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

Примітки[ред. | ред. код]

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

Література[ред. | ред. код]

Див. також[ред. | ред. код]