Оптимизациони проблем

Из Википедије, слободне енциклопедије

У математици и рачунарству, оптимизациони проблем је проблем проналажења најбољег од свих могућих решења. Формално речено, оптимизациони проблем је четворка , где је

  • скуп инстанци;
  • за дату инстанцу , је скуп свих могућих решења;
  • за дату инстанцу и могуће решење за , означава меру за , која је обично позитиван реални број.
  • је циљна функција, и то обично или .

Тада је циљ за неку инстанцу пронаћи оптимално решење, то јест могуће решење за које је

За сваки оптимизациони проблем постоји одговарајући проблем одлучивања, који поставља питање да ли постоји могуће решење за неку конкретну меру . На пример, ако је дат граф који садржи чворове и , оптимизациони проблем би могао да буде наћи пут од до који пролази кроз најмање грана. Одговор на овај проблем би могао да буде на пример 4. Одговарајући проблем одлучивања би био да ли постоји путања од до која пролази кроз 10 или мање грана? Одговор на овај проблем је једноставно да или не.

Види још[уреди]