How can I use recursion in an Hamiltonian cycle?

Question

I got to resolve an optimization and programmation problem in my cursus of Business Engineering.
The program must simulate the movements of an elevator at the start to serve n people in the Empire State Building.
Here is the problem statement, and unfortunately, I have trouble in recursion coding using the permutation code :

5. Implements the presence of a second lift whose purpose is to minimize the longest waiting times. This second lift has a capacity of 5 people, as for the first one. Whenever the maximum waiting time exceeds 100 seconds, the second lift turns on. It first identifies the set S of the 5 most long-waiting people and builds both the set Q={(origin_i, destination_i), for each i in S} and the distance matrix D between each pairs of distinct floors in Q. Subsequently, it computes the shortest Hamiltonian path in the graph induced by D and serves the people in S according to this schema.

The four first steps were quite easy, but the fifth is quite harder.

Answer 1

How would a brute-force recursive algorithm look like?

We have the "luxury" that our graph is fully connected so we can just go from any node to any other which makes the code pretty simple.

function shortest_path(Q, current, distance){
if(Q is empty) return distance;

return minimum of for (trip in Q) {
shortest_path(
Q - {trip}, trip, distance + D[current, trip]
)
};
}

Where D is the distance matrix.
Then

answer = minimum of for (trip in Q) {
shortest_path(Q - {trip}, trip, 0)
};

It's wonky pseudocode but I hope you see what I mean. To print the path taken in proper order you need to do some more work but I'll leave that to you :P

Answer 2

Imagine you have five people taking the trips

1 -> 2
10 -> 11
20 -> 21
30 -> 31
40 -> 41

You are supposed to build the distance matrix for a graph containing all trips Q = {(1, 2), (10, 11), (20, 21), (30, 31), (40, 41)}.

The distance between two trips `a` and `b` is easy, its `|origin_b - destination_a|`; that's what the elevator has to travel to get from the drop-off point of person `a` to the pick-up point of person `b`.

If the origin of trip `b` falls within trip `a`, we can even say the distance between `a` and `b` is zero: The elevator will stop while transporting person `a` to pick up person `b` with 0 extra travelling time.

(dist(a,b) ≠ dist(b,a), by the way.)

Then all you need to do is find the shortest hamiltonian path in this five-node graph and take the five trips in that order.

You can probably brute-force it and just try all 5! = 120 different paths, using recursion if you wish. 120 possible paths is not many so a dumb algorithm will do.

Answer 3

@schindlabua

Let me first thank you for your time in helping me! :)

My problem is more in the comprehension of your recursive pseudocode than in the problem's comprehension.
Actually, I got the problem.
As I said, my problem is more to adapt the problem to a recursive code because, in fact, I knew the pseudocode you gave.

Answer 4

Could your please explain me more in details what your pseudocode means with my problem?

For instance : don't get " minimum of for (...)"

Thanks in advance

Answer 5

Sure.

Some notation first:
`S + {x}` is adding the element `x` to the set `S`
`S - {x}` is removing the element
`L + [x]` adds an element to a list.
(programmers are pedantic, set vs. list is important)

I will call the current path we are checking `P`.
`Q` is the set we constructed in the beginning, containing all nodes - but with all the nodes that are in `P` removed. In other words, it's all the nodes left to try.

Also, imagine you have an oracle that tells you magically what the shortest remaining distance is, given the path you are currently on, which is pretty handy.

How can we implement our function with that?

fn shortest_distance(Q, P, distance) {
return oracle(Q, P);
}

Okay, that doesn't really help. Let's deconstruct that one step, so the oracle doesn't have to do everything...

1. We choose an element `q` from `Q`
2. We add that to `P` which means `q` is the next trip we take
3. Our oracle tells us the shortest remaining distance given`Q - {q}` and `P + [q]`

[cont..]

Answer 6

To get the shortest path overall, we take all elements in `Q`, try to add them to `P` one by one, and then have our oracle tell us the shortest remaining path for each `q` in `Q`.

The really real, overall shortest path then is `P + [q]` where `q` is the node that gave us the smallest answer doing the stuff above.

And that's what I mean by `minimum of`. I'll spell it out some more:

fn shortest_distance(Q, P, distance) {
let next_q;
let shortest = Integer.MAX_VALUE;

for (q in Q){
let d = oracle(Q - {q}, P + [q]);
if(d < shortest) {
shortest = d;
next_q = q;
}
}

return distance + shortest;
}

Okay, now you've 2 things left to do:
- somehow get `P` out of the function because that's what you are after
- Remove the oracle. But, we don't need it, it turns out the oracle was you all along. With the power of friendship, err..., recursion, we can just replace the calls to the oracle with recursive ones.

Answer 7

It's slightly counterintuitive, but the set Q that we're trying to find an optimal path for contains whole trips, not individual floors!
So the "distance" between two nodes in your graph isn't the distance between two floors but the distance between two trips, which is somewhat more abstract.

In your assignment they call a trip a "pair of distinct floors".

The optimal path we want to find is a path of trips. It tells you in which order to take the trips, not in which order to visit the floors. But if you know which trip to take first, you can figure out which floors to go to in which order (the origin of that trip first, then the destination)

Imagine you have the trips

(18, 26), (1, 10), (10, 1), (11, 15), (16, 27)

Doing all the stuff we discussed, the algorithm turns orders our trips into the following order (probably, I haven't tested it):

(10,1)
(1,10)
(11,15)
(16,27)
(18,26)

[cont..]

Answer 8

That immediately tells you which floors to visit in what order:

Go to floor 10, pick up person 1
Go to floor 1, drop off person 1
Go to floor 1, pick up person 2
Go to floor 10, drop off person 2
Go to floor 11, pick up person 3
Go to floor 15, drop off person 3
Go to floor 16, pick up person 4
Careful, tricky:
Go to floor 18, pick up person 5
Go to floor 26, drop off person 5
Go to floor 27, drop off person 4

The "interweaving" thing happens automagically because of what I said in my first post, when you set the distance to 0 in the distance matrix in some cases.

When pretty printing the output to the screen that might need a bit of extra work though.

Answer 9

I haven't done this type of problem before, but I did try to implement some backtracking algorithms which might be what you are really after.
Try this, maybe it will set you on the right track.
https://www.google.com/amp/s/www.geeksforgeeks.org/hamiltonian-cycle-backtracking-6/amp/

I have solved these with backtracking:
https://code.sololearn.com/cdPRo6zEn369/?ref=app
https://code.sololearn.com/cf32yLv8KVjz/?ref=app

Answer 10

@schindlabua

I understand the principle, but could you give me an exemple in java code?

Answer 11

That would be me doing your homework, sorry! Translating the pseudocode above into java should be pretty straightforward.

Answer 12

Ok, but I've sure a problem:

How can I say to my algorithm to take first the person on his waiting floor?
Like the lift could'nt take the person on his destination floor before his waiting floor?