MEKDELA AMBA UNIVERSITY

College of computing and informatics

Departments of computer science
Course name :Design and Analysis of Algorithm
Corse code=CoSc3094
No_ Group Name Id_no.

1 Daniel Zigabe 1600375

2 Getaneh Markie 1600605

3 Kindu Fikad 1600756

Submission date: 11/08/2018 E.C

Submitted to :Melese A

Gimba, Ethiopia
Table of Contents
Chapter-5 Backtracking ................................................................................................................................. 1
Outline .......................................................................................................................................................... 1
INTRODUCTION ......................................................................................................................................... 2
Backtracking .............................................................................................................................................. 3
1. Knapsack Problem ..................................................................................................................................... 3
Algorithm of Knapsack Problem ........................................................................................................... 4
Advantages of Knapsack Problem ............................................................................................................. 9
Disadvantages of Knapsack Problem ...................................................................................................... 10
[Link] Salesman Problem (TSP)........................................................................................................... 10
Advantages of TSP................................................................................................................................... 11
Disadvantages of TSP .............................................................................................................................. 11
SOLVING TRAVELLING SALESMAN PROBLEM USING BRANCH AND BOUND APPROACH....................... 12
Row Reduction .................................................................................................................................... 14
Column Reduction............................................................................................................................... 15
Summary ..................................................................................................................................................... 25
References .................................................................................................................................................. 26
 Chapter-5
Backtracking

Outline
Knapsack Problems
Traveling Salesman Problems

1
INTRODUCTION

Backtracking is a powerful algorithmic technique used in computer science to

solve complex problems by exploring all possible solutions in a systematic and
efficient manner. It works by building a solution step by step, making decisions at
each stage and checking whether those decisions lead toward a valid and optimal
outcome. If a chosen path fails or violates the problem’s constraints, the
algorithm automatically reverses the last step and tries a different alternative,
ensuring that no possible solution is overlooked. This approach is particularly
useful in solving combinatorial and optimization problems where multiple
possibilities must be examined, such as the 0/1 Knapsack Problem and the
Traveling Salesman Problem (TSP). In the Knapsack Problem, backtracking helps
determine the best combination of items that maximizes value without exceeding
a given capacity. Similarly, in TSP, it is used to find the shortest possible route that
visits each city exactly once and returns to the starting point. By applying
intelligent pruning techniques, backtracking reduces unnecessary computations
and improves efficiency.

2
Backtracking
 Backtracking -is an algorithmic problem-solving technique used to find solutions by
exploring all possible options in a structured and systematic way.
 It works by building a solution step by step, making a choice at each stage, and checking
whether that choice can lead to a valid solution.
 If the choice turns out to be incorrect or leads to a dead end, the algorithm “backs up”
(or backtracks) to the previous step and tries a different option. This process continues
until a correct solution is found or all possibilities have been explored.
 Backtracking is especially useful for problems that involve multiple combinations or
arrangements, such as solving puzzles like Sudoku, finding paths in a maze,and others.

1. Knapsack Problem
The Knapsack Problem is a resource allocation problem where a decision-maker (a
thief, a cargo loader, etc.) must choose a subset of items from a given set to pack into a

container of fixed capacity. Each item has a weight and a value. The objective is to
maximize the total value without exceeding the capacity. The "0/1" constraint means an
item is either taken wholly or left behind — no splitting allowed.

 The 0-1 Knapsack problem is an optimization problem.

 No polynomial time algorithm is known for the 0-1 Knapsack problem.

 Nobody has shown that a polynomial time algorithm is not possible for
Knapsack problem

 The Backtracking Algorithm for the 0-1 Knapsack Problem

3
  The number of total nodes in the state space tree for n items = 2 n+1 – 1

 O(2n ) at worst-case!

Algorithm of Knapsack Problem

Knapsack(i, weight, profit):

if weight > W:

return

if profit > best:

best = profit

if i == n:

return

# include item

Knapsack(i+1, weight + w[i], profit + v[i])

# exclude item

Knapsack(i+1, weight, profit)

4
Example 1

Item (i) Weight (w) Profit (p)

1 2 3
2 3 5
3 4 6
4 5 10

Maximum capacity M = 8

Step-by-Step Explanation

Level 0
Start at root → (0,0)

Level 1 (Item 1)
Include → (2,3)

Exclude → (0,0)

Level 2 (Item 2)
From (2,3):

Include → (5,8)

Exclude → (2,3)

From (0,0):

Include → (3,5)

Exclude → (0,0)

Level 3 (Item 3)
From (5,8):

