Problem optymalizacyjny

Problem optymalizacyjny

Problem optymalizacyjny to zagadnienie obliczeniowe, którego celem jest znalezienie największej lub najmniejszej wartości określonego parametru, zwanego funkcją kosztu (funkcją celu). Problemy te dzielą się na dwa główne typy:

• Problemy maksymalizacyjne: Celem jest znalezienie największej wartości funkcji kosztu.
• Problemy minimalizacyjne: Celem jest znalezienie najmniejszej wartości funkcji kosztu.

Każdy problem optymalizacyjny można przekształcić w problem decyzyjny, co oznacza, że istnieje wersja decyzyjna każdego problemu optymalizacyjnego. Jednak nie każde zagadnienie decyzyjne można sprowadzić do problemu optymalizacyjnego.

Przykład

W przypadku problemu pokrycia wierzchołkowego w wersji optymalizacyjnej poszukiwany jest najmniejszy zbiór wierzchołków w grafie, który jest incydentny z każdą krawędzią, co czyni go problemem minimalizacyjnym.

Kategoria: Teoria obliczeń