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

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

Визначення

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

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

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

Приклади

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

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

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

Примітки

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

Література

Див. також

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.