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

Комбінаторна оптимізація (англ. 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)}.$