Include → (9,14) ❌ (exceeds)

5
 Exclude → (5,8)

From (3,5):

Include → (7,11) ✔

Exclude → (3,5)

Level 4 (Item 4)
From (5,8):

Include → (10,18) ❌

Exclude → (5,8)

From (7,11):

Include → (8,15) ❌ BEST

Exclude → (7,11)

The final answer is= (8,15) → Weight = 8, Profit = 15

Items 2 and 4

6
Based on this diagram

Example 2
Item Weight Value
1 2 40
2 3 50
3 5 100
Capacity = 6

Step 1: Start
(0,0)

No items selected.

7
Step 2: Include Item 1
(2,40)

Weight = 2, Value = 40 ✔ valid

Step 3: From (2,40)

➤ Include Item 2
(5,90)

Weight = 5, Value = 90 ✔ valid

Step 4: From (5,90)

➤ Include Item 3
(10,140) ❌

Weight exceeds 6 → PRUNE (stop)

Step 5: Backtrack from (2,40)

➤ Exclude Item 2

No better solution found → keep (2,40)

Step 6: From root (0,0)

➤ Include Item 2
(3,50)

Step 7: From (3,50)

➤ Include Item 3
(8,150) ❌

Exceeds capacity → PRUNE

Step 8: Try Item 3 alone

8
(5,100) ✔ valid

Final Comparison

(5,90)

(3,50)

(2,40)

(5,100) ✔ best

Final Answer: Maximum Profit = 100

Best subset = Item 3 only

Advantages of Knapsack Problem

 Optimal Resource Utilization
 Wide Real-World Applications
 Clear Mathematical Model
 Flexible Variations

