Комбінаторна оптимізація () — розділ теорії оптимізації. Розглядає задачі оптимізації, у яких множина розв'язків є дискретною або може бути зведена до дискретної.
Визначення
Задача дискретної оптимізації визначається як четвірка , де: — формальна мова над множиною розв'язна за поліноміальний час; — підмножина для кожного ; існує поліном такий, що для всіх та всіх , та мови та розв'язні за поліноміальний час; є функцією, обчислюваною за поліноміальний час;
Елементи називають екземплярами . Для кожного екземпляру елементи називають припустимими розв'язками .
Приклади
Задача комівояжера
В задачі комівояжера задане ціле та відстані між всіма парами міст у вигляді матриці , де . Обхід — це замкнений маршрут, що проходить через кожне місто один раз. Задача полягає у відшуканні обходу з найменшою довжиною.
Можна взяти F={всі перестановки з об'єктів}. Кожна перестановка є обходом, якщо інтерпретувати як місто, відвідуване після міста , . Тоді вартість відображає в
Див. також Дискретна оптимізація Задача про 1-центр
Примітки
Література
, : 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.
Див. також
Задача комівояжера, Задача пакування рюкзака, Задача прокату лиж, Обчислювальна складність. Цілочисельне програмування