[OT] Quiz of the Day [2008-11-04]

[Chris Wright]

Sean Kelly Wrote:
> This sounds like a job for Dijkstra's algorithm!  The easiest solution 
> would be to simply exclude the individuals who are above tether capacity 
> and run the algorithm on the rest.  However, this doesn't account for 
> groups of low-weight individuals would could all be tethered together. 
> For that, the best I've come up with so far is to do a best-fit sort on 
> the people to determine optimal grouping for tether loads and then 
> iteratively run Dijkstra's algorithm using that information to determine 
> the proper path to take.  But the iterative part is bothering me and I'm 
> sure there's a better solution.
> 
> Perhaps use Floyd's algorithm and make edges between group members 
> bidirectional and edges between single person tether loads bidirectional 
> but have edged from single-person loads to group loads unidirectional 
> into the group and unidirectional out of the group?  Then to keep the 
> groups together, every edge out of a group would have to have a 
> relatively high cost in order to prevent the tether from grabbing a 
> single group member and then moving on to someone outside the group, 
> then later returning for another group member.  I hope that makes sense :-p

I explicitly don't want to take people who are close together. I want them evenly spaced, so I can get an even coverage of each race, religion, et cetera.

The guy on the tether is just there so you can pass someone and grab them later, but you can only keep track of one.

The original problem relates to a cache-oblivious lookahead array ( http://portal.acm.org/citation.cfm?id=1248393 ). Specifically, the problem is fractional cascading with variable length elements.