2. Example-2
Find Solution of Travelling salesman problem using nearest neighbor method
| Work\Job | A | B | C | D | E | | A | x | 2 | 5 | 7 | 1 | | B | 6 | x | 3 | 8 | 2 | | C | 8 | 7 | x | 4 | 7 | | D | 12 | 4 | 6 | x | 5 | | E | 1 | 3 | 2 | 8 | x |
Solution:
The number of rows = 5 and columns = 5
| | `A` | `B` | `C` | `D` | `E` | | | `A` | M | 2 | 5 | 7 | 1 | | | `B` | 6 | M | 3 | 8 | 2 | | | `C` | 8 | 7 | M | 4 | 7 | | | `D` | 12 | 4 | 6 | M | 5 | | | `E` | 1 | 3 | 2 | 8 | M | | | | | | | | | |
1. If we start from A, then path is
`A->E=1,``E->C=2,``C->D=4,``D->B=4,``B->A=6`
and total distance = 17
2. If we start from B, then path is
`B->E=2,``E->A=1,``A->C=5,``C->D=4,``D->B=4`
and total distance = 16
3. If we start from C, then path is
`C->D=4,``D->B=4,``B->E=2,``E->A=1,``A->C=5`
and total distance = 16
4. If we start from D, then path is
`D->B=4,``B->E=2,``E->A=1,``A->C=5,``C->D=4`
and total distance = 16
5. If we start from E, then path is
`E->A=1,``A->B=2,``B->C=3,``C->D=4,``D->E=5`
and total distance = 15
This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then
|
