• Increase font size
  • Default font size
  • Decrease font size

A* search algorithm

The algorithm is widely used in path-finding and graph traversal problems. It is an extension of Edsger Dijkstra's algorithm (1959). A* achieves better performance (with respect to time) by using heuristic function.

 

Peter Hart, Nils Nilsson and Bertram Raphael of Stanford Research Institute (now SRI International) described the algorithm in 1968.

It is a best-search first algorithm (best-search first alg. is estimating the promise of node n by a function f(n) tha is actually "heuristic evaluation function" f(n), so f(n) = h(n) ).

A* algorithm uses f(n) as well but it consits of two parts:

1. cost function to the node = known distance from the starting node to the current node 'n' - usually denoted g(n)

2. a future path-cost, which is an admissible "heuristic estimate" of the distance from the current node 'n' to the goal - usually denoted h(n)

Then f(n) = g(n) + h(n)

 

Demo

The demo below demonstrates how A* algorithm works. There are 2 grey rectangles. The left one is the start position and the right one is the position we want to get. Obviously there are also obstacles between them so the algorithm has to find the way around them.

 

 

Comments  

 
0 #19 massage lyon 2017-04-19 14:11
De 1680 a 1700, le magistrat eleva devant la tour un batiment a la moderne, faisant
face a la place, surmonte, aux deux ailes, de deux petites
lanternes, ou belvederes, de tres-bon gout, qu'un auteur signale, dans un livre d'architecture,
comme un modele d'elegance.

massage lyon: http://www.sophiechassat.com
Quote
 
 
0 #18 fishing trip 2016-02-23 14:01
Hello, i read your blog occasionally and i own a similar one and i was just wondering if you get a lot of
spam remarks? If so how do you prevent it, any plugin or anything you can advise?

I get so much lately it's driving me mad so any help is very much
appreciated.
Quote
 
 
-1 #17 Pure Muscle X 2015-10-25 18:03
Hello there! I could have sworn I've been to this blog before
but after checking through some of the post I realized
it's new to me. Nonetheless, I'm definitely glad I found it and I'll be bookmarking and checking back often!
Quote
 
 
+1 #16 Xtreme Antler Spray 2015-10-22 03:29
Thanks for the good writeup. It if truth be told used to be
a leisure account it. Glance complicated to more added
agreeable from you! By the way, how can we keep in touch?
Quote
 
 
0 #15 http://www. 2015-10-17 20:15
Hi, the whole thing is going nicely here and ofcourse every one is sharing information, that's actually
good, keep up writing.
Quote
 
 
0 #14 comprarviagraes24. 2015-10-04 18:44
Greetings! I've been reading your web site for a long time now and finally got the bravery to go ahead and
give you a shout out from Humble Texas! Just wanted to mention keep up the excellent
work!
Quote
 
 
0 #13 testo xl supplement 2015-10-02 21:07
Hi there! I just wish to offer you a big thumbs up for the excellent information you have got here on this post.
I'll be coming back to your blog for more soon.
Quote
 
 
0 #12 Erecteen Performance 2015-09-27 16:27
Good way of telling, and good piece of writing to obtain facts concerning my presentation subject matter,
which i am going to deliver in institution of higher education.
Quote
 
 
0 #11 health4u.sk 2015-07-17 03:55
Dotknutá téma je dosť vážna, ale toto je napísané veľmi konkrétne
Quote
 
 
0 #10 restaurants near me 2015-06-27 06:55
This site was... how do I say it? Relevant!! Finally
I've found something which helped restaurants near me on map: http://restaurantsnearme.space.
Many thanks!
Quote
 

Add comment

No bad words.


Security code
Refresh


Design by i-cons.ch / etosha-namibia.ch