Wraz z pojawieniem się programowania liniowego metody te zostały zastosowane do rozwiązywania problemów, takich jak przypisanie, maksymalny przepływ i transport. W erze nowożytnej optymalizacja kombinatoryczna jest przydatna do badania algorytmów, ze szczególnym uwzględnieniem sztucznej inteligencji, uczenia maszynowego i badań operacyjnych.
Do czego służy optymalizacja kombinatoryczna?
Optymalizacja kombinatoryczna to proces poszukiwania maksimów (lub minimów) funkcji celu F, której dziedzina jest dyskretną, ale dużą przestrzenią konfiguracyjną (w przeciwieństwie do N-wymiarowej ciągła spacja).
Dlaczego optymalizacja kombinatoryczna jest trudna?
Trudność wynika z faktu, że w przeciwieństwie do programowania liniowego możliwy obszar problemu kombinatorycznego nie jest zbiorem wypukłym. Dlatego musimy zamiast tego przeszukać siatkę dopuszczalnych punktów lub, w przypadku mieszanej liczby całkowitej, zbiór rozłącznych półprostych lub odcinków linii, aby znaleźć optymalne rozwiązanie.
Na czym polega problem optymalizacji kombinatorycznej?
Optymalizacja kombinatoryczna to temat, który polega na znalezieniu optymalnego obiektu ze skończonego zbioru obiektów … Działa w dziedzinie tych problemów optymalizacyjnych, w których zbiór rozwiązań dopuszczalnych jest dyskretny lub można go zredukować do dyskretnego, a celem jest znalezienie najlepszego rozwiązania.
Czy optymalizacja kombinatoryczna jest NP-trudna?
Gdy okaże się, że wersja decyzyjna problemu optymalizacji kombinatorycznej należy do klasy problemów NP-zupełnych, wówczas wersją optymalizacji jest NP-trudne … Problem optymalizacji, tj. znalezienie minimalnej liczby (najmniej k) wielokątów gwiaździstych, których suma jest równa danemu wielokątowi prostemu, jest NP-trudne.
