This article data science blogthon.
prologue
In the previous article, we learned about various blind search algorithms. This is because it provides no information other than the constraints presented in the question. So the algorithm looks to go through different states before reaching the goal state. The drawback of these search strategies is very poor time complexity. Therefore, using these strategies to solve real-world problems is pointless.
This solution can be overcome by providing heuristics such as “experience from exposure” to solve this problem.This gives way to Informed search strategyThese algorithms promise solutions and can solve complex problems quickly. It also reduces time complexity.
The Informed Search strategy uses several heuristic functions to select nodes and ensure the most promising way to reach the goal. The most common way to give search problems more information about the problem is to heuristic function. This is an estimate of the cost to reach the goal state from a given node n. Any problem-specific function can be used (arbitrary and non-negative). H(n) = 0 if n is the goal node.
Two informed search strategies presented in this article are:
- Best First Search Algorithm
- A* Search Algorithm
Best First Search Algorithm
Informed BFS follows a greedy approach for state transitions to reach their goal. For every node here we maintain a merit function (f(n)) that provides cost estimates. The idea is to grow the node with the smallest f(n) each time. The evaluation function here has a heuristic function h(n) component.i.e.
f(n) = h(n)
So the node that seems closest to the goal is expanded. The implementation of this algorithm is done using a priority queue ordered by each node’s merit function. Pseudocode for the same would be:
function Best_First_Search(problem)
{
node = problem.initial_state;
frontier = priority queue with node as the only element
explored = empty set
loop(until goal state is found)
if(frontier == empty)
return failure
node = frontier.pop()
add node to explored_set
if(node == problem.goal_state)
return path from Initial state up to the node
else
generate successors of the node
if(successors not in frontier and not in explored_set)
add successor to the priority queue
end loop
}
Best-first search algorithm properties:
Perfect: No. You may get stuck in a loop.
space complexity: O(b^m)
time complexity: O(b^m) (but good heuristics can improve significantly.)
Optimal: No
(b is the branching factor and m is the maximum depth of the search space.)
A* Search Algorithm
The A* search strategy is one of the most widely used strategies as it guarantees the best solution. The idea is to avoid extending paths that are already expensive. For the same reason as Best-FS, it uses an evaluation function (f(n)) to evaluate every node (state) in the path.
f(n) = g(n) + h(n)
where g(n) is the actual cost from the initial state to the current node.
h(n) is the estimated cost from the current node to the goal state.
* The algorithm succeeds in finding the shortest distance path of the problem faster. Therefore, it is the most widely accepted solution for state-space search. The optimality of the A* search solution depends on the permissiveness of the chosen heuristic function. More on this later.
A* search strategy algorithm
step 1: Initialize an empty set (explored). Initialize a priority queue (frontier) ordered by the node’s merit function. Add a node (initial state) to the queue with the evaluation function f(start) = 0+h(start) …………..(g(start)=0) .
step 2: loop until goal is found – returns failure if frontier is empty. Otherwise, pop the node with the lowest merit function (best_node) from the frontier. Add best_node to the explored set. Check if best_node is the goal state. If yes, return the solution. Otherwise, generate a successor.
Step3: for all generated successors,
3.1Action: Set successor to point to best_node. (These backlinks help find the solution path from the initial state to the final goal state.)
3.2: Compute the actual cost of the successor. That is, compute the actual cost from g(successor) = g(best_node) + best_node to the successor.
3.3: If the successor node is already in the forefront (i.e. there is already a path to reach this node), we call it old_node.
3.4Action: Add old_node to best_node’s list of successors. Now compare the actual cost of reaching old_node via the previous path (g(n)) with the current new path (i.e. via best_node).
3.5: continue if old pass is cheaper. Otherwise, update old_node’s parent link to point to best_node and update old_node’s evaluation function.
3.6: If a successor exists in explored (i.e. has visited this node before), we call it old_node. Repeat steps 3.4 and 3.5 to see if you get a new better path. This improvement should be propagated to successors of old_node.
3.7: If the successor is neither in the frontier nor in the quest set, add it to the frontier. Put it on the list of successors to best_node. Calculate its merit function.
(f(successor) = g(successor) + h(successor))
The time complexity of this algorithm is b^d.
The spatial complexity of this algorithm is b^d.
(where b is the branching factor of the tree and d is the depth of the solution node.)
The optimality of the solution depends on the allowed heuristics. So what is an acceptable heuristic?
Tolerance heuristic
A heuristic function h(n) is acceptable if h(n) is less than or equal to g(n) for all nodes. (where g(n) is the actual cost of reaching the goal state). The admissible heuristic therefore does not overestimate the cost of reaching the goal. Always optimistic about finding the optimal path to the goal node. If h(n) is allowed by the A* algorithm, then we have the optimal solution to the problem.
If there are two admissibility functions (h1 and h2) such that h2(n) ≥ h1(n), then h2 dominates h1.
Conclusion
In this essay, you learned about two methods of informed search strategy. A heuristic function provides more information about the problem to an informed search strategy. We observed both tactics: Best-First Search and A* Search algorithms. According to their attributes, the A* algorithm is the most effective search strategy among all informed and uninformed search strategies.
In future articles, we will learn about state-space search local search algorithms and constraint satisfaction problems.If you like my articles, connect with me on Linkedin here.
Media shown in this article are not owned by Analytics Vidhya and are used at the author’s discretion.
