Tidskomplexiteten för backtracking -algoritmer är i allmänhet
exponentiell , särskilt ofta uttryckt som
o (b^d) , var:
* b är grenfaktorn (antalet möjliga val vid varje beslutspunkt).
* d är djupet i sökträdet (det maximala antalet beslut som måste fattas för att nå en lösning).
Förklaring:
Backtracking undersöker alla möjliga lösningar genom att systematiskt bygga upp en kandidatlösning ett steg åt gången. Vid varje steg kontrollerar den om den nuvarande kandidaten lovar (dvs om det potentiellt kan leda till en giltig lösning). Om kandidaten lovar undersöker algoritmen rekursivt ytterligare val. Om kandidaten inte lovar (en "återvändsgränd"), algoritmen * backtracks * till föregående steg och försöker ett annat val.
Eftersom algoritmen undersöker ett träd av möjligheter, och antalet grenar kan växa snabbt, kan tidskomplexiteten bli mycket stor, särskilt när djupet `d` ökar.
Varför exponentiellt?
Tänk på det som en trädsökning. Om varje nod i trädet har "B" -barn (grenfaktor "B"), och trädets maximala djup är "D", kan du i värsta fall potentiellt utforska alla "B^d" -noder.
Viktiga överväganden:
* Worst-Case-scenario: O (b^d) tidskomplexiteten är vanligtvis ett * värsta fall * -scenario. Den faktiska runtime beror starkt på problemet och beskärningens effektivitet (hur effektivt algoritmen kan identifiera och undvika att utforska kompromiserande grenar).
* beskärning: Bra backtracking -algoritmer använder olika beskärningstekniker för att avsevärt minska sökutrymmet. Beskärning kan dramatiskt förbättra runtime, men det förändrar inte den inneboende exponentiella naturen hos algoritmen i värsta fall.
* Exempel: Ett klassiskt exempel är att lösa N-Queens-problemet. För att placera N -drottningar på ett NXN -schackbräde är grenfaktorn relaterad till antalet tillgängliga kolumner i rad, och djupet är relaterat till antalet rader. Den värsta tidskomplexiteten reduceras avsevärt genom att kontrollera om konflikter (attackerar drottningar) vid varje steg, vilket beskärar många av de potentiella grenarna.
* Andra faktorer: Förutom `B` och` D` kan andra faktorer påverka runtime. Till exempel kan den tid det tar att utvärdera om en kandidatlösning lovar också vara en betydande faktor.
* np-komplettering: Många problem som löses med backtracking är NP-komplett. Detta innebär att det tros att det inte finns någon polynom-tidsalgoritm för att lösa dem i allmänhet, och backtracking blir ofta en nödvändig (men ibland ineffektiv) tillvägagångssätt.
Sammanfattningsvis:
Även om backtracking kan vara en kraftfull problemlösningsteknik, betyder dess exponentiella tidskomplexitet att den är bäst lämpad för problem där:
* Problemstorleken är relativt liten.
* Effektiva beskärningsstrategier kan användas för att avsevärt minska sökutrymmet.
* En ungefärlig lösning är acceptabel om den exakta lösningen är för tidskrävande för att hitta.
Om ditt problem är stort och beskärning är ineffektivt kan du behöva överväga alternativa algoritmer eller tillnärmningstekniker.
