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

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

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

  • I скуп инстанци;
  • за дату инстанцу x \in I, f(x) је скуп свих могућих решења;
  • за дату инстанцу x и могуће решење y за x, m(x, y) означава меру за y, која је обично позитиван реални број.
  • g је циљна функција, и то обично \min или \max.

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


m(x, y) = g \{ m(x, y') \mid y' \in f(x) \} .

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

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