Combinatorial Search and Heuristic Methods

Question 1

What is backtracking?

Answer 1

Backtracking is a systematic way to iterate through all the possible configurations
of a search space.

Question 2

Typically, when would you use backtracking?

Answer 2

When there are multiple solutions to a problem and you want to return multiple solutions

Question 3

Write out the common back tacking algorithm

Answer 3

bool finished = FALSE; /* found all solutions yet? /
backtrack(int a[], int k, data input)
{
int c[MAXCANDIDATES]; / candidates for next position /
int ncandidates; / next position candidate count /
int i; / counter */
if (is_a_solution(a,k,input))
process_solution(a,k,input);
else {
k = k+1;
construct_candidates(a,k,input,c,&ncandidates);
for (i=0; i