عقبگرد در برابر انشعاب و تحدید
State-Space Search: Backtracking vs. Branch and Bound
جستوجوی فضای حالت: مقایسهٔ روش عقبگرد (Backtracking) با انشعاب و تحدید (Branch and Bound).
طراحی الگوریتم کنکور ارشد علوم کامپیوتر
کارتها · 5
Backtracking suits feasibility/constraint-satisfaction searches; Branch and Bound adds a cost bound for optimization.
When the per-call work f(n) outgrows the watershed n^(log_b a), the recurrence is dominated by the top level and T(n)=Theta(f(n)).
Computing x^n with the four basic operations needs only Θ(log n) multiplications, not Θ(n) : repeatedly square the base while halving the exponent, multiplying in an extra x whenever a bit of n is 1 .
When the work to split/combine, f(n) , exactly matches the leaf cost n^(log_b a) , the recurrence T(n)=aT(n/b)+f(n) solves to Θ (n^(log_b a)log n) — every level costs the same, and there are Θ(log n) levels.
When a recurrence shrinks n by a constant factor (e.g. n→ n/2 or n→√n ), the substitution n=2^m converts division into subtraction, turning a hard recurrence in n into an easy one in m that you can unroll or hit with the Master Theorem.