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