Beefy Boxes and Bandwidth Generously Provided by pair Networks
Do you know where your variables are?
 
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 romping around the Monastery: (16)
As of 2015-07-06 14:34 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    The top three priorities of my open tasks are (in descending order of likelihood to be worked on) ...









    Results (75 votes), past polls