SEARCHING ALGORITHMS-II

Question 1

What’s the formula of A* Algorithm

Answer 1

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

g(n) –> Actual cost of that node
h(n) –> Estimated cost from the node to goal

Question 2

Explain A* Algorithm

Answer 2

A* Algorithm is the most refined version of the best first search Algorithm.
This algorithm maintains a priority queue, where the values of f(n) = g(n) + h(n) is stored.
The lowest value is then traversed.

Question 3

Explain the type of Heuristic function used

Answer 3

The heuristic is an admissible heuristic. An admissible heuristic h(n) is a heuristic that always underestimates the cost to reach the goal.

Question 4

What is Adversarial Search

Answer 4

This is the type of problem where we examine the problem and try to move ahead of the world and the other agents are planning against us.

The environment with more than one agent is termed as multi agent env, in this each agent is an opponent to the other agent. Each agent needs to consider the action of the other agent and has to see it’s affect on them.

Question 5

Explain Mini Max Algorithm

Answer 5

This is a backtracking algorithm which is used in decision making and game theory.
In this algorithm there are two players, max and min. Max tries to maximise the utility of an agent, and Min will try to minimise the utility of the same agent.
This algorithm works on Depth First Search.

Time Complexity –> b^d

Question 6

Explain Alpha Beta Pruning

Answer 6

This is an optimised method of mini max algorithm. In this technique we can compute the correct minimax decision without checking each node, this is achieved by pruning.

Alpha –> The best choice (Highest Value) we have found so far. This can be used by Maximiser.
Beta –> The best choice (Lowest Value) we have found so far. This can be used by Minimiser.

Question 7

Worst and Average time complexity of Alpha Beta Pruning

Answer 7

Worst –> b^d
Average –> b^(d/2)