• 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 #36 Abeer Mahmoud 2018-04-15 01:07
Hello! Do you know if tey make any plugins to protect against hackers?

I'm kinda paranoid about losing everything I've worked
hard on. Any recommendations ?

My blog :: Abeer Mahmoud: https://swrbook.blogspot.com/
Quote
 
 
0 #35 Doaa Hosny 2018-04-14 14:22
Wow, amazing blog layout! How lengthy have you ever been running a blog for?
you make blogging glance easy. The entire glance of your website is great, let alone the content!


Here is my site: Doaa Hosny: https://alf111.blogspot.com
Quote
 
 
0 #34 Manar ahmed 2018-04-13 02:15
Woah! I'm really digging the template/theme of this website.
It's simple, yet effective. A lot of times it's tough to get that "perfect balance" between superb usability and appearance.
I must say you've done a great job with this. Also,
the blog loads very fast for me on Chrome.
Exceptional Blog!

Also visit my web blog Manar ahmed: https://manarahmed.blogspot.com
Quote
 
 
0 #33 Hussin Ahmed 2018-04-08 09:05
Have you ever considered writing an ebook or guest authoring on other websites?

I have a blog based upon on the same ideas you discuss and would really like
to have you share some stories/information. Iknow my visitors would
value your work. If you're even remotely interested, feel
fee to shoot me an e mail.

my website: Hussin Ahmed: https://swrbook.blogspot.com/
Quote
 
 
0 #32 Manar 2018-04-07 20:24
I visited multiple web pages except the audio feature for audio songs present
at this web page is genuinely wonderful.


my blog Manar: https://manarahmed.blogspot.com
Quote
 
 
0 #31 Hussin Ahmed 2018-04-07 08:43
whoah this weblog is great i like reading your posts.
Keep up the great work! You know, lots of people are looking round for this information, you could aid them greatly.


Have a loook at my web-site :: Hussin Ahmed: https://swrbook.blogspot.com/
Quote
 
 
0 #30 Manar AHmd 2018-04-07 00:55
Fastidious answer back in return of this query with genuine arguments and telling the whole thing on the topic of that.


Feel free to surf to my web-site Manar AHmd: https://manarahmed.blogspot.com
Quote
 
 
0 #29 Doaa Hosny 2018-04-06 11:05
Nice post. I used to be checking continuously this weblog
and I am inspired! Very useful info particularly
the closing phase :) I deal with such info a lot. I used
to be seeking this particular information for a very lengthy time.
Thanks and best of luck.

my page - Doaa Hosny: https://swrbook.blogspot.com/
Quote
 
 
0 #28 Buy Lumigan 2018-03-31 19:57
I'm curious to find out what blog platform you happen tto
be utilizing? I'm experiencing some minjor security problems
with my latest website and I would like to find something mode safe.

Do you have any solutions?

Heree is my web site ... Buy Lumigan: https://sites.google.com/site/buylumiganonlineoverthecounter/
Quote
 
 
0 #27 Buy lumigan cheap 2018-03-29 12:38
I'm not sure why but this blog is liading very slow for me.

Is anyone else having this problem or is iit a issue
on my end? I'll check back later aand ssee if the problem still
exists.

Take a look at my wbsite ... Buy lumigan cheap: https://sites.google.com/site/buylumiganonlineoverthecounter/
Quote
 

Add comment

No bad words.


Security code
Refresh


New articles

Differential Equations - Simple spring model Machine Learning and Robotics
Read More 1859 Hits
Kalman Filter implementation Machine Learning and Robotics
Read More 2660 Hits
Inverse kinematics Machine Learning and Robotics
Read More 3314 Hits
gpsim tutorial Machine Learning and Robotics
Read More 8060 Hits

Most read content

New articles

Differential Equations - Simple spring model Machine Learning and Robotics
Read More 1859 Hits
Kalman Filter implementation Machine Learning and Robotics
Read More 2660 Hits
Inverse kinematics Machine Learning and Robotics
Read More 3314 Hits
gpsim tutorial Machine Learning and Robotics
Read More 8060 Hits
Design by i-cons.ch / etosha-namibia.ch