Separacija i evaluacija
Separacija i evaluacija (, BB, B&B) je opšti algoritam za pronalaženje optimalnog rešenja za različite zadatke optimizacije, pogotovo u diskretnoj i kombinatoričkoj optimizaciji. Branch and bound algoritam se sastoji iz sistematičnog nabrajanja svih mogućih rešenja, gde se veliki podskupovi nepotrebnih kandidata masovno odbacuju, korišćenjem procenjene gornje i donje granice kolicine koja je optimizovana.

Ova metodu je prvi predstavio A.H. Land i A.G. Doig 1960. za diskretno programiranje.

Generalni opis 
Da bi se olakšao konkretan opis, pretpostavljamo da je cilj da se nađe minimalna vrednost za funkciju  gde je  iz skupa  iz prihvatljivog ili mogućeg rešenja. Imajući na umu da može da se nađe maksimalna vredost f(x) tako što se nađe minimum iz .

Algoritam separacije i evaluacije zahteva dva procesa. Prvi je proces deljenja koji, imajući skup kandidata , vraća dva ili više slična skupa  čija unija čini skup . Imajući na umu da minimum fukcije  iz skupa  je , gde je svako  minimum funkcije  iz skupa . Ovaj korak se zove grananje (), pošsto njegova rekurzivna primena definiste strukturu stablo ciji su čvorovi podskupovi .

