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

Комбінаторна оптимізація (Шаблон:Lang-en) — розділ теорії оптимізації. Розглядає задачі оптимізації, у яких множина розв'язків є дискретною або може бути зведена до дискретної.

Визначення

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

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

Елементи $X$ називають екземплярами $𝒫$. Для кожного екземпляру $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)}.$

Див. також

• Дискретна оптимізація
• Задача про 1-центр

Література

• Шаблон:Iw2, Шаблон:Iw2: Combinatorial Optimization: Theory and Algorithms. In: Algorithms and Combinatorics Band 21, 4. Auflage, Springer-Verlag, Berlin 2008, ISBN 978-3-540-71843-7.
• Сергиенко И. В., Шаблон:Comment, Шаблон:Comment Классификация прикладных методов комбинаторной оптимизации Шаблон:Webarchive (info Шаблон:Webarchive) // Кибернетика и системный анализ. — 2009. — № 5. — С. 71-83. — Бібліогр.: 74 назв. Шаблон:Ref-ru
• Л. Ф. Гуляницкий, С. И. Сиренко. Гибридная метаэвристика, основанная на оптимизации муравьиными колониями и Н-методе Шаблон:Webarchive (info Шаблон:Webarchive) // Компьютерная математика. — 2009. — Вып. 1. — С. 142—151. / Об авторах: стр. 151.

Див. також

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