In article <1188375180.739073.276390@[EMAIL PROTECTED]
>,
ivanatora@[EMAIL PROTECTED]
wrote:
> Thank you for your reply.
> I've finally managed to implement BFS in PHP and run it.
> It seems it runs a bit too slow, here are some observations. N-start
> point, SEARCH - end point
[...]
> N: 1
> SEARCH: 3300
> 1->4->7->11->24->162->236->385->485->1082->1710->2777->3300
> 13 NODES away
> 3582 nodes traversed
> TIME: 5.2510550022125 seconds
> ----------------------------------
> Does this responds to the time complexity?
> If so, I'd better try bidi search.
I believe that what you're seeing is the expanding amount of time that
it takes to try all possible paths in a growing world.
* You might try profiling, and seeing if you have some obvious
bottleneck.
* You might try seeing if you can mark links-taken, such that they
aren't re-traversed (I bet this is where you run into a lot of
slowdown.) If I'm right about this, you'll also save much memory.
In a world with < 4000 nodes, 5 seconds is FAR too long to traverse the
tree.
....Although...
Statistics on the average links per node would be helpful, too.
Actually, rather than marking links as taken, mark nodes as visited.
Then, when looking for a "next step", skip going toward nodes already
visited (since you've already been there.) This should give you great
speed improvement.
--
Please take off your pants or I won't read your e-mail.
I will not, no matter how "good" the deal, patronise any business which
sends
unsolicited commercial e-mail or that advertises in discussion newsgroups.
|
