Problem optymalizacyjny – problem obliczeniowy, którego rozwiązanie polega na znalezieniu największej bądź najmniejszej wartości pewnego parametru problemu, która spełnia określoną własność. Parametr, którego największej bądź najmniejszej wartości szukamy, nazywa się funkcją kosztu (funkcja celu). Problem optymalizacyjny nazywa się problemem maksymalizacyjnym, jeśli polega on na znalezieniu największej wartości funkcji kosztu, i minimalizacyjnym, jeśli szukana jest najmniejsza wartość funkcji kosztu.
Każdy problem optymalizacyjny daje się sprowadzić do problemu decyzyjnego, w tym sensie, że każdy problem optymalizacyjny ma swoją wersję decyzyjną. Odwrotne twierdzenie nie musi być prawdziwe.
Przykład
W optymalizacyjnej wersji problemu pokrycia wierzchołkowego poszukiwany jest najmniejszy zbiór wierzchołków danego grafu incydentny z każdą krawędzią. Jest więc to problem minimalizacyjny.
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
