JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD B.Tech IV Year EXPERT SYSTEMS Previous Question Paper (December-2023/January-2024 - R18)

Heuristic search techniques are essential in artificial intelligence because they provide a mechanism to solve complex problems where an exhaustive search is computationally infeasible. Their importance is defined by the following factors:

• Efficiency and Performance: By employing a heuristic function, h(n), which estimates the cost from a current state to the goal, these techniques prune the search space. This significantly reduces the time and memory requirements compared to uninformed search methods like Breadth-First Search or Depth-First Search.
• Handling Large State Spaces: In real-world applications such as game playing, pathfinding, or complex scheduling, the number of possible states is often astronomically large. Heuristics allow the system to focus on the most promising paths, making problem-solving tractable within reasonable time limits.
• Informed Decision Making: Heuristics act as a 'rule of thumb' or an educated guess based on domain-specific knowledge. This allows an expert system to prioritize actions that are more likely to lead to an optimal or near-optimal solution.
• Balancing Optimality and Completeness: Many heuristic algorithms, such as A* search, provide a balance between finding the shortest path (optimality) and ensuring a solution is found if one exists (completeness), provided the heuristic is admissible (never overestimates the actual cost).

Blind search strategies, also known as uninformed search, are search algorithms that have no additional information about the distance from the current state to the goal state beyond the problem definition. These strategies explore the search space systematically without any heuristic guidance, relying solely on the order in which nodes are expanded.

Key characteristics and common strategies include:

• Breadth-First Search (BFS): Explores the search tree level by level. It expands the root node first, then all successors of the root, then all successors of those successors. It is complete and optimal for unit step costs, but has high space complexity as it stores all nodes at the current level.
• Depth-First Search (DFS): Explores the deepest node in the current branch of the search tree first. It uses a LIFO (Last-In-First-Out) stack structure. While it is more space-efficient than BFS, it is not guaranteed to find the shortest path and can get stuck in infinite loops in infinite state spaces.
• Uniform Cost Search (UCS): An extension of BFS that expands the node with the lowest path cost g(n). It is optimal and complete provided the step costs are non-negative.
• Depth-Limited Search: A variation of DFS that imposes a fixed depth limit to prevent the algorithm from exploring infinitely deep paths.
• Iterative Deepening Depth-First Search (IDDFS): Combines the space efficiency of DFS with the completeness and optimality of BFS by repeatedly performing depth-limited searches with increasing depth limits.

Blind search is primarily used when the state space is small or when no domain-specific knowledge is available to guide the search process.