Комбінаторна оптимізація (англ. Combinatorial optimization) — розділ теорії оптимізації. Розглядає задачі оптимізації, у яких множина розв'язків є дискретною або може бути зведена до дискретної.
Визначення
Задача дискретної оптимізації визначається як четвірка , де:
- — формальна мова над множиною розв'язна за поліноміальний час;
- — підмножина для кожного ; існує поліном такий, що для всіх та всіх , та мови та розв'язні за поліноміальний час;
- є функцією, обчислюваною за поліноміальний час;
Елементи називають екземплярами . Для кожного екземпляру елементи називають припустимими розв'язками .
Приклади
Задача комівояжера
В задачі комівояжера задане ціле та відстані між всіма парами міст у вигляді матриці , де . Обхід — це замкнений маршрут, що проходить через кожне місто один раз. Задача полягає у відшуканні обходу з найменшою довжиною.
Можна взяти F={всі перестановки з об'єктів}. Кожна перестановка є обходом, якщо інтерпретувати як місто, відвідуване після міста , . Тоді вартість відображає в
Див. також
Примітки
- Х. Пападимитриу, К. Стайглиц. Комбинаторная оптимизация, алгоритмы и сложность. Мир.
Література
- [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.
Див. також
- Задача комівояжера,
- Задача пакування рюкзака,
- Задача прокату лиж,
- Обчислювальна складність.
- Цілочисельне програмування
Це незавершена стаття з математики. Ви можете проєкту, виправивши або дописавши її. |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет