CODEWITHSUNDEEP
algorithmbacktracking
venkysmarty
venkysmarty

Reputation: 11431

back tracking algorithm design technique definition

I am reading about backtracking algorithm design technique. It is mentioned as follows.

Backtracking is a refinement of the brute force approach, which systematically searches for a solution to a problem among all available options. It does so by assuming that the solutions are represented by vectors (v1, v2, ..., vm) of values and by traversing, in a depth first manner, the domains of the vectors until the solutions are found.

My quesitons on above text as follows.

  1. What does author mean by solutions are represented by vectors?

  2. What does author mean by domains of vectors?

Thanks for clarifying.

Upvotes: 1

Views: 1265

Answers (1)

fjardon
fjardon

Reputation: 7996

Let's take the eight queen problem as an example.

The solutions are a vector of 8 positions, 1 for each queen. The vector belongs to the space: ([0,7]x[0,7])^8. This is a very big space, so the backtracking algorithm will use the condition: 'no queen should check another queen', to restrict to a smaller 'domain' (subspace of ([0,7]x[0,7])^8) where the solution vectors exist.

In this case the algorithm will create a solution vector by trying one of the allowed value for the 1st queen, giving the vector: [ (0,0), X, X, X ...]. Then using the condition it will restrict the subspace where the second position should be searched for, and keep doing this until it find a suitable vector.

Depth-first mean that before moving to the domain for the solution [ (0,1), X, X, X ...] the algorithm will exhaust all potential vectors from the domain defined by [ (0,0), X, X, X ...]

Upvotes: 3

Related Questions