Prezenatori :Darii Ina Senatov Mircea

ObiectiveDefinitieExempleAplicareConcluzii

DefinitieMetoda Ramifica si margineste ( branch and bound) reprezinta metoda care pentru a rezolva o problema parcurge un arbore binar de ordin m, denumit arborele solutiilor . Algoritmul este capabil s simt soluia, s se ndrepte spre aceasta, i n plus metoda data nu poate conduce la un ciclu infinit, dac problema are soluie, chiar dac spaiul strilor este infinit.

Exemple :Tabla de sah pentru utilizarea celor mai efective metode.GPS-navigator pentru calcularea cea mai scurte rute.Jocul de perspico pentru minimum de mutariProblemele de logica (Gen: Omul; Tapu; Lupul; Varza)

Aplicare :Etapa initiala :Se creeaza lista nodurilor active. La inceput aceasta lista contine un singur element radacina arborelui solutiilor.Jocul de perspico

Etapa ramifica :Din lista nodurilor active se extrage nodul de cos minim si se genereaza toti descendentii acestora.

Etapa margineste:Pentru fiecare descendent se calculeaza valoarea functiiei de cos. Descendentii costului carora este inacteptabil (de obicei, subarborii dati nu contin stari finale) sunt exclusi din studiu. Descendentii ramasi se include in lista nodurilor active.

Concluzie :In concluzie acesta metoda poate fi utilizata doar ca depende de complexitatea problemei incit acesta metoda poate dura mai mult timp de cit celelalte.