Scribd
Upload
571 views14 pages

Backtracking: Definition Constraints

Backtracking is an algorithmic technique for solving problems by incrementally building candidates to the solutions, and abandoning each partial candidate ("backtracking") as soon as it is determined that the candidate cannot possibly be completed to a valid solution. There are two types of constraints in problems solved with backtracking: explicit constraints that restrict the possible values for each variable, and implicit constraints that determine how the variables must be related to satisfy the problem's criteria. Examples of problems solved with backtracking include finding sums of subsets, graph coloring, finding Hamiltonian cycles, and solving the N-Queens problem.

Uploaded by

Pandia Raj
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
571 views14 pages

Backtracking: Definition Constraints

Backtracking is an algorithmic technique for solving problems by incrementally building candidates to the solutions, and abandoning each partial candidate ("backtracking") as soon as it is determined that the candidate cannot possibly be completed to a valid solution. There are two types of constraints in problems solved with backtracking: explicit constraints that restrict the possible values for each variable, and implicit constraints that determine how the variables must be related to satisfy the problem's criteria. Examples of problems solved with backtracking include finding sums of subsets, graph coloring, finding Hamiltonian cycles, and solving the N-Queens problem.

Uploaded by

Pandia Raj
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PPT, PDF, TXT or read online on Scribd
You are on page 1/ 14

Backtracking

 Definition

 Constraints
• Explicit constraints

• Implicit constraints

 Backtracking Algorithm:

 Examples
Definition
• Backtracking is one of the most general algorithm design
technique useful for optimizing search under some
constraints.
• Many problems which deal with searching for a set of
solutions or for a optimal solution satisfying some
constraints can be solved using the backtracking
formulation.
• To apply backtracking method, the desired
solution must be expressible as an n-tuple (x1…
xn) where xi is chosen from some finite set Si.

• The solution is based on finding one or more


vectors that maximize, minimize, or satisfy a
criterion function P(x1,…,xn).
The major advantage of this method is, once
we know that a partial vector (x1,…xi) will not
lead to an optimal solution that (mi+1………..mn)
possible test vectors may be ignored entirely.
Constrains
• Many problems solved using backtracking require that
all the solutions satisfy a complex set of constraints.

Backtrack approach,
• Requires less than m trials to determine the solution

• Form a solution (partial vector) one component at a


time, and check at every step if this has any chance of
success
Constrains

• If the solution at any point seems not-


promising, ignore it
• If the partial vector (x1; x2; : : : ; xi) does not
yield an optimal solution, ignore mi+1…mn
possible test vectors even without looking at
them
Constrains

• Effectively, find solutions to a problem that


incrementally builds candidates to the
solutions, and abandons each partial
candidate that cannot possibly be completed
to a valid solution
– Only applicable to problems which admit the
concept of partial candidate solution and a
relatively quick test of whether the partial
solution can grow into a complete solution
– If a problem does not satisfy the above
constraint, backtracking is not applicable
– Backtracking is not very efficient to find a given
value in an unordered list
• All the solutions require a set of constraints
divided into two

i) Explicit constraints

ii) Implicit constraints


Explicit constraints

• Explicit constraints are rules that restrict each


xi to take on values only from a given set.
• Explicit constraints depend on the particular
instance I of problem being solved
• All tuples that satisfy the explicit constraints
define a possible solution space for I
Examples of explicit constraints
Implicit constraints
• Implicit constraints are rules that determine
which of the tuples in the solution space of I
satisfy the criterion function.
• Implicit constraints describe the way in which
the xi must relate to each other.
• Determine problem solution by systematically
searching the solution space for the given
problem instance.
• Xi € { j } when j is integer 1 ≤ i ≤ n
Backtracking Algorithm
Examples

Certain problems which are solved using


backtracking method are,
• Sum of subsets.

• Graph coloring.

• Hamiltonian cycle.

• N-Queens problem.

You might also like