ALGORITHMS AND DATA STRUCTURES
Prof. Massimo Poncino
Lez 15 - Search-based paradigms: backtracking
Search-based
Algorithms paradigms:
backtracking
Outline
Search-based
Î Search-based paradigms
paradigms
Î Search and solution spaces
Î Backtracking
Search-based paradigms Search-based paradigms
In many problems, the only
way to find a solution is to Two variants
check for all possibilities
Explicit search
We call “all possibilities” Implicit search
the solution space
Copyright © Università Telematica Internazionale UNINETTUNO
1
ALGORITHMS AND DATA STRUCTURES
Prof. Massimo Poncino
Lez 15 - Search-based paradigms: backtracking
Explicit search Brute-force search
a.k.a. Brute-force search Example
Exhaustively enumerate all Find all the divisors
candidates for solution of a natural number n
Cost proportional to the Solution
number of candidate solutions Enumerate all integers from
1 to n, and check whether
each of them divides n
without remainder
Implicit search Implicit search
How to reduce the
Non-useful portions of search space?
the space are pruned
Use specific properties
Implies exploitation of of the search space
some properties of the Backtracking
solution space!
Branch and bound
Depending on the problem
and the strategy, it may “Sample” the search space
yield approximate solutions Random search
Search and solution spaces
The search process is
represented as a decision tree
Search and
solution spaces Unlike the divide-and-conquer
approach the decision tree
represents various solutions
(and not just one)
Copyright © Università Telematica Internazionale UNINETTUNO
2
ALGORITHMS AND DATA STRUCTURES
Prof. Massimo Poncino
Lez 15 - Search-based paradigms: backtracking
Search and solution spaces Search and decision tree:
an example
Tree = composed by nodes Problem
Find all 3-bit binary patterns
Three kinds of nodes for which the # of 1's is ≥ 2
The root node
The only way to solve this
Internal nodes ¨ decisions problem is to check all
the possibilities
Leaf nodes ¨ candidate
solutions (000, 001, 010, ...,111)
Search and decision tree: Search and decision tree:
an example an example
---
Bit i=0
23 = 8 possibilities = Bit 1
Bit i=1
the search space of the problem 0-- 1--
Bit 2
We organize it as
00- 01- 10- 11-
a decision tree
Bit 3
000 001 010 011 100 101 110 111
Backtracking
Backtracking is a refinement
of the brute force approach,
which systematically searches
Backtracking for a solution to a problem
among all available options
Copyright © Università Telematica Internazionale UNINETTUNO
3
ALGORITHMS AND DATA STRUCTURES
Prof. Massimo Poncino
Lez 15 - Search-based paradigms: backtracking
Backtracking algorithms Backtracking algorithms:
general scheme
We assume the solution is The algorithm starts with
represented as a vector an empty vector v = ()
a(1), a(2), ... , a(n) At each stage it extends
the partial vector with
a new value
Where each element a(i)
is selected from a finite v = (a(1), a(2), … , a(k-1))
ordered set S
v = (a(1), a(2), …, a(k-1), a(k))
Backtracking algorithms: Backtracking algorithms:
general scheme general scheme
If the partial solution is
acceptable proceed
If possible choices of a(k)
Otherwise delete current are exhausted, backtrack
choice of a(k) and try and try the next choice
another a(k) for a(k-1)
If possible choices of a(k)
are exhausted, backtrack
and try the next choice
for a(k-1)
Backtracking algorithms: Backtracking algorithms:
general scheme general scheme
Backtrack (k)
i = generic candidate i=0 //initialize candidates
do
k = recursion level i= i+1 //Choose next candidate
if (acceptable)
add a(k) to v
m = # of candidates at each if (k<n)
level (i=1,…,m) Backtrack(k+1)
if (not successful)
n = size of the solution remove a(k) from v
(n candidates) while (not successful and i≠m)
Copyright © Università Telematica Internazionale UNINETTUNO
4
ALGORITHMS AND DATA STRUCTURES
Prof. Massimo Poncino
Lez 15 - Search-based paradigms: backtracking
Backtracking algorithms: Backtracking algorithms:
general scheme general scheme
Backtrack (k)
if (k=n) return The basic backtracking
i=0 // initialize candidates
do scheme can be modified
i= i+1 // Choose next candidate in order to find
if (acceptable)
add a(k) to v
if (k<n) All solutions
Backtrack(k+1)
if (not successful) An optimal solution
remove a(k) from v
while (not successful and i≠m)
Backtracking: computing Backtracking: computing
all solutions all solutions
Backtrack (k)
Equivalent to trying all for (i = 1 … m)
candidates regardless of Choose k-th candidate
the success of the move if (acceptable)
Store it
if (k < n)
Backtrack (k + 1)
Remove the “not successful” else
condition from the main loop print solution
Remove from solution
Backtracking: computing Backtracking: computing
an optimal solution an optimal solution
Backtrack (k)
First option: generate for (i = 1 … m)
all solution and retain Choose k-th candidate
the one with best “value” if (acceptable)
Store it
if (k < n)
Backtrack (k + 1)
Assume that optimality else
is defined in terms of a if (f(solution) > f (optimum)
(positive valued) function f() optimum = solution
Remove from solution
Copyright © Università Telematica Internazionale UNINETTUNO
5
ALGORITHMS AND DATA STRUCTURES
Prof. Massimo Poncino
Lez 15 - Search-based paradigms: backtracking
A working example Example 1: find one solution
---
Find all 3-bit binary k=1 =0
patterns for which the ai
# of 1's is ≥ 2 0--
k=2
n=3 00-
m=2 [0,1] k=3
Backtrack
000
Example 1: find one solution Example 1: find one solution
--- ---
0 0
k=1 a i= k=1 a i=
0-- 0--
k=2 k=2
00- Backtrack 00- Backtrack
k=3 k=3
000 001 000 001
Example 1: find one solution Example 1: find one solution
--- ---
0 0
k=1 a i= k=1 a i=
0-- 0--
k=2 k=2
00- 01- 00- 01-
k=3 k=3 Solution
Backtrack found!
000 001 010 000 001 010 011
Copyright © Università Telematica Internazionale UNINETTUNO
6
ALGORITHMS AND DATA STRUCTURES
Prof. Massimo Poncino
Lez 15 - Search-based paradigms: backtracking
Example 2: find all solutions Example 2: find all solutions
--- ---
k=1 ai=0 k=1 ai=0
0-- 0--
k=2 k=2
00- 00- Backtrack
k=3 k=3
Backtrack
000 000 001
Example 2: find all solutions Example 2: find all solutions
--- ---
0 0
k=1 a i= k=1 a i=
0-- 0--
k=2 k=2
00- 01- 00- 01-
k=3 k=3
Backtrack
000 001 010 000 001 010 011
Example 2: find all solutions Example 2: find all solutions
--- ---
0 a 0 a
k=1 a i= i =1 k=1 a i= i =1
0-- 1-- 0-- 1--
k=2 k=2
00- 01- 10- 00- 01- 10- Backtrack
k=3 Backtrack k=3
000 001 010 011 100 000 001 010 011 100 101
Copyright © Università Telematica Internazionale UNINETTUNO
7
ALGORITHMS AND DATA STRUCTURES
Prof. Massimo Poncino
Lez 15 - Search-based paradigms: backtracking
Example 2: find all solutions Example 2: find all solutions
--- ---
=0 a =0 a
k=1 ai i =1 k=1 ai i =1
0-- 1-- 0-- 1--
k=2 k=2
00- 01- 10- 11- 00- 01- 10- 11-
k=3 Backtrack k=3
000 001 010 011 100 101 110 000 001 010 011 100 101 110 111
Example 3: Find an optimal Example 3: Find an optimal
solution solution
---
0 a
Assume that objective k=1 a i= i =1
function f() is defined
as the number of 1’s of 0-- 1--
a solution k=2
Example: 00- 01- 10- 11-
f(011)=2
k=3
f(111)=3
… 000 001 010 011 100 101 110 111
Improving backtracking: Example: 1’s count example
search pruning
---
Search pruning can help 0
k=1 a i=
reducing the search space
0--
Avoid paths that may not k=2
lead to a solutions as Backtrack
early as possible 00-
Backtrack immediately From 00- you cannot reach
without building a a solution with ≥ 2 ones
“hopeless” solution so you can avoid recurring
Copyright © Università Telematica Internazionale UNINETTUNO
8
ALGORITHMS AND DATA STRUCTURES
Prof. Massimo Poncino
Lez 15 - Search-based paradigms: backtracking
Example 1: Find one solution Example 1: Find one solution
--- ---
k=1 =0
ai k=1 =0
ai
0-- 0--
k=2 k=2
00-
00- 01- 00-
00- 01-
k=3 k=3 Solution
Backtrack found!
010 010 011
Algorithms
Copyright © Università Telematica Internazionale UNINETTUNO
