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 nepotebnih 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 f(x) gde je x iz skupa S 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 g(x)= -f(x).

Algoritam separacije i evaluacije zahteva dva procesa. Prvi je proces deljenja koji, imajući skup kandidata S, vraća dva ili više slična skupa S_1,S_2... čija unija čini skup S. Imajući na umu da minimum fukcije f(x) iz skupa S je \min\{v_1, v_2, \ldots\}, gde je svako V_i minimum funkcije f(x) iz skupa S_i. Ovaj korak se zove *grananje* (), pošsto njegova rekurzivna primena definiste strukturu stablo ciji su čvorovi podskupovi S.

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

Glavna ideja za BB algoritam je: ako je donja granica nekog cvora A veca od gornje granice nekog čvora B, onda A 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 m koji čuva minimum gornje granice koja je pronađena među trenutno proverenim. Bilo koj čvor čija je donja granica veća od od m može da se izbaci.

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

Kada je x vektor iz R^n, 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
* 
* 
*