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

[Sean Kelly]

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


Sean