Drugi proces je procedura koja izracunava gornju i donju granicu za minimalnu vrednost funkcije  iz datog podskupa skupa . Ovaj korak se zove spajanje''' ().

Glavna ideja za BB algoritam je: ako je donja granica nekog cvora  veca od gornje granice nekog čvora , onda  može bezbedno da se izbaci iz pretrage. Ovaj korak se zove orezivanje'' (), i obično se implementira tako sto se održava globalna varijabla  koji čuva minimum gornje granice koja je pronađena među trenutno proverenim. Bilo koj čvor čija je donja granica veća od od  može da se izbaci.

Rekurzija se zaustavlja kada se trenutni kandidat iz skupa  smanji na jedan element ili kada se gornja granica iz skupa  poklopi sa donjom granicom. Bilo koji element iz skupa  će biti minimum te funkcije iz skupa .

Kada je  vektor iz , algoritam separacije i evaluacije se spaja sa intervalnom analziom i ugovoračem technika da bi moglo da se obezbedi ograđivanje globalnog minimuma.

Primene 
Ovaj pristup se koristi za veliki broj NP-teških problema:
 Celobrojno programiranje
 Nelinearno programiranje
 Problem putujućeg prodavca (TSP)
 Problem kvadratne dodele
 Maksimalno zadovoljavajući problem (MAX-SAT)
 Pretrega za najbližim susedom (NNS)
 Problem sečenja zalihe
 Analiza lažne buke (FNA)
 Računarska filogenija
 Inverzija skupova
 Procene parametara

Algoritam separacije i evaluacije može takođe da bude baza za razne heuristike. Npr, jedan će možda hteti da prestane da se grana kada se raspon između gornje i donje granice manji od određenog praga. Ovo se koristi kada je rešenje "dovoljno dobro za praktične upotrebe" i može znatno da se smanji broj potrebnih računanja. Ovaj tip rešenja je posebno prihvatljiv kada je cena iskorišćene funkcije velika ili kada je rezltat statičkih procena i onda ne zna se precizno, ali se samo zna da se nalazi u rasponu vrednosti sa specifičnim mogućnostima. Primer njegovre priemene je u biologiji kada se vrsi kladistična analiza da bi se proracunao evolucioni odnos između organizama, gde su setovi podataka obično nepraktično veliki bez heuristike.

Iz ovog raloga, tehnike separacije i evaluacije se često koriste u algoritmu za pretragu stabla igre, najznačanije je u korišćenju alpha-beta orezivanja.

Reference

Literatura 
 
 
 

Оптимизациони алгоритми и методи
Комбинаторна оптимизација
Separacija i evaluacija ( , BB , B&B ) je opšti algoritam za pronalaženje optimalnog rešenja za različite zadatke optimizacije , pogotovo u diskretnoj i kombinatoričkoj optimizaciji . Branch and bound algoritam se sastoji iz sistematičnog nabrajanja svih mogućih rešenja , gde se veliki podskupovi nepotrebnih kandidata masovno odbacuju , korišćenjem procenjene gornje i donje granice kolicine koja je optimizovana . Ova metodu je prvi predstavio A.H . Land i A.G . Doig za diskretno programiranje . Generalni opis Da bi se olakšao konkretan opis , pretpostavljamo da je cilj da se nađe minimalna vrednost za funkciju gde je iz skupa iz prihvatljivog ili mogućeg rešenja . Imajući na umu da može da se nađe maksimalna vredost f( x ) tako što se nađe minimum iz \ . Algoritam separacije i evaluacije zahteva dva procesa . Prvi je proces deljenja koji , imajući skup kandidata , vraća dva ili više slična skupa čija unija čini skup \ . Imajući na umu da minimum fukcije iz skupa je , gde je svako minimum funkcije iz skupa \ . Ovaj korak se zove grananje ( ) , pošsto njegova rekurzivna primena definiste strukturu stablo ciji su čvorovi podskupovi \ . Drugi proces je procedura koja izracunava gornju i donju granicu za minimalnu vrednost funkcije iz datog podskupa skupa \ . Ovaj korak se zove spajanje ' ' ' ( ) . Glavna ideja za BB algoritam je : ako je donja granica nekog cvora veca od gornje granice nekog čvora , onda može bezbedno da se izbaci iz pretrage . Ovaj korak se zove orezivanje ' ' ( ) , i obično se implementira tako sto se održava globalna varijabla koji čuva minimum gornje granice koja je pronađena među trenutno proverenim . Bilo koj čvor čija je donja granica veća od od može da se izbaci . Rekurzija se zaustavlja kada se trenutni kandidat iz skupa smanji na jedan element ili kada se gornja granica iz skupa poklopi sa donjom granicom . Bilo koji element iz skupa će biti minimum te funkcije iz skupa \ . Kada je vektor iz , algoritam separacije i evaluacije se spaja sa intervalnom analziom i ugovoračem technika da bi moglo da se obezbedi ograđivanje globalnog minimuma . Primene Ovaj pristup se koristi za veliki broj NP-teških problema : Celobrojno programiranje Nelinearno programiranje Problem putujućeg prodavca ( TSP ) Problem kvadratne dodele Maksimalno zadovoljavajući problem ( MAX-SAT ) Pretrega za najbližim susedom ( NNS ) Problem sečenja zalihe Analiza lažne buke ( FNA ) Računarska filogenija Inverzija skupova Procene parametara Algoritam separacije i evaluacije može takođe da bude baza za razne heuristike . Npr , jedan će možda hteti da prestane da se grana kada se raspon između gornje i donje granice manji od određenog praga . Ovo se koristi kada je rešenje " dovoljno dobro za praktične upotrebe " i može znatno da se smanji broj potrebnih računanja . Ovaj tip rešenja je posebno prihvatljiv kada je cena iskorišćene funkcije velika ili kada je rezltat statičkih procena i onda ne zna se precizno , ali se samo zna da se nalazi u rasponu vrednosti sa specifičnim mogućnostima . Primer njegovre priemene je u biologiji kada se vrsi kladistična analiza da bi se proracunao evolucioni odnos između organizama , gde su setovi podataka obično nepraktično veliki bez heuristike . Iz ovog raloga , tehnike separacije i evaluacije se često koriste u algoritmu za pretragu stabla igre , najznačanije je u korišćenju alpha-beta orezivanja . Reference Literatura Оптимизациони алгоритми и методи Комбинаторна оптимизација