Пређи на садржај

Сепарација и евалуација

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

Separacija i evaluacija (engl. Branch and bound, ББ, Б&Б) је општи алгоритам за проналажење оптималног решења за различите задатке оптимизације, поготово у дискретној и комбинаторичкој оптимизацији. Бранцх анд боунд алгоритам се састоји из систематичног набрајања свих могућих решења, где се велики подскупови непотребних кандидата масовно одбацују, коришћењем процењене горње и доње границе колицине која је оптимизована.

Ова методу је први представио А.Х. Ланд и А.Г. Доиг 1960. за дискретно програмирање.[1]

Генерални опис

[уреди | уреди извор]

Да би се олакшао конкретан опис, претпостављамо да је циљ да се нађе минимална вредност за функцију где је из скупа из прихватљивог или могућег решења. Имајући на уму да може да се нађе максимална вредост ф(x) тако што се нађе минимум из .

Алгоритам сепарације и евалуације захтева два процеса. Први је процес дељења који, имајући скуп кандидата , враћа два или више слична скупа чија унија чини скуп . Имајући на уму да минимум фукције из скупа је , где је свако минимум функције из скупа . Овај корак се зове гранање (енгл. branching), пошсто његова рекурзивна примена дефинисте структуру стабло цији су чворови подскупови .

Други процес је процедура која израцунава горњу и доњу границу за минималну вредност функције из датог подскупа скупа . Овај корак се зове спајање' (енгл. bounding).

Главна идеја за ББ алгоритам је: ако је доња граница неког цвора веца од горње границе неког чвора , онда може безбедно да се избаци из претраге. Овај корак се зове орезивање (енгл. pruning), и обично се имплементира тако сто се одржава глобална варијабла који чува минимум горње границе која је пронађена међу тренутно провереним. Било кој чвор чија је доња граница већа од од може да се избаци.

Рекурзија се зауставља када се тренутни кандидат из скупа смањи на један елемент или када се горња граница из скупа поклопи са доњом границом. Било који елемент из скупа ће бити минимум те функције из скупа .

Када је вектор из , алгоритам сепарације и евалуације се спаја са интервалном аналзиом[2] и уговорачем тецхника да би могло да се обезбеди ограђивање глобалног минимума.[3][4]

Овај приступ се користи за велики број НП-тешких проблема:

  • Целобројно програмирање
  • Нелинеарно програмирање
  • Проблем путујућег продавца (ТСП)
  • Проблем квадратне доделе
  • Максимално задовољавајући проблем (МАX-САТ)
  • Претрега за најближим суседом (ННС)
  • Проблем сечења залихе
  • Анализа лажне буке (ФНА)
  • Рачунарска филогенија
  • Инверзија скупова
  • Процене параметара

Алгоритам сепарације и евалуације може такође да буде база за разне хеуристике. Нпр, један ће можда хтети да престане да се грана када се распон између горње и доње границе мањи од одређеног прага. Ово се користи када је решење "довољно добро за практичне употребе" и може знатно да се смањи број потребних рачунања. Овај тип решења је посебно прихватљив када је цена искоришћене функције велика или када је резлтат статичких процена и онда не зна се прецизно, али се само зна да се налази у распону вредности са специфичним могућностима. Пример његовре приемене је у биологији када се врси кладистична анализа да би се прорацунао еволуциони однос између организама, где су сетови података обично непрактично велики без хеуристике.

Из овог ралога, технике сепарације и евалуације се често користе у алгоритму за претрагу стабла игре, најзначаније је у коришћењу алпха-бета орезивања.

Референце

[уреди | уреди извор]
  1. ^ А. Х. Ланд анд А. Г. Доиг (1960). „Ан аутоматиц метход оф солвинг дисцрете программинг проблемс”. Ецонометрица. 28 (3). стр. 497—520. дои:10.2307/1910129. 
  2. ^ Мооре, Р. Е. (1966). Интервал Аналyсис. Енглеwоод Цлифф, Неw Јерсеy: Прентице-Халл. ISBN 0-13-476853-1. 
  3. ^ Јаулин, L.; Киеффер, M.; Дидрит, О.; Wалтер, Е. (2001). Апплиед Интервал Аналyсис. Берлин: Спрингер. ISBN 1-85233-219-0. 
  4. ^ Хансен, Е.Р. (1992). Глобал Оптимизатион усинг Интервал Аналyсис. Неw Yорк: Марцел Деккер. 

Литература

[уреди | уреди извор]
  • Хансен, Е.Р. (1992). Глобал Оптимизатион усинг Интервал Аналyсис. Неw Yорк: Марцел Деккер. 
  • Мооре, Р. Е. (1966). Интервал Аналyсис. Енглеwоод Цлифф, Неw Јерсеy: Прентице-Халл. ISBN 0-13-476853-1. 
  • Јаулин, L.; Киеффер, M.; Дидрит, О.; Wалтер, Е. (2001). Апплиед Интервал Аналyсис. Берлин: Спрингер. ISBN 1-85233-219-0.