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

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

Примітки

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

Література

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.
Сергиенко И. В., Гуляницкий Л. Ф., Сиренко С. И. Классификация прикладных методов комбинаторной оптимизации (info) // Кибернетика и системный анализ. — 2009. — № 5. — С. 71-83. — Бібліогр.: 74 назв. (рос.)
Л. Ф. Гуляницкий, С. И. Сиренко. Гибридная метаэвристика, основанная на оптимизации муравьиными колониями и Н-методе (info) // Компьютерная математика. — 2009. — Вып. 1. — С. 142—151. / Об авторах: стр. 151.

Див. також

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.

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