Download to read offline
Informed search algorithm.pptx power poi
- 1.
- 2. • Informed searchalgorithms, also known as heuristic search algorithms, are an essential component of Artificial Intelligence (AI). • These algorithms use domain-specific knowledge to improve the efficiency of the search process, leading to faster and more optimal solutions compared to uninformed search methods. • By incorporating heuristics, informed search algorithms can make educated guesses about which paths to explore in a search space, ultimately reducing the time and computational resources required to find a solution.
- 3. • Key Characteristicsof Informed Search Algorithms 1.Heuristic Function: Informed search algorithms use a heuristic function h(n) that provides an estimate of the minimal cost from node n to the goal. This function helps the algorithm to prioritize which nodes to explore first based on their potential to lead to an optimal solution. 2.Efficiency: By focusing on more promising paths, informed search algorithms often find solutions more quickly than uninformed methods, especially in large or complex search spaces. 3.Optimality and Completeness: Depending on the heuristic used, informed search algorithms can be both optimal and complete. An algorithm is complete if it is guaranteed to find a solution if one exists, and it is optimal if it always finds the best solution.
- 4. • Greedy Best-FirstSearch • Greedy Best-First Search is a heuristic-driven algorithm that prioritizes the exploration of nodes based on their estimated cost to the goal. The algorithm selects the node that appears most promising according to a heuristic function h(n)h(n), which estimates the cost from node nn to the goal. • How Greedy Best-First Search Works? • Greedy Best-First Search works by evaluating the cost of each possible path and then expanding the path with the lowest cost. This process is repeated until the goal is reached. • The algorithm uses a heuristic function to determine which path is the most promising. • The heuristic function takes into account the cost of the current path and the estimated cost of the remaining paths. • If the cost of the current path is lower than the estimated cost of the remaining paths, then the current path is chosen. This process is repeated until the goal is reached.
- 5. EXAMPLE: BEST-FIRST SEARCH Q.HereC is the initial or source node and L and Z are goal nodes. Open: C Closed: —
- 6. Now, C isadded to Closed, and B, T, O, E and P are added to Open. Open: T, O, E, B, P Closed: C
- 7. Now, Thas the least distance hence, T is added to Closed. Open: O, E, B, P Closed: C, T
- 8. As Tdoes not have any successors, the next node from open that is O is removed from Open and added to closed. Open: E, B, P Closed: C, T, O
- 9. The successorsof node O that is node I and N are added to Open. Open: I, E, B, P, N Closed: C, T, O
- 10. Now, nodeI is removed from Open and added to closed. Open: E, B, P, N Closed: C, T, O, I
- 11. The successorof I that is Z is added to Open. Open: Z, E, B, P, N Closed: C, T, O, I
- 12. Now, nodeZ is removed from Open and added to closed. Open: E, B, P, N Closed: C, T, O, I, Z The Goal is found. The final path is C – O – I – Z.
- 13. • Advantages ofGreedy Best-First Search: • Simple and Easy to Implement: Greedy Best-First Search is a relatively straightforward algorithm, making it easy to implement. • Fast and Efficient: Greedy Best-First Search is a very fast algorithm, making it ideal for applications where speed is essential. • Low Memory Requirements: Greedy Best-First Search requires only a small amount of memory, making it suitable for applications with limited memory. • Flexible: Greedy Best-First Search can be adapted to different types of problems and can be easily extended to more complex problems. • Efficiency: If the heuristic function used in Greedy Best-First Search is good to estimate, how close a node is to the solution, this algorithm can be a very efficient and find a solution quickly, even in large search spaces.
- 14. • Disadvantages ofGreedy Best-First Search: • Inaccurate Results: Greedy Best-First Search is not always guaranteed to find the optimal solution, as it is only concerned with finding the most promising path. • Local Optima: Greedy Best-First Search can get stuck in local optima, meaning that the path chosen may not be the best possible path. • Heuristic Function: Greedy Best-First Search requires a heuristic function in order to work, which adds complexity to the algorithm. • Lack of Completeness: Greedy Best-First Search is not a complete algorithm, meaning it may not always find a solution if one is exists. This can happen if the algorithm gets stuck in a cycle or if the search space is a too much complex.