Heuristic Search and Function |Artificial intelligence Telugu

The informed search algorithm is more useful for large search space. Informed search algorithm uses the idea of heuristic, so it is also called Heuristic search. Heuristics function: Heuristic is a function which is used in Informed Search, and it finds the most promising path. It takes the current state of the agent as its input and produces the estimation of how close agent is from the goal. The heuristic method, however, might not always give the best solution, but it guaranteed to find a good solution in reasonable time. h(n) is less than h*(n) Here h(n) is heuristic cost, and h*(n) is the estimated cost. Hence heuristic cost should be less than or equal to the estimated cost. the informed search we will discuss two main algorithms which are given below: Best First Search Algorithm(Greedy search) A* Search Algorithm 1.) Best-first Search Algorithm (Greedy Search): Greedy best-first search algorithm always selects the path which appears best at that moment. It is the combination of depth-first search and breadth-first search algorithms. It uses the heuristic function and search. Best-first search allows us to take the advantages of both algorithms. With the help of best-first search, at each step, we can choose the most promising node. In the best first search algorithm, we expand the node which is closest to the goal node and the closest cost is estimated by heuristic function, i.e. f(n)= g(n). Were, h(n)= estimated cost from node n to the goal. The greedy best first algorithm is implemented by the priority queue. Best first search algorithm: Step 1: Place the starting node into the OPEN list. Step 2: If the OPEN list is empty, Stop and return failure. Step 3: Remove the node n, from the OPEN list which has the lowest value of h(n), and places it in the CLOSED list. Step 4: Expand the node n, and generate the successors of node n. Step 5: Check each successor of node n, and find whether any node is a goal node or not. If any successor node is goal node, then return success and terminate the search, else proceed to Step 6. Step 6: For each successor node, algorithm checks for evaluation function f(n), and then check if the node has been in either OPEN or CLOSED list. If the node has not been in both list, then add it to the OPEN list. Step 7: Return to Step 2. Advantages: Best first search can switch between Breadth first search and Depth first search by gaining the advantages of both the algorithms. This algorithm is more efficient than BFS and DFS algorithms. Disadvantages: It can behave as an unguided depth-first search in the worst case scenario. It can get stuck in a loop as DFS. This algorithm is not optimal. Expand the nodes of S and put in the CLOSED list Initialization: Open [A, B], Closed [S] Iteration 1: Open [A], Closed [S, B] Iteration 2: Open [E, F, A], Closed [S, B] : Open [E, A], Closed [S, B, F] Iteration 3: Open [I, G, E, A], Closed [S, B, F] : Open [I, E, A], Closed [S, B, F, G] Hence the final solution path will be: S---- B-----F---- G Time Complexity: The worst case time complexity of Greedy best first search is O(b^m). Space Complexity: The worst case space complexity of Greedy best first search is O(b^m). Where, m is the maximum depth of the search space. Complete: Greedy best-first search is also incomplete, even if the given state space is finite. Optimal: Greedy best first search algorithm is not optimal.