01-03-2013, 01:54 PM
Backtracking
Backtracking.pdf (Size: 1.03 MB / Downloads: 150)
The idea
Maze of hedges by Hampton Court Palace
A sequence of objects is chosen from a specified set so
that the sequence satisfies some criterion
Example: n-Queens problem
Sequence: n positions on the chessboard
Set: n2 possible positions
Criterion: no two queens can threaten each other
Depth-first search of a tree (preorder tree traversal
Graph coloring
The m-Coloring problem
Finding all ways to color an undirected graph using at most m
different colors, so that no two adjacent vertices are the same
color.
Usually the m-Coloring problem consider as a unique problem
for each value of m.
The Hamiltonian Circuits Problem
The traveling sales person problem
Chapter 3: Dynamic programming
T(n) = (n-1)(n-2)2n-3
Hamiltonian Circuit (also called a tour)
Given a connected, undirected graph
A path that starts at a given vertex, visits each vertex in the
graph exactly once, and ends at the starting vertex