Question: Find the path of travelling sales person problem of given graph.
0

Subject: Analysis Of Algorithm

Topic: Dynamic Programming

Difficulty: High

enter image description here

aoa(14) • 1.3k views
ADD COMMENTlink
modified 7 months ago by gravatar for Yashbeer Yashbeer170 written 3.4 years ago by gravatar for satishmanje93 satishmanje9340
0

Step 1: Represent the graph in form of matrix.

enter image description here

Find minimum value of each column and subtract the column minimum value from corresponding column.

Minimum value in column 1, column 2, column 3 and column 4 is 0, 0, 1 and 5. So total minimum value is 6.

After subtracting the Matrix becomes.

$M = \begin{bmatrix} \ ∞ & 0 & 4 & 5 \\ \ 0 & ∞ & 3 & 0 \\ \ 0 & 7 & ∞ & 1 \\ \ 0 & 0 & 0 & ∞ \\ \end{bmatrix}$

Step 4 : Full reduction.

The total reduced cost is = cost (row reduction M) + cost(Column reduction M) = 29 + 6 = 35

$Thus \begin{bmatrix} \ ∞ & 10 & 15 & 20 \\ \ 5 & ∞ & 9 & 10 \\ \ 6 & 13 & ∞ & 12 \\ \ 8 & 8 & 9 & ∞ \\ \end{bmatrix} \ \ \ \text{full reduced matrix} \ \ → \ \ \begin{bmatrix} \ ∞ & 0 & 4 & 5 \\ \ 0 & ∞ & 3 & 0 \\ \ 0 & 7 & ∞ & 1 \\ \ 0 & 0 & 0 & ∞ \\ \end{bmatrix}$

enter image description here

Now as cost of node 2 is optimum, we will set node 2 as E-node and generate its children nodes 5 and 6. Consider path 1, 2, 3 for node 5. Set 1st row and 2nd row to ∞, set 3rd column and 2nd column to ∞. Also M 2 = ∞, M 3 = ∞

$M = \begin{bmatrix} \ ∞ & ∞ & ∞ & ∞ \\ \ ∞ & ∞ & ∞ & ∞ \\ \ ∞ & ∞ & ∞ & 1\\ \ 0 & ∞ & ∞ & ∞ \\ \end{bmatrix}$

Therefore cost of node 5 is optimum cost + reduced cost + old value of M 2 = 35 + 1 + 3 = 39

enter image description here

ADD COMMENTlink
modified 7 months ago by gravatar for Yashbeer Yashbeer170 written 3.4 years ago by gravatar for satishmanje93 satishmanje9340
Please log in to add an answer.