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

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

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

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

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

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

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

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

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

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

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

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

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

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

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


Сигма Це незавершена стаття з математики.
Ви можете допомогти проекту, виправивши або дописавши її.