Re: [Sheflug] Weird algorithm question

[Alex Hudson <home@xxxxxxxxxxxxxx>]

On 25/06/10 16:37, Adam Funk wrote:
> I also posted this to the corpora mailing list (related to natural
> language processing) and got some interesting suggestions about graph
> search algorithms.
>    

Yeah; thinking about it, it's not really travelling salesman because 
you're looking for the longest route, not the longest route visiting all 
nodes (as I understand the problem, anyway).

Thinking about this, there ought to be some MapReduce magic you could 
work here. If there are "loops" where you have start and end nodes with 
multiple "routes" between them but only two vertices per node, e.g.:

--A--C--E--T--B--
    \----F--G----/

.. then you can automatically throw away the A->F->G->B route because 
it's never going to be part of any longest route.

I don't know how much of that kind of pruning you can actually do, but I 
would have thought that could help cut down the search space pretty 
usefully.

It's still going to be a pretty crazy complex problem to solve tho ;)

Thanks

Alex

_______________________________________________
Sheffield Linux User's Group
http://sheflug.org.uk/mailman/listinfo/sheflug_sheflug.org.uk
FAQ at: http://www.sheflug.org.uk/mailfaq.html

GNU - The Choice of a Complete Generation