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

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

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

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

Задача дискретної оптимізації визначається як четвірка \mathcal P = (X, (S_x)_{x \in X}, c, goal), де:

  • X — формальна мова над множиною \{0, 1\} розв'язна за поліноміальний час;
  • S_x — підмножина \{0, 1\}^* для кожного x\in X; існує поліном p такий, що size(y) \leq p(size(x)) для всіх y \in S_x та всіх x \in X, та мови \{(x, y) : x \in X, y \in S_x\} та \{ x \in X : S_x = \emptyset \} розв'язні за поліноміальний час;
  • c : \{(x, y) : x \in X, y \in S_x \} \to Q є функцією, обчислюваною за поліноміальний час;
  • goal \in \{max, min\}

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

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

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

В задачі комівояжера задане ціле n>0 та відстані між всіма парами n міст у вигляді (n \times n) матриці [d_{ij}], де d_{ij}\in Z^+. Обхід — це замкнений маршрут, що проходить через кожне місто один раз. Задача полягає у відшуканні обходу з найменшою довжиною.[1]

Можна взяти F={всі перестановки \pi з n об'єктів}. Кожна перестановка \pi є обходом, якщо інтерпретувати \pi(j) як місто, відвідуване після міста j, j = 1, \dots, n. Тоді вартість c відображає \pi в \sum_{j=1}^n d_{j\pi(j)}.

Джерела інформації[ред.ред. код]

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

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