From: Gavin Kistner <gavin@...>
Date: 2005-05-11T22:27:37+09:00
Subject: Re: Representing Undirected Edges (advice, please)

On May 10, 2005, at 1:38 PM, Greg Millam wrote:
> As far as we are concerned, there's only one effective connection from
> each edge to the other: the shortest song. You will never go back to
> that node, you will never need to traverse a second song from that  
> node
> to another particular node. And in no instance will a costlier
> connection ever be considered over a cheaper connection connecting the
> two same nodes.

That's one particular solution to the Barrel of Monkeys quiz, and one  
particular type of path that may be desirable.

I understand the benefits of optimizations like Djikstra's algorithm  
and adjacency matrices, but (to be clear) there are certainly  
pathfinding cases where short/early optimizations do not apply.

For example, consider the Barrel of Monkeys quiz 'extra credit' part  
to find a playlist as close to a specific duration as possible. Or  
consider a desire to find a path where the mean song length is as  
close to 5:00 as possible.

Both of these lead towards bin-packing type problems (and hence  
really, really slow solutions) but if that's what you need, that's  
what's you need.


I'm very much enjoying reading the discussion in this thread, and  
eventually plan to implement optimizations where possible in my  
library. But my initial goal is to create a library that lets you  
specify any conceivable criteria for the path you want, and provide  
hints as to how to find it.