[RESOLVED] Going through gates

[gonliSs]

I have such problem. I think it is simple problem because I saw it many times before.

There is some number of people and each of them has time to go through gate. You can only go through gate with item. There is only one such item. There can only be max 2 people in gate at given time. I am looking for algorithm which finds the shortest path.

For example:
A: 1
B: 4
C: 5
D: 6
are on the left side with given time to go through gate. I think it can be good solution:
AB: 4
A backs with item: 1
AC: 5
A backs with item: 1
AD: 6
= 17.

Which algorithm can I use? Or how this problem is named so I can google it?

[razzle]

I think it can be good solution:

Yes it seems like an optimal strategy. The person with the lowest time carries the item all the time. This item-carrier is then accompanying one person at a time through the gate and is then returning alone to accompany yet another person through the gate until everybody have passed.

[Philip Nicoletti]

For those values, it looks like that is optimal. But in the general case, it looks like that algorithm is not necessarily optimal. For an example, see:

http://mathforum.org/library/drmath/view/56756.html

[razzle]

But in the general case, it looks like that algorithm is not necessarily optimal.

Thank you. I wasn't sure I understood the problem so I just made the proposition in my previous post in the hope the OP would return and discuss.

It looks like an optimal strategy involves splitting the people into a fast and a slow category. The fast people ensure the item can be cheaply returned back through the gate which then allows slow people to pass cheaply in pairs.

It's probably not that hard to formulate a combinatorial algorithm that finds an optimal solution to the problem but that doesn't mean an optimal strategy has been found. That would require a proof.

[gonliSs]

I marked it resolved because I found this:
http://www.inf.fu-berlin.de/inst/ag-...e_at_night.pdf

It's article about this problem with optimal solution.

[razzle]

It's article about this problem with optimal solution.

Too bad.

I was about to suggest a formulation based on the shortest alternating path in a directed graph. The "alternating" comes from the fact that people are moving back and forth through the gate.

The graph has 2^N nodes (states) where N is the number of people. I'm pretty sure a modified Dijkstra shortest path algorithm can be used. And Dijkstra is a greedy algorithm so maybe it's in fact the same solution your link has arrived at.

[gonliSs]

Too bad.

I was about to suggest a formulation based on the shortest alternating path in a directed graph. The "alternating" comes from the fact that people are moving back and forth through the gate.

The graph has 2^N nodes (states) where N is the number of people. I'm pretty sure a modified Dijkstra shortest path algorithm can be used. And Dijkstra is a greedy algorithm so maybe it's in fact the same solution your link has arrived at.

Bold fragment was my first thought. I'll try do it that way

[razzle]

I'll try do it that way

Although the formulation I suggested (shortest alternating (red-blue) path in a directed graph) will work and seems fairly standard I cannot promise it will be better than your article and I haven't been able to locate an implementation (*), so it's better to go for the article. Good luck!

(*) The best evidence I've found that such an algorithm isn't unreasonably hard is that it's given as homework here (see 2.16).

http://alg15.cs.uchicago.edu/Assignments/a2.pdf