Het belangrijkste verschil tussen backtracking en branch and bound is dat: de backtracking is een algoritme voor het vastleggen van sommige of alle oplossingen voor bepaalde rekenproblemen, met name voor problemen met de tevredenheid van beperkingen, terwijl vertakking en gebonden een algoritme is om de optimale oplossing voor veel optimalisatieproblemen te vinden, vooral bij discrete en combinatorische optimalisatie.

Een algoritme is een methodische opeenvolging van stappen om een ​​bepaald probleem op te lossen. Er zijn verschillende algoritmen, en twee daarvan zijn backtracking en branch-and-bound.

Backtracking, vertakking en gebonden

Wat is Backtracking?

Backtracking is een algoritme dat het probleem recursief oplost. Het is een systematische manier om verschillende reeksen beslissingen te proberen om de juiste beslissing te vinden. Het berekent de oplossing door methodisch de oplossingsruimte van het gegeven probleem te doorzoeken.

Alle oplossingen voor backtracking moeten voldoen aan een complexe reeks expliciete en impliciete beperkingen. De expliciete beperking beperkt elk vectorelement dat uit de gegeven set kan worden geselecteerd. Bovendien vindt impliciete beperking de tuples in de oplossingsruimte die aan de criteriumfunctie kunnen voldoen.

Wat is vertakt en gebonden?

Vertakt en gebonden is meer geschikt voor situaties waarin we de hebzuchtige methode en dynamisch programmeren niet kunnen toepassen. Gewoonlijk is dit algoritme traag omdat het in het ergste geval exponentiële tijdscomplexiteit vereist, maar soms werkt het met redelijke efficiëntie. Deze methode helpt echter bij het bepalen van globale optimalisatie in niet-convexe problemen.

Verder verdeelt deze methode, om een ​​probleem op te lossen, het gegeven deelprobleem in ten minste twee nieuwe beperkte deelproblemen.

Verschil tussen teruglopen en vertakking en gebonden

Definitie

Backtracking is een algoritme voor het vinden van alle oplossingen voor sommige rekenproblemen, met name problemen met de tevredenheid van de beperking die stapsgewijs kandidaten voor de oplossingen bouwen. Vertakking en gebonden is een algoritme voor discrete en combinatorische optimalisatieproblemen en wiskundige optimalisatie. Dit is dus het belangrijkste verschil tussen teruglopen en vertakking en gebonden.

Proces

Verder vindt backtracking de oplossing voor het algemene probleem door een oplossing te vinden voor het eerste deelprobleem en recursief andere deelproblemen op te lossen op basis van de oplossing van het eerste deelprobleem. Vertakking en gebonden lost echter een bepaald probleem op door het op te delen in ten minste twee nieuwe beperkte deelproblemen. Daarom is dit een ander verschil tussen backtracking en branch and bound.

efficiëntie

Conclusie

Backtracking is een algoritme voor het vastleggen van sommige of alle oplossingen voor bepaalde rekenproblemen, met name voor problemen met de tevredenheid van beperkingen. Branch and Bound, aan de andere kant, is een algoritme om optimale oplossingen te vinden voor veel optimalisatieproblemen, vooral bij discrete en combinatorische optimalisatie. Dat is het belangrijkste verschil tussen Backtracking en Branch and Bound.

Verwijzing:

1. "DAA-algoritme-ontwerptechnieken - Javatpoint." Www.javatpoint.com, beschikbaar hier.2. "Backtracking-introductie - Javatpoint." Www.javatpoint.com, hier beschikbaar.3. "Teruglopen." Wikipedia, Wikimedia Foundation, 7 december 2018, hier beschikbaar.4. "Vertakking en gebonden." Wikipedia, Wikimedia Foundation, 8 oktober 2018, hier beschikbaar.5. “Wat is achteruitrijden? – Definitie van Techopedia.” Techopedia.com, hier beschikbaar.

Afbeelding met dank aan:

1. "Algoritmen vs. Programmeertalen" door Lubaochuan - Eigen werk (CC BY-SA 4.0) via Commons Wikimedia