AI mod 2 Flashcards
Brief definition for A* algorithm
It is a searching algorithm that is used to find the shortest path between an initial and a final point.
It is a handy algorithm that is often used for map traversal to find the shortest path to be taken. A* was initially designed as a graph traversal problem, to help build a robot that can find its own course. It still remains a widely popular algorithm for graph traversal.
Is A* optimal algorithm ?
It searches for shorter paths first, thus making it an optimal algorithm. An optimal algorithm will find the least cost outcome for a problem
Is A* a complete algorithm ?
Yes, a complete algorithm finds all the possible outcomes of a problem.
By using which data structure, A* algorithm is implemented ?
Another aspect that makes A* so powerful is the use of weighted graphs in its implementation. A weighted graph uses numbers to represent the cost of taking each path or course of action. This means that the algorithms can take the path with the least cost, and find the best route in terms of distance and time.
What is the drawback of A* algorithm ?
A major drawback of the algorithm is its space and time complexity. It takes a large amount of space to store all possible paths and a lot of time to find them.
What is the basic concept of A* algorithm ?
A heuristic algorithm sacrifices optimality, with precision and accuracy for speed, to solve problems faster and more efficiently.
All graphs have different nodes or points which the algorithm has to take, to reach the final node. The paths between these nodes all have a numerical value, which is considered as the weight of the path. The total of all paths transverse gives you the cost of that route.
Initially, the Algorithm calculates the cost to all its immediate neighboring nodes,n, and chooses the one incurring the least cost. This process repeats until no new nodes can be chosen and all paths have been traversed. Then, you should consider the best path among them. If f(n) represents the final cost, then it can be denoted as :
f(n) = g(n) + h(n), where :
g(n) = cost of traversing from one node to another. This will vary from node to node
h(n) = heuristic approximation of the node’s value. This is not a real value but an approximation cost
Breif definition for AO* algorithm
AO* Algorithm basically based on problem decompositon (Breakdown problem into small pieces)
When a problem can be divided into a set of sub problems, where each sub problem can be solved separately and a combination of these will be a solution, AND-OR graphs or AND - OR trees are used for representing the solution.
The decomposition of the problem or problem reduction generates AND arcs.
A* Vs AO*
Are both informed search algorithms ?
Both are part of informed search technique and use heuristic values to solve the problem.
A* Vs AO*
Is solution guaranteed in both the algorithms ?
The solution is guaranteed in both algorithm.
A* Vs AO*
Is optimal solution is guaranteed in both of them ?
A* always gives an optimal solution (shortest path with low cost) But It is not guaranteed to that AO* always provide an optimal solutions.
Why AO* doesn’t give optimal solution ?
Because AO* does not explore all the solution path once it got solution.
