Branch and bound er en matematisk metode til efter et bestemt kriterium at finde den bedste mulighed blandt flere uden gennemregning af samtlige muligheder hver for sig.

Faktaboks

Etymologi
Branch and bound er engelsk og betyder 'forgren og forbind'.

Metoden stammer fra George B. Dantzig, Delbert R. Fulkerson (1924-1976) og Selmer M. Johnson (1916-1996), der i 1954 brugte den på "the travelling salesman problem", der, som navnet antyder, går ud på at lægge den korteste rute gennem et antal givne byer. At finde samtlige ruter og derefter sammenligne dem er uoverkommeligt i praksis. Ved forgrening deles problemet op i mindre, fx ved at vælge nogle delruter ud, som skal benyttes. Dette gøres så på forskellige måder, der sammenlignes ved hjælp af en vurdering af den kortest mulige samlede rejselængde med de forskellige delruter anvendt. De grene, hvis ruter under alle omstændigheder er længere end andre, udelukkes nu. Derved reduceres problemets kompleksitet og dermed regnetiden betydeligt. Metoden anvendes på kombinatoriske og operationsanalytiske problemer.

Læs mere i Den Store Danske

Kommentarer

Kommentarer til artiklen bliver synlige for alle. Undlad at skrive følsomme oplysninger, for eksempel sundhedsoplysninger. Fagansvarlig eller redaktør svarer, når de kan.

Du skal være logget ind for at kommentere.

eller registrer dig