Комбинаторна оптимизация
 | За информацията в тази статия или раздел не са посочени източници. Въпросната информация може да е непълна, неточна или изцяло невярна. Имайте предвид, че това може да стане причина за изтриването на цялата статия или раздел. |  |
Комбинаторната оптимизация (на английски: combinatorial optimization) е термин в приложната математика и компютърните науки, с който се означава откриването на оптимален обект измежду крайно множество от дискретни или сводими до дискретни обекти. Някои обичайни задачи, съдържащи комбинаторна оптимизация, са Задачата за търговския пътник (Traveling Salesman Problem, TSP) и Задачата за минималното покриващо дърво (Minimum Spanning Tree Problem, MSTP). В много задачи за комбинаторна оптимизация е неприложим подходът на пълното изчерпване.
Комбинаторната оптимизация е подобласт на математическата оптимизация и е свързана с теорията на алгоритмите, областта изследване на операциите и теорията на изчислителната сложност. Има важни приложения в области на изкуствения интелект, машинно обучение, софтуерно инженерство и други.
Има множество изследвания над алгоритми за полиномиално време за определени специални класове дискретна оптимизация, голяма част от които обект на теорията на линейното програмиране. Някои известни примери за задачи за комбинаторна оптимизация, които спадат към тази група, са:
- Задача за назначенията (Assignment problem),
- Задача за удовлетворяване на ограниченията (Constraint satisfaction problem),
- Задача за линейно разкрояване (Cutting stock problem),
- Задача за раницата (Knapsack problem),
- Задача за минимално покриващо дърво (Minimum spanning tree problem),
- Задача за търговския пътник (Traveling salesman problem),
- Задача за разпределение на медицинските сестри (Nurse scheduling problem),
- различни задачи за маршрутизация (Vehicle routing problem, Vehicle rescheduling problem)
и други.