Problem optymalizacyjny: Różnice pomiędzy wersjami
| [wersja nieprzejrzana] | [wersja przejrzana] |
Nie podano opisu zmian |
Nie podano opisu zmian |
||
| Linia 2: | Linia 2: | ||
Każdy problem optymalizacyjny daje się sprowadzić do [[Problem decyzyjny (teoria obliczeń)|problemu decyzyjnego]], |
Każdy problem optymalizacyjny daje się sprowadzić do [[Problem decyzyjny (teoria obliczeń)|problemu decyzyjnego]], |
||
w tym sensie, że każdy problem optymalizacyjny ma wersję decyzyjną. Odwrotne twierdzenie nie musi być prawdziwe. |
w tym sensie, że każdy problem optymalizacyjny ma swoją wersję decyzyjną. Odwrotne twierdzenie nie musi być prawdziwe. |
||
==Przykład== |
==Przykład== |
||
Wersja z 10:12, 13 lut 2007
W teorii obliczeń problem optymalizacyjny jest to problem obliczeniowy, którego rozwiązanie polega na znalezieniu największej bądź najmniejszej wartości pewnego parametru problemu, która spełnia pewną własność. Parametr, którego największej bądź najmniejszej wartości szukamy nazywa się funkcją kosztu. 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.