Waarom is dit belangrijk?
Zoekprogramma's kunnen met de vertakkingsfactor vooraf inschatten hoeveel vervolgstappen ze nog kunnen doorrekenen voordat het aantal paden te groot wordt. In de wetenschap bepaalt dat hoe ver een robot bij routeplanning vooruit kan kijken zonder elke mogelijkheid na te lopen. Voor onderzoekers en ontwikkelaars betekent dit een haalbare planning, maar een te vroege stop kan een kortere weg over het hoofd zien.
Zo werkt het in de praktijk
Bij ritplanning voor voertuigen is de vertakkingsfactor heel groot, en een overzicht zet er Monte Carlo Tree Search op in, een zoekmethode met steekproeven. In de zorg bouwen Philips Research en de Universiteit Maastricht zorgplannen als paden in een boom. De vertakkingsfactor daalt daar na elke gekozen dienst, met gegevens van het Amerikaanse CDC.
Een overzicht over branch-and-bound koppelt de rekentijd aan de vertakkingsfactor en de diepte van de boom. Onderzoekers vergelijken smalle vertakking, met twee kinderen per knoop, met brede vertakking.
Branch-and-bound splitst een optimalisatieprobleem in deelproblemen en laat takken weg zonder betere oplossing. Pakketten zoals CPLEX en Gurobi gebruiken die werkwijze voor geheeltallige programmering. De vertakkingsfactor is dan het grootste aantal deelproblemen per knoop.




