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

Комбінаторна оптимізація (англ. 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^+$. Обхід — це замкнений маршрут, що проходить через кожне місто один раз. Задача полягає у відшуканні обходу з найменшою довжиною.

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

Джерела інформації

• Bernhard Korte, Jens Vygen: Combinatorial Optimization: Theory and Algorithms. In: Algorithms and Combinatorics Band 21, 4. Auflage, Springer-Verlag, Berlin 2008, ISBN 978-3-540-71843-7.

Див. також

• Задача комівояжера,
• Задача пакування рюкзака,
• Задача прокату лиж,
• Обчислювальна складність.
• Цілочисельне програмування