Talk About Network

Google


Register and Login
Nick
Password
Register create new account Sign up is FREE and you can post replies, new topics, bookmark posts and more!
Recover lost password


Gaming > Development Programming Algorithms > Re: Finding sho...
Latest [ Topics | Posts ] Archive Post A New Topic Post a Reply
<< Topic < Post Post 2 of 8 Topic 639 of 680
Post > Topic >>

Re: Finding shortest path into unweighted undirected graph

by Michael Arens <Michael.Arens@[EMAIL PROTECTED] > Aug 25, 2007 at 07:52 PM

> Hello to all!

Hi

> Let's call it the algorithm of two circles. [...]

Actually thats bidirectional breadth-first search:
http://en.wikipedia.org/wiki/Breadth_first_search
http://en.wikipedia.org/wiki/Bidirectional_search

> Please post any comments on that algorithm, especially comments on the
> speed and memory requirements.

Time and memory complexity are exponential in the search depth. (divided 
by 2 in case of your bidirectional search). Thats quite bad, but as long 
as your search space is small enough, it might do the job. Correct me if 
I am wrong, but I don't know of "better" search methods for uninformed 
search.

If you run short of memory you can greatly decrease the memory 
complexity at the cost of slightly increased search time.
The method I'd recommend in that case is called Iterative deepening 
depth-first search:
http://en.wikipedia.org/wiki/Iterative_deepening_depth-first_search

> If you know faster|simplier algorithm I'd like to know.

To improve time and memory complexity you should try to make it a 
problem of informed search, which comes with quite efficient algorithms.

What do these nodes represent? Are they points on a map? Then the 
euclidean distance metric will present a nice heuristic for informed 
search methods. Is it a game like 8-puzzle/sliding-puzzle? Then the sum 
of distances to the goal positions of all tiles is a good choice as 
input heuristic.

Once you found out how to describe "the distance to the goal" you should 
have a look at algorithms for informed search, like A*:
http://en.wikipedia.org/wiki/A%2A

> Best regards, Ivan.

Michael
 




 8 Posts in Topic:
Finding shortest path into unweighted undirected graph
ivanatora@[EMAIL PROTECTE  2007-08-24 14:53:00 
Re: Finding shortest path into unweighted undirected graph
Michael Arens <Michael  2007-08-25 19:52:17 
Re: Finding shortest path into unweighted undirected graph
ivanatora@[EMAIL PROTECTE  2007-08-29 08:13:00 
Re: Finding shortest path into unweighted undirected graph
Miss Elaine Eos <Misc@  2007-08-29 14:01:47 
Re: Finding shortest path into unweighted undirected graph
ivanatora@[EMAIL PROTECTE  2007-08-29 08:29:39 
Re: Finding shortest path into unweighted undirected graph
ivanatora@[EMAIL PROTECTE  2007-08-29 14:40:51 
Re: Finding shortest path into unweighted undirected graph
ivanatora@[EMAIL PROTECTE  2007-08-29 14:41:38 
Re: Finding shortest path into unweighted undirected graph
ivanatora@[EMAIL PROTECTE  2007-08-29 17:02:30 

Post A Reply:
  Go here to Signup

AddThis Feed Button


About - Advertising - Contact - Frequently Asked Questions - Privacy Policy - Terms of Use - Signup

Contact
tan12V112 Sat Jul 26 8:52:34 CDT 2008.