Beefy Boxes and Bandwidth Generously Provided by pair Networks
Perl Monk, Perl Meditation
 
PerlMonks  

Re: Multi-token word chains (was The Threeve Game)

by blokhead (Monsignor)
on Feb 11, 2010 at 00:53 UTC ( #822554=note: print w/ replies, xml ) Need Help??


in reply to Multi-token word chains (was The Threeve Game)
in thread The Threeve Game

FYI: The problem of finding the longest "chain" is NP-complete, even in the case of just 2-word phrases, as can be seen from a reduction from the longest path problem in directed graphs.

Each single word is a vertex, and there is an edge from word A to word B if "A B" is a valid 2-word phrase. A path in the graph corresponds to a "chain" of valid 2-word phrases in this game, and we want to find the longest one.

blokhead


Comment on Re: Multi-token word chains (was The Threeve Game)
Re^2: Multi-token word chains (was The Threeve Game)
by Limbic~Region (Chancellor) on Feb 11, 2010 at 15:46 UTC
    blokhead,
    FYI: The problem of finding the longest "chain" is NP-complete

    Yes, I know which is why I said "Oh, I am pretty sure there is a fairly well known computer science problem hidden within so heuristics solutions are likely necessary." See for instance, Not Quite Longest Path Problem. I am really not interested in someone finding the longest path but someone who can find a long path that is longer than everyone else and examine their heuristic solution.

    Cheers - L~R

Log In?
Username:
Password:

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://822554]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others chanting in the Monastery: (11)
As of 2014-12-18 15:05 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    Is guessing a good strategy for surviving in the IT business?





    Results (56 votes), past polls