I need a help in the following question: Re-consider problem 4. A moving company

Question

I need a help in the following question:

Re-consider problem 4. A moving company needs to move n homes on a street to their new locations on the same street. The moving company is also located on the same street. Specifically, the current location of home i, 1 i n, is at distance S[i] to the right side of the company. Its new location is at distance F[i] to the right side of the company. For simplicity, we assume 0 S[i] < F[i], which means every home will move to the right side of its current location. (S[i], F[i]] is called moving interval i. Now, suppose the company has only one moving truck and can move only one home at a time. After finishing moving the n homes, the moving truck will return to the company.

For convenience, we assume the array S is sorted such that S[1] < S[2] < … < S[n], but we do not assume that every two adjacent intervals (S[i], F[i]] and (S[i+1], F[i+1]] intersect.

Please design a greedy algorithm to determine the moving order among the n homes such that the total distance traveled by the truck is minimized. You need to prove the correctness.

Explanation / Answer

Modified Branch and bound for finding k-best tours for the traveling salesman problem
Input: (G, d), the set of tours H and an integer so that 1 k |H|
Output: A set H(k) of best tours in the (G, d).
Procedure EXPLORE (I, O, G)
1 Begin
2 Find (LB(I, O)) for (G, d)
3 If (LB(I, O) <U))
4 Then if |I| = n-1
5 Then begin
6 H is the completion of the partial tour I
7 If(|G| = k)
8 Then
9 Remove one of the longest tours in G
10 G = G {H}
11 If (|G| = k)
12 Then
13 U is the length of a longest tour in G
14 End
15 Else begin
16 Find a branching edge E
17 EXPLORE (I{e},O,G)
18 Find LB(I, O {e} taking into account (G, d)
19 If (LB(I, O {e}) <U)
20 Then
21 EXPLORE (I, O {e}, G)
22 End
23 Begin
24 U <=
25 H(k) <= 0
26 EXPLORE (0, 0, H(k))
27 End

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.