Дискретна оптимізація

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

Визначення

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

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

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

Приклади

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

Докладніше: Задача комівояжера

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

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

Див. також

• Задача про 1-центр

Примітки

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

Література

• ^[en], ^[de]: Combinatorial Optimization: Theory and Algorithms. In: Algorithms and Combinatorics Band 21, 4. Auflage, Springer-Verlag, Berlin 2008, .
• Сергиенко И. В., Гуляницкий Л. Ф., Сиренко С. И. Классификация прикладных методов комбинаторной оптимизации [ 13 Січня 2016 у Wayback Machine.] (info [ 19 Січня 2016 у Wayback Machine.]) // Кибернетика и системный анализ. — 2009. — № 5. — С. 71-83. — Бібліогр.: 74 назв. (рос.)
• Л. Ф. Гуляницкий, С. И. Сиренко. Гибридная метаэвристика, основанная на оптимизации муравьиными колониями и Н-методе [ 22 Січня 2016 у Wayback Machine.] (info [ 23 Січня 2016 у Wayback Machine.]) // Компьютерная математика. — 2009. — Вып. 1. — С. 142—151. / Об авторах: стр. 151.

Див. також

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