Backtracking

Index

N-Queens Problem
Hamiltonian Circuit Problem
Subset-Sum Problem
Branch and Bound
Assignment Problem
Knapsack Problem
Traveling Salesperson Problem

Backtracking is an algorithmic method to solve a problem in an additional way. It uses a recursive approach to explain the problems. We can say that backtracking is needed to find all possible combinations to solve an optimization problem.

Backtracking is a systematic way of trying out different sequences of decisions until we find one that works.

Suppose we have to make a series of decisions, among various choices, where we don't have enough information to know what to choose and each decision leads to a new set of choices, Some sequence of choices (possibly more than one) may be a solution to our problem Backtracking is a methodical way of trying out various sequences of decisions, until we find one that works.

N-Queens Problem

N-Queens problem is to place n-queens in such a manner on an n * n chessboard that no two queens attack each other by being in some row, columns, or diagonal.

It can be seen that for n=1, the problem has a trivial solution, and no solution exists for n=2 and n=3, So first we will consider the 4-queens problem and then generalize it to an n-queens problem.

Solution of n-queens problem

State-space: - Configuration n=8 queens on the board with only one queen per row and column per row and column.
Initial state: - Configuration without queens on the board.
Goal state: - Configuration with n=8 queens such that no queen attacks any other.
Operators or action: - Place a queen on the board.
Condition: - The new queen is not attacked by any other already placed.
Transformation: - Place a new queen in a particular square of the board.
Solution: - one solution (cost is not considered)

Example:

The above picture shows a 4 * 4 chessboard and we have to place 4 queens on it. So, we will start by placing the first queen in the first row.

Now, the second step is to place the second queen in a safe position. Also, we can't place the queen in the first row, so we will try putting the queen in the second row this time.

Let's place the third queen in a safe position, somewhere in the third row.

Now, we can see that there is no safe place where we can put the last queen. So, we will just change the position of the previous queen i.e., backtrack and change the previous decision.

Also, there is no other position where we can place the third queen, so we will go back one more step and change the position of the second queen.

And now we will place the third queen again in a safe position other than the previously placed position in the third row.

We will continue this process and finally, we will get the solution as shown below.

Hamiltonian Circuit Problem

A Hamiltonian circuit is a circuit that visits every vertex once with no repeats. Being a circuit, it must start and end at the same vertex. A Hamiltonian path also visits every vertex once with no repeats but does not have to start and end at the same vertex.

If there exists a closed walk in the connected graph that visits every vertex of the graph exactly once (except starting vertex) without repeating the edges, then such a graph is called a Hamiltonian graph.

Example:

Consider a graph G = (V, E) shown in fig. we have to find a Hamiltonian circuit using the Backtracking method

Firstly, we start our search with vertex 'a' this vertex 'a' becomes the root of our implicit tree.

Next, we choose vertex 'b' adjacent to 'a' as it comes first in lexicographic order (b, c, d).

Next, we select 'c' adjacent to 'b'.

Next, we select 'd' adjacent to 'c'.

Next, we select 'e' adjacent to 'd'.

Next, we select vertex 'f' adjacent to 'e'. The vertex adjacent to 'f' is d and e, but they have already visited. Thus, we get the dead end, and we backtrack one step and remove the vertex 'f' from the partial solution.

From backtracking, the vertex adjacent to 'e' is b, c, d, and f from which vertex 'f' has already been checked, and b, c, d have already visited. So, again we backtrack one step. Now, the vertex adjacent to d are e, f from which e has already been checked, and adjacent of 'f' are d and e. if 'e' vertex, revisited them we get a dead state. So again we backtrack one step.

Now, adjacent to c is 'e' and adjacent to 'e' is 'f' and adjacent to 'f' is 'd' and adjacent to 'f' is 'd' and adjacent to 'd' is 'a'. Here, we get the Hamiltonian cycle as all the vertex other than the start vertex 'a' is visited only once (a-b-c-e-f-d-a).

Here we have generated one Hamiltonian circuit, but another Hamiltonian circuit can also be obtained by considering another vertex.

Subset - Sum Problem

A subset Sum problem is a problem of finding a subset such that the sum of elements equals a given number. The backtracking approach generates all permutations in the worst case but in general, performs better than the recursive approach towards subset sum problem.

Let S is a set of elements and m is the expected sum of subsets then: -

Start with an empty set
Add to the subset, the next element from the list.
If the subset is having sum m then stop with that subset as a solution.
If the subset is not feasible or if we have reached the end of then set then backtrack through the subset until we find the most suitable value.
If the subset is feasible then repeat step 2
If we have visited all the elements without finding a suitable subset and if no backtracking is possible then stop without a solution.

Example:

Solve following problem and draw portion of state space tree M = 30, W = {5, 10, 12, 13, 15, 18}

Solution:

Initially subset={}	sum = 0	Description
5	5	Then add next element.
5, 10	15 i.e., 15 < 30	Add next element
5, 10, 12	27 i.e., 27 < 30	Add next element
5, 10, 12, 13	40 i.e., 40 < 30	Sum exceeds M = 30. Hence backtrack
5, 10, 12, 15	42	Sum exceeds M = 30. Hence backtrack
5, 10, 12, 18	45	Sum exceeds M = 30. Hence backtrack
5, 12, 13	30	The solution obtained as M = 30