9
Disadvantages of Knapsack Problem
 High Computational Complexity
 Not Always Practical for Large Data
 Simplified Assumptions
 Limited to Single Constraint (Basic Form.

[Link] Salesman Problem (TSP)

The Traveling Salesman Problem is a route optimization problem where a salesperson must
visit a set of cities exactly once and return to the starting city, while minimizing the total travel
distance (or cost, time, fuel, etc.).

 It is one of the most famous NP-hard problems in combinatorial optimization.

 The goal is to minimize the total travel cost (distance/time)

Backtracking treats TSP as a permutation problem: finding the best order to visit the cities. The
algorithm builds a tour step by step, starting from a home city, then choosing which city to visit
next, then the next, and so on, until all cities are visited, finally returning home.

Imagine you have 4 cities: A (start), B, C, D. You want the shortest round trip.

i. Start at A.
ii. You can go to B, C, or D next. Try B first.
iii. From B, go to an unvisited city (C or D). Try C.
iv. From C, go to the last unvisited city (D).
v. From D, return to A. Calculate total distance. This is one complete tour.
vi. Now backtrack: instead of going C from B, try D from B. Then from D, go to C, then back
to A. Calculate.
vii. Backtrack further: from A, try C next instead of B, and so on.

10
The Traveling Salesman Problem (TSP) is a combinatorial optimization problem where a
salesperson must:

 Visit each city exactly once.

 Return to the starting city .
 Minimize the total travel cost (distance, time, fuel, etc.)

Advantages of TSP
 Helps solve real-world routing problems (delivery, logistics)
 Improves optimization skills in algorithms
 Useful in fields like:
 Transportation
 Network design
 Circuit design
 Backtracking gives exact (optimal) solution

Disadvantages of TSP
 Very slow for large inputs (factorial time: O(n!))
 Backtracking explores many unnecessary paths

11
  Not practical for many cities (needs approximation methods)
 High computational cost.

Example
The following graph shows a set of cities and distance between every pair of cities.

if salesman starting city is A, then a TSP tour in the graph is

A→ B → D → C →A
host of the tour
= 10 + 25 + 30 + 15
= 80 unit
Minimum Cost is = 80

SOLVING TRAVELLING SALESMAN PROBLEM USING BRANCH AND BOUND

APPROACH
The Traveling Salesman Problem (TSP) using the Branch and Bound approach is a method to
find the minimum-cost tour by systematically exploring possible routes while eliminating non-
promising paths early.

Branching is dividing the problem into smaller sub problems (possible paths)

Bounding is calculating a lower bound (minimum possible cost) for each path

12
Problem Solve Travelling Salesman Problem using Branch and Bound Algorithm in the following
graph.

solution
Step-1:
Write the initial cost ma trix and reduce it

 To reduce a matrix, perform the row reduction and column reduction of the matrix
separately.

 A row or a column is said to be reduced if it contains at least one entry ‘0’ in it.

13
Row Reduction

 Consider the rows of above matrix one by one.

 If the row already contains an entry ‘0’, then

 There is no need to reduce that row.
 If the row does not contains an entry ‘0’, then
 There is no need to reduce that row.
 Select the least value element from that row.
 Subtract that element from each element of that row.
 This will create an entry ‘0’ in that row, thus reducing that row

Following this, we have

 Reduce the elements of row-1 by 4.

 Reduce the elements of row-2 by 5.

 Reduce the elements of row-3 by 6.

 Reduce the elements of row-4 by 2

 Performing this, we obtain the following row-reduced matrix.

14
 Column Reduction

Consider the columns of above row-reduced matrix one by one.

 If the column already contains an entry ‘0’, then

 There is no need to reduce that column.

 If the column does not contains an entry ‘0’, then

 Reduce that particular column.

 Select the least value element from that column.

 Subtract that element from each element of that column.

 This will create an entry ‘0’ in that column, thus reducing that column.

Following this, we have

 There is no need to reduce column-1.
 There is no need to reduce column-2.
 Reduce the elements of column-3 by 1.
 There is no need to reduce column-4.

15
Finally, the initial distance matrix is completely reduced.

Now, we calculate the cost of node-1 by adding all the reduction elements.
Cost(1)
= Sum of all reduction elements
=4+5+6+2+1
= 18

Step-2

 we consider all other vertices oneby one.

 We select the best vertex where we can land upon to minimize the tour cost
 from the reduced matrix of step-01, M[A,B] = 0
 Set row-A and column-B to ∞
 Set M*B,A+ = ∞

now, resulting cost matrix is:

Now,

 We reduce this matrix.

 Then, we find out the cost of node 02.

16
Row Reduction

 We can not reduce row-1 as all its elements are ∞.

 Reduce all the elements of row-2 by 13.
 There is no need to reduce row-3.
 There is no need to reduce row-4

Column Reduction

 Reduce the elements of column-1 by5.

 We can not reduce column-2 as all its elements are ∞.
 There is no need to reduce column-3.
 There is no need to reduce column-4

 finally, the matrix is completely reduced.

 Now, we calculate the cost of node-2. Cost(2)= Cost(1) + Sum of reduction elements+
M[A,B]

= 18 + (13 + 5) + 0

= 36

17
Node-3 (Path A → C)

 from the reduced matrix of step-01, M[A,C] = 7

 Set row-A and column-C to ∞
 Set M*C,A+ = ∞
 Now, resulting cost matrix is

We reduce this matrix.

Then, we find out the cost of node- 03.

Row Reduction

 We can not reduce row-1 as all its elements are ∞.

 There is no need to reduce row-2.
 There is no need to reduce row-3.
 There is no need to reduce row-4

Column Reduction

 There is no need to reduce column-1.

 There is no need to reduce column-2.
 We can not reduce column-3 as all its elements are ∞.
 There is no need to reduce column-4.
 Thus, the matrix is already column reduced.
 Finally, the matrix is completely reduced.

Now, we calculate the cost of node-3. Cost(3) = Cost(1) + S um of reduction elements + M[A,C]
=18 + 0 + 7 = 25

Node-4 (Path A → D)

18
  Row the reduced matrix of step-01, M[A,D] = 3
 Set row-A and column-D to ∞
 Set M*D,A+ = ∞

We reduce this matrix. Then, we find out the cost of node- 04

Row Reduction

 We can not reduce row-1 as all its elements are ∞.

 There is no need to reduce row-2.
 Reduce all the elements of row-3 by 5.
 There is no need to reduce row-4

Column Reduction

 There is no need to reduce column-1.

 There is no need to reduce column-2.
 There is no need to reduce column-3.
 We can not reduce column-4 as all its elements are ∞. Thus, the matrix is already
column- reduced.
 Finally, the matrix is completely reduced. Now, we calculate the cost of node-4 Cost(4)
= Cost(1) + Sum of reduction elements + M[A,D] = 18 + 5 + 3 = 26

Thus, we have

19
  Cost(2) = 36 (for Path A → B)
 Cost(3) = 25 (for Path A → C)
 Cost(4) = 26 (for Path A → D)
 We choose the node with the lowest cost.
 Since cost for node-3 is lowest, so we prefer to visit node-3.
 Thus, we choose node-3 i.e. path A → C.

Step-03:

 We explore the vertices B and D from node-3.

 We now start from the cost matrix at node-3 which is-

 From the reduced matrix of step- 02, M*C,B+ = ∞

 Set row-C and column-B to ∞
 Set M*B,A+ = ∞
 Now, resulting cost matrix is

Now,

20
We reduce this matrix. Then, we find out the cost of node-5.

Row Reduction

We can not reduce row-1 as all its elements are ∞. o Reduce all the elements of row-2 by 13.

We can not reduce row-3 as all its elements are ∞.

Reduce all the elements of row-4 by 8.

Performing this, we obtain the following row-reduced matrix

Column Reduction

 There is no need to reduce column-1.

 We can not reduce column-2 as all its elements are ∞.
 We can not reduce column-3 as all its elements are ∞.
 There is no need to reduce column-4. Thus, the matrix is already column reduced.
Finally, the matrix is completely reduced. Now, we calculate the cost of node-5.

Cost(5) = cost(3) + Sum of reduction elements + M[C,B]

= 25 + (13 + 8) + ∞

=∞

21
Node-6 (Path A → C → D)

From the reduced matrix of step-02, M*C,D+ = ∞ Set row-C and column-D to ∞ Set M*D,A+ = ∞
Now, resulting cost matrix is

1. We reduce this matrix.

2. Then, we find out the cost of node-6.

Row Reduction

 We can not reduce row-1 as all its elements are ∞.

 There is no need to reduce row-2.
 We can not reduce row-3 as all its elements are ∞.
 We can not reduce row-4 as all its elements are ∞.
 Thus, the matrix is already row reduced.

Column Reduction

 There is no need to reduce column-1.

 We can not reduce column-2 as all its elements are ∞.
 We can not reduce column-3 as all its elements are ∞.
 We can not reduce column-4 as all its elements are ∞.
 Thus, the matrix is already column reduced.
 Finally, the matrix is completely reduced. Now, we calculate the cost of node-6. Cost(6)

= cost(3) + Sum of reduction elements + M[C,D]

= 25 + 0 + 0= 25

Thus, we have

22
  Cost(5) = ∞ (for PathA → C → B)
 Cost(6) = 25 (for PathA → C → D)
 We choose the node with the lowest cost. Ø Since cost for node-6 is lowest, so we
prefer to visit node-6.
 Thus, we choose node-6 i.e. path C → D

Step-4:

 We explore vertex B from node-6.

 We start with the cost matrix at node-6 which is

Node-7 :(Path A → C → D → B)

 From the reduced matrix of step-03, M[D,B] = 0

 Set row-D and column-B to ∞
 Set M*B,A+ = ∞
 Now, resulting cost matrix is

Now,
23
  We reduce this matrix.
 Then, we find out the cost of node-7.

Row Reduction

 We can not reduce row-1 as all its elements are ∞.

 We can not reduce row-2 as all its elements are ∞.
 We can not reduce row-3 as all its elements are ∞.
 We can not reduce row-4 as all its elements are ∞.

Column Reduction

 We cannot reduce column-1 as all its elements are ∞.

 We cannot reduce column-2 as all its elements are ∞.
 We cannot reduce column-3 as all its elements are ∞.
 We cannot reduce column-4 as all its elements are ∞.

Thus, the matrix is already column reduced.

Finally, the matrix is completely reduced. All the entries have become ∞. Now, we calculate
the cost of node-7.

Cost(7) = cost(6) + Sum of reduction elements + M[D,B]

= 25 + 0 + 0= 25

Thus,

Optimal path is: A → C → D → B → A

Cost of Optimal path = 25 units To gain better understanding about Travelling Salesman
Problem.

24
 Summary

Principle Knapsack problem TSP(Traveling Salesman Problem)

State representation Set of items considered so far, Partial tour (sequence of visited
current weight, current value cities), current cost
Decision at each step Include or exclude next item Choose next unvisited city
Feasibility check Weight ≤ capacity No city revisited (except start at
end)
Optimization Upper bound on remaining value Lower bound on remaining cost
pruning (bound)
Goal Maximize total value Minimize total cost
When to backtrack When infeasible OR bound not When partial cost already too
promising high OR bound not promising

25
References
1. Introduction to Algorithms – Thomas H. Cormen, Charles E. Leiserson,
Ronald L. Rivest, Clifford Stein. MIT Press.
2. Algorithm Design – Jon Kleinberg and Éva Tardos. Pearson.
3. The Design and Analysis of Algorithms – Anany Levitin. Pearson Education.
4. Fundamentals of Computer Algorithms – Ellis Horowitz and Sartaj Sahni.
5. GeeksforGeeks – Articles on Knapsack Problem and Traveling Salesman
Problem.
6. TutorialsPoint – Backtracking and optimization problem tutorials.

26