Комбинаторна оптимизация

от Уикипедия, свободната енциклопедия
Направо към навигацията Направо към търсенето

Комбинаторната оптимизация (на английски: combinatorial optimization) е термин в приложната математика и компютърните науки, с който се означава откриването на оптимален обект измежду крайно множество от дискретни или сводими до дискретни обекти. Някои обичайни задачи, съдържащи комбинаторна оптимизация, са Задачата за търговския пътник (Traveling Salesman Problem, TSP) и Задачата за минималното покриващо дърво (Minimum Spanning Tree Problem, MSTP). В много задачи за комбинаторна оптимизация е неприложим подходът на пълното изчерпване.

Комбинаторната оптимизация е подобласт на математическата оптимизация и е свързана с теорията на алгоритмите, областта изследване на операциите и теорията на изчислителната сложност. Има важни приложения в области на изкуствения интелект, машинно обучение, софтуерно инженерство и други.

Има множество изследвания над алгоритми за полиномиално време за определени специални класове дискретна оптимизация, голяма част от които обект на теорията на линейното програмиране. Някои известни примери за задачи за комбинаторна оптимизация, които спадат към тази група, са:

и други.

Вижте също[редактиране | редактиране на кода]