Try   HackMD

Week 2c - Informed Search

Source: Lecture Video

Outline & Objectives

  • Learn about two different informed search algorithms
    • Greedy Best-First Search
    • A* Search
  • Understand the role that heuristic plays in these algorithms
  • Being able to use Greedy Best-First Search and A* Search to solve a search problem
  • UCS: Expand unexpanded node n with the lowest path cost g(n). Formally, this is via an evaluation function f(n) = g(n).
  • UCS Implementation: Use a priority queue ordered by path cost g(n).
  • Evaluation function f(n)
    • For UCS, path cost measures how far a node is from the initial state
    • Is this effective? Does a shorter path from the initial state mean we're nearer to the goal state?
    • Path cost ignores direction. This might lead to a lot of redundant searches.

Heuristics

Definition: A rule of thumb, simplification, or educated guess that reduces or limits the search for solutions in domains that are difficult and poorly understood.

Heuristic function h(n)

  • The heuristic function h(n) is an estimate of how close a state n is to the goal state.
  • Informed search algorithms use heuristics to solve the search problem.
  • There are good and bad heuristics

In the Romania Holiday example, the straight line distances to the Goal state could be used as the heuristic function.

  • General Idea: Expand the node n with the lowest heuristic h(n)
  • Implementation: use a PQ ordered by heuristic h(n).
    • Evaluation function f(n) = h(n)

Steps

  1. The initial state (Arad). Queue: A
  2. After expanding Arad: Queue: Sibiu, Timisoara, Zerind, Arad (lowest heuristic first)
  3. After expanding Sibiu: Queue: F,R,S,T,A,Z,O,A. Since A is already in the queue, it will not be added anymore.

Properties

  • Completeness: No (can get stuck in the loop, unless the repeated states are kept track of)
  • Optimality: No (GBFS uses heuristic instead of real path cost rather than metrics)
  • Time complexity:
    O(bm)
    (Similar to DFS but a good heuristic can improve the performance greatly)
  • Space complexity:
    O(bm)
    (keeps all nodes in memory)

Exercise: UCS vs GBFS

  • What are the issues with UCS in contrast to greedy search?
    • Complete and optimal but may "waste" search in the wrong direction.
  • What are the issues with GBFS, in contrast to UCS?
    • Search generally in the "right" direction but not complete or optimal
  • Is there a way to combine the two and address each's shortcomings?
    • UCS: f(n) = g(n)
    • Greedy: f(n) = h(n)
    • Combined: f(n) = g(n)+h(n)
  • General idea: Expand the node n that has incurred the least cost and is nearest to the goal state.
  • Implementation: using a priority queue ordered by evaluation function f(n)
    • Evaluation function f(n) = g(n)+h(n)
    • Path cost g(n) = total path cost from start node to node n
    • Heuristic h(n) = estimated distance from node n to goal state.

Property

  • Completeness: Yes
  • Optimality: Yes (if heuristics are admissible/consistent)
  • Time complexity: Same as UCS
  • Space complexity: Same as UCS