Notes on Informed Search Strategies

Informed Search Strategies
  • Definition: Informed search strategies utilize additional knowledge about the search space to optimize the process of finding a goal node, making it more efficient than uninformed search strategies.
Lecture Outline
  • Introduction to Informed Search Strategies
  • Best-first search
  • Greedy best-first search
  • A* search
  • Heuristics
Informed Search vs Uninformed Strategies
  • Uninformed Search Strategies:
    • Search without knowledge of the search space.
  • Informed Search Strategies:
    • Use additional knowledge (e.g., distance to goal).
    • Result in exploring less of the search space.
    • More advantageous in large state spaces due to efficiency.
    • Employ heuristic functions for decision-making.
Heuristic Function
  • Definition: A heuristic function provides estimates of the distance from the current state to the goal, denoted as h(n).
  • Utility: While not guaranteed to yield the best solution, it is effective in finding satisfactory solutions quickly.
Best-First Search
  • Concept:
    • Utilizes an evaluation function f(n) for assessing the desirability of nodes based on heuristics.
  • Strategy: Expand the most promising unexpanded node based on this evaluation.
  • Special Cases: Includes Greedy best-first search and A* search.
Greedy Best-First Search
  • Evaluation Function: f(n) = h(n) (where h(n) is the heuristic estimate).
  • Functionality: Focuses on the node that appears closest to the goal without considering the cost to reach there (i.e., disregards g(n)).
Properties of Greedy Best-First Search
  • Completeness: Not complete; can get stuck in loops.
  • Time Complexity: O(b^m); improvement depends on the heuristic used.
  • Space Complexity: O(b^m); retains all nodes in memory.
  • Optimality: Not optimal.
A* Algorithm
  • Evaluation Function: f(n) = g(n) + h(n)
    • g(n): Cost incurred so far to reach node n.
    • h(n): Estimated cost from n to the goal.
    • Purpose: f(n) gives the estimated total cost from the start to the goal through node n.
Properties of A* Search
  • Completeness: Yes, guarantees a solution if one exists.
  • Time Complexity: O(b^d); dependent on the state space and heuristic.
  • Space Complexity: O(b^d); also retains all nodes in memory.
  • Optimality: Yes, provided the heuristic is admissible.
Admissible Heuristic
  • Definition: A heuristic is admissible if its estimate never overestimates the true cost to reach the goal.
  • Example: For road distances, a heuristic should be the straight-line distance and should remain optimistic.
Admissible Heuristic in 8-Puzzle Problem
  • h1(n): Number of misplaced tiles.
  • h2(n): Total Manhattan distance—sum of horizontal and vertical distances needed for each tile to reach its goal position.
  • Calculating Examples:
    • Misplaced Tiles: h1(S) = 8
    • Total Manhattan Distance: h2(S) = sum of distances of misplaced tiles.
Distance Measures
  • Euclidean Distance:
    • Formula: d(x,y) = √((x2-x1)² + (y2-y1)²)
  • Manhattan Distance:
    • Formula: d(x,y) = |x2-x1| + |y2-y1|
  • Minkowski Distance: d(x,y) = (|x1-x2|^p + |y1-y2|^p)^(1/p).
Practical Examples for Distance Calculations
  • Euclidean Example Calculation:
    • d((2,3),(7,6)) = √((7-2)² + (6-3)²) = 5.83
  • Manhattan Example Calculation:
    • d((2,3),(7,6)) = |7-2| + |6-3| = 8.
Summary of f(n)
  • Formula utilized in algorithms:
    • f(n) = g(n) + h(n)
    • where g(n) represents the cost incurred so far and h(n) is the heuristic estimate to the goal.
  • Important for guiding search strategies effectively towards the goal.