Branch and Bound Algorithm

Branch and Bound is an algorithm design paradigm that is generally used for solving combinatorial optimization problems. These problems are typically exponential in terms of time complexity and may require exploring all possible permutations in the worst case.

The branch and bound algorithm is similar to backtracking but is used for optimization problems. It performs a graph transversal on the space-state tree, but general searches BFS instead of DFS

Assignment Problem

In assignment problem 'n' people are assigned 'n' tasks. We have to find the minimum total cost of assignment where each person has exactly one task to perform. For solving this problem we use the n by n cost matrix.

There are two approaches to calculate the cost function:

For each worker, we choose a job with minimum cost from a list of unassigned jobs (take the minimum entry from each row)
For each job, we choose a worker with the lowest cost for that job from the list of unassigned workers (take the minimum entry from each column)

Let's take the below example and try to calculate the promising cost when job 2 is assigned to worker A.

Since job2 is assigned to work A, cost becomes 2, and job2 and worker A becomes unavailable.

Now we assign job3 to worker B as it has minimum cost from the list of unassigned jobs. Cost becomes 2+3=5 and job3 and worker B also becomes unavailable.

Finally, job1 gets assigned to worker C as it has minimum cost among unassigned jobs and job4 gets assigned to worker C as it is the only job left. Total cost becomes 2+3+5+4=14

Knapsack Problem

A knapsack with a limited weight capacity.
Few items each have some weight and value.

The Problem states:

The value of profit obtained by putting the items into the knapsack is maximum

And the weight limit of the knapsack does not exceed.

Knapsack Problem Variants:

Fractional Knapsack Problem
0/1 Knapsack Problem

Fractional Knapsack Problem

As the name suggests, items are divisible here

We can even put the fraction of any item into the knapsack if taking the complete item is not possible.

It is solved using the Greedy Method.

Solved:

For each item, compute its value/weight ratio.
Arrange all the items in decreasing order of their value/ weight ratio.
Start putting the items into the knapsack beginning from the item with the highest ratio. Put as many items as you can into the knapsack.

Example:For the given set of items and knapsack capacity = 60kg, find the optimal solution for the fractional knapsack problem making use of the greedy approach.

Compute the value/weight ratio for each item.

Sort all the items in decreasing order of their value/weight ratio

Start filling the knapsack by putting the items into it one by one.

Now:

Knapsack weight left to be filled is 20kg but item_4 has a weight of 22kg.
Since in fractional knapsack problem, even the fraction of any item can be taken.
So, the knapsack will contain the following items.
< i1, i2, i5, (20/22) i4 >
The total cost of the knapsack
= 160 + (20/22) * 77
= 160 + 70
= 230 units

0/1 Knapsack Problem

As the name suggests, items are indivisible here.
We cant not take the fraction of any item.
we have either take an item completely or leave it completely.
It is solved using a dynamic programming approach.

0/1 Knapsack problem using Dynamic Programming:

Knapsack weight capacity = w
Number of items each having some weight and value = n

Example:For the given set of items and knapsack capacity = 5kg, find the optimal solution for the 0/1 knapsack problem making use of a dynamic programming approach.

Solution:
knapsack capacity (w) = 5kg
Number of items (n) = 4

Draw a table say 'T' with (n+1) = 4+1 = 5 number of rows and (w+1) = 5+1 = 6 number of columns. Fill all the boxes of 0th row and 0th column with 0

Start filling the table row-wise top to bottom from left to right using the formula -
T(i, j) = max{T(i-1), j), value; +T (i-1, j-weight;)}
Finding T(1, 1)
i = 1, j = 1
(value); = 3, (weight); = 2
Substituting the values.
T(1, 1) = max{T(1-1, 1), 3 + T(1-1, 1-2)}
T(1, 1) = max{T(0, 1), 3 + T(0, -1)}
T(1, 1) = 0
Finding T(1, 2)
i = 1, j = 2
(value); = 3, (weight); = 2
Substituting the values.
T(1, 2) = max{T(1-1, 2), 3 + T(1-1, 2-2)}
T(1, 2) = max{T(0, 3 + 0}
T(1, 2) = 3
Finding T(1, 3) = 3
Finding T(1, 4) = 3
Finding T(1, 5) = 3
Finding T(2, 1) = 0
Finding T(2, 2) = 3
Finding T(2, 3) = 4
Finding T(2, 4) = 4
Finding T(2, 5) = 7
Similarly, compute all the entries. After all the entries are computed and filled in the table, we get the following table -

The last entry represents the maximum possible value that can be put into the knapsack
So, the maximum possible value that can be put into the knapsack = 7

Traveling Sales Problem

In this a salesman needs to visit 'n' sites in such a manner that all cities must be visited at once and in the end he returns to the city from where he started with minimum cost.

Suppose the cities are x1, x2, ....... xn where cost cij denotes the cost of traveling from city xi to xj. The traveling salesman's problem is to find a route starting and ending at x1 that will take in all the cities with the minimum cost.

Greedy Strategy for Travelling Salesman Problem:

Example:A newspaper agent daily drops the newspaper to the area assigned in such a manner that he has to cover all the houses in the respective area with minimum travel cost. Compute the minimum travel cost. The area assigned to the agent where he has to drop the newspaper is shown in Fig.