Laundry shop/cleaner- C
Drugstore- D
Target Mall – T
In which order should she do these errands in order to minimize the time spent on her broom?
Aaronn Daphne M. Gatchalian BSCS 1-5
Use both methods (brute-force algorithm and nearest- neighbor method) and compare. Show
MODULE 6 ASSIGNMENT 1: Traveling Salesman Problems SOLVE THE TWO PROBLEMS
complete solution and enclose final answer. Use Figure 20
A. PROBLEM 1: Traveling Saleswitch Problem
Steps for Both methods are Shown on the last page
Laila is a traveling sales witch and has the following list of errands:
Pet store –P
Greenhouse- G
Laundry
shop/cleaner- C
Drugstore- D
Target Mall – T
In which order should she do these errands in order to minimize the time spent on her broom? Use
both methods (brute-force algorithm and nearest- neighbor method) and compare. Show complete
solution and enclose final answer. Use Figure 20
Brute-force Algorithm
(6-1)! = 5x4x3x2x1
= 120 hamilton circuits
Hamilton Circuit Weights of the edges Total Time spent
HTDCGPH 40+45+50+36+22+36 229
HPTDCGH 36+67+45+50+36+32 266
HTDCPGH 40+45+50+58+22+32 247
HTPGCDH 40+67+22+36+50+22 237
HDCPGTH 22+50+58+22+71+40 263
HGPTDCH 32+22+67+45+50+54 270
Nearest-Neighbor method
Start at H.
H to T is 40
T to D is 45
D to C is 50
C to G is 36
G to P is 22
P to H is 36
If Laila will use the order HTDCGPH, she will spent 229minutes.
Drugstore- D
Target Mall – T
In which order should she do these errands in order to minimize the time spent on her broom?
Aaronn Daphne M. Gatchalian BSCS 1-5
Use both methods (brute-force algorithm and nearest- neighbor method) and compare. Show
MODULE 6 ASSIGNMENT 1: Traveling Salesman Problems SOLVE THE TWO PROBLEMS
complete solution and enclose final answer. Use Figure 20
A. PROBLEM 1: Traveling Saleswitch Problem
Steps for Both methods are Shown on the last page
Laila is a traveling sales witch and has the following list of errands:
Pet store –P
Greenhouse- G
Laundry
shop/cleaner- C
Drugstore- D
Target Mall – T
In which order should she do these errands in order to minimize the time spent on her broom? Use
both methods (brute-force algorithm and nearest- neighbor method) and compare. Show complete
solution and enclose final answer. Use Figure 20
Brute-force Algorithm
(6-1)! = 5x4x3x2x1
= 120 hamilton circuits
Hamilton Circuit Weights of the edges Total Time spent
HTDCGPH 40+45+50+36+22+36 229
HPTDCGH 36+67+45+50+36+32 266
HTDCPGH 40+45+50+58+22+32 247
HTPGCDH 40+67+22+36+50+22 237
HDCPGTH 22+50+58+22+71+40 263
HGPTDCH 32+22+67+45+50+54 270
Nearest-Neighbor method
Start at H.
H to T is 40
T to D is 45
D to C is 50
C to G is 36
G to P is 22
P to H is 36
If Laila will use the order HTDCGPH, she will spent 229minutes.
