Перейти до вмісту

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

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

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

Визначення

[ред. | ред. код]

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

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

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

Приклади

[ред. | ред. код]

Задача комівояжера

[ред. | ред. код]

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

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

Див. також

[ред. | ред. код]

Примітки

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

Література

[ред. | ред. код]

Див. також

[ред. | ред. код]