Beefy Boxes and Bandwidth Generously Provided by pair Networks
XP is just a number

Re: OT(ish) - Best Search Algorithm

by Melly (Hermit)
on Oct 15, 2007 at 15:48 UTC ( #644968=note: print w/replies, xml ) Need Help??

in reply to OT(ish) - Best Search Algorithm

Wow. It's a while since I visited perlmonks, and now I'm wondering why. "Cycle detection" it is.

Needless to say, I haven't been slacking, and I quickly realised that my problem is not really about finding shortest paths in a known graph, but is more about building the graph and then looking for any valid path.

I think the approach I'm going to take is this (mainly via sql via perl):

  • Pick 1st friend (n)
  • Get list of friends that I know but n doesn't (these will be the target end-points)
  • Put mutual friends of me and n in a temporary ignore table
  • Check n's friends for a match with target list (will always fail on first iteration)
  • Store n->n's friends in a temporary table with level 1 code since we're at the first iteration
  • Now check n's friends friends for a match with my target list, storing them as level 2
  • Don't bother checking anyone who is already in the table (i.e. avoid going round in circles)
  • Keep going like this until we either find one of our targets or hit the max iterations (e.g. no more than 10 hops)
  • If a match is found, use the table to work out the route
  • If no match was found, but we ran out of iterations, move to next friend and start again, but ignore anyone we checked via the first friend

Of course, this could get pretty silly - if, on average, everyone has about 15 friends, then I'm going to be checking a lot of pathways - that guy with the chessboard and the rice ain't got nothing on me...

map{$a=1-$_/10;map{$d=$a;$e=$b=$_/20-2;map{($d,$e)=(2*$d*$e+$a,$e**2 -$d**2+$b);$c=$d**2+$e**2>4?$d=8:_}1..50;print$c}0..59;print$/}0..20
Tom Melly, pm (at) cursingmaggot (stop) co (stop) uk

Replies are listed 'Best First'.
Re^2: OT(ish) - Best Search Algorithm
by perlfan (Curate) on Oct 15, 2007 at 16:37 UTC
    >Wow. It's a while since I visited perlmonks, and now I'm wondering why.

    haha - yeah...there are many monks who lurk around for a shot at problems just like this :)

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://644968]
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others about the Monastery: (8)
As of 2018-06-20 19:32 GMT
Find Nodes?
    Voting Booth?
    Should cpanminus be part of the standard Perl release?

    Results (117 votes). Check out past polls.