FIFA-2022 Career Guide Free Tutorials Go to Your University Placement Preparation 
0 like 0 dislike
3.7k views
in VTU B.Tech (CSE-VII Sem) Artificial Intelligence and Machine Learning Lab by Goeduhub's Expert (3.1k points)
edited by
Implement A* Search algorithm.

1 Answer

0 like 0 dislike
by Goeduhub's Expert (3.1k points)
edited by
 
Best answer

A* Search Algorithm

  1. As we know, Human is a wanderer.He uses many routes to get from one place to another.

  2. Since ancient times, humans used to apply a lot of calculation to  choose a optimal path for destination. Like time, cost, long and short paths.

  3. Actually A* is a  part of informed search techniques(Algorithms) in Artificial Intelligence.
  4. Before moving on Informed search algorithm let's understand search technique first.
  5. In the olden times it was very difficult to find the right path. today, we have algorithms that can help us find the shortest paths virtually. We just need to add costs (time, money etc.) to the graphs or maps and the algorithm finds us the path that we need to take to reach our destination as quick as possible.This is what a search algorithm do.
  6. Search Algorithm divided into two parts informed search and uninformed search or blind.
  7. Here we are discussing Informed Search Algorithm.
  8. Informed search algorithm contains an array of knowledge such as how far we are from the destination, path cost, how to reach to destination node, etc. 
  9. A* algorithm is a type of  Informed Search Algorithm.
  10. A* mostly known for its completeness, optimality, and optimal efficiency.Meaning it's sure that A* will  find all  route from source  to destination , with least cost.
  11. Since It is A* is best and popular technique used in path-finding and graph traversals. It is used many computer games and web-map.

How A* is actually work

     F(n) = G(n) + H(n)

A*  Algorithm use this formula to provide a optimal path

Here 

n-node (in current state)

F- Least cost from source (start node ) to the destination (goal node)

G-Actual cost from start node to n node.

H-Estimated cost from n node to the Goal node (heuristic value of node).

In the above diagram, we see two paths to go from source to Goal. From both, we should take the path of minimum cost.

H- Values shows in green color are heuristic/ estimated  value of the nodes. (Generally heuristic value of the goal is zero.)

Note: The heuristic function is a way to inform the search about the direction to a goal. It provides an informed way to guess which neighbor of a node will lead to a goal. 

G- values in maroon color shows actual cost between nodes.

Let's calculate formula and see the values 

F(S)= 0 + 5 =5  , F(S-A) =3 +4 =7     and   F(S-B) = 4+5 = 9  

As we can see the path (S-A) is less costly than path (S-B)we will take it.

F(S-A-G) = 3+10+0 =13    and  F(S-B-G) = 4 + 2 +0 = 6 

From the given example we can say that our path will we F(S-B-G). In this way we find optimal path to destination.

For Practical implementation of Algorithm Click Here 

Learn & Improve In-Demand Data Skills Online in this Summer With  These High Quality Courses[Recommended by GOEDUHUB]:-

Best Data Science Online Courses[Lists] on:-

Claim your 10 Days FREE Trial for Pluralsight.

Best Data Science Courses on Datacamp
Best Data Science Courses on Coursera
Best Data Science Courses on Udemy
Best Data Science Courses on Pluralsight
Best Data Science Courses & Microdegrees on Udacity
Best Artificial Intelligence[AI] Courses on Coursera
Best Machine Learning[ML] Courses on Coursera
Best Python Programming Courses on Coursera
Best Artificial Intelligence[AI] Courses on Udemy
Best Python Programming Courses on Udemy

 Important Lists:

Important Lists, Exams & Cutoffs Exams after Graduation PSUs

 Goeduhub:

About Us | Contact Us || Terms & Conditions | Privacy Policy ||  Youtube Channel || Telegram Channel © goeduhub.com Social::   |  | 

 

Free Online Directory

...