Re: OT(ish) - Best Search Algorithm

[Melly]

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...

[perlfan]

>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 :)