| dbo:abstract
|
- Az elágazás és korlátozás (BB, B&B vagy BnB) algoritmustervezési paradigma diszkrét és kombinatorikus optimalizálási problémákhoz, valamint a matematikai optimalizáláshoz szolgálnak. Az elágazás és korlátozás algoritmus a jelölt megoldások szisztematikus felsorolását foglalja magában a térmodell keresés segítségével: a jelölt megoldások halmazát úgy gondolják, hogy egy gyökeres fát alkot, amelynek teljes része a gyökér. Az algoritmus e fa ágait vizsgálja, amelyek a megoldás halmazának részhalmazait képviselik. Az ág jelölt megoldásainak felsorolása előtt megvizsgáljuk az ágat az optimális megoldás felső és alsó becsült határaival szemben, és elvetjük, ha nem képes jobb megoldást eredményezni, mint az algoritmus által eddig megtalált legjobb megoldás. Az algoritmus a keresési terület ágainak alsó és felső határainak hatékony becslésén múlik. Ha nem állnak rendelkezésre határok, az algoritmus aprólékos keresésre vált. A módszert először Ailsa Land és Alison Doig tette közzé, miközben a British Petroleum által 1960-ban támogatott londoni közgazdasági iskolában végzett kutatást diszkrét programozás témakörben, és ez lett a leggyakrabban használt eszköz az NP-nehéz feladat optimalizálási problémák megoldására. Az "ágak és összeköttetések" név először Little et al. az utazó értékesítő problémájával kezdődött. (hu)
- Az elágazás és korlátozás (BB, B&B vagy BnB) algoritmustervezési paradigma diszkrét és kombinatorikus optimalizálási problémákhoz, valamint a matematikai optimalizáláshoz szolgálnak. Az elágazás és korlátozás algoritmus a jelölt megoldások szisztematikus felsorolását foglalja magában a térmodell keresés segítségével: a jelölt megoldások halmazát úgy gondolják, hogy egy gyökeres fát alkot, amelynek teljes része a gyökér. Az algoritmus e fa ágait vizsgálja, amelyek a megoldás halmazának részhalmazait képviselik. Az ág jelölt megoldásainak felsorolása előtt megvizsgáljuk az ágat az optimális megoldás felső és alsó becsült határaival szemben, és elvetjük, ha nem képes jobb megoldást eredményezni, mint az algoritmus által eddig megtalált legjobb megoldás. Az algoritmus a keresési terület ágainak alsó és felső határainak hatékony becslésén múlik. Ha nem állnak rendelkezésre határok, az algoritmus aprólékos keresésre vált. A módszert először Ailsa Land és Alison Doig tette közzé, miközben a British Petroleum által 1960-ban támogatott londoni közgazdasági iskolában végzett kutatást diszkrét programozás témakörben, és ez lett a leggyakrabban használt eszköz az NP-nehéz feladat optimalizálási problémák megoldására. Az "ágak és összeköttetések" név először Little et al. az utazó értékesítő problémájával kezdődött. (hu)
|
