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

enter image description here

dynamic programming approach • 1.5k  views
0
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

0
Please log in to add an answer.

Continue reading

Find answer to specific questions by searching them here. It's the best way to discover useful content.

Find more