Graph Heuristics - AP Computer Science A Lesson

Learning Objectives

By the end of this lesson, we will be able to:

  • Define graph heuristics and explain their purpose
  • Compare traditional algorithms with heuristic approaches
  • Implement and analyze Greedy Best-First Search
  • Understand the A* algorithm and its mathematical foundation
  • Apply heuristics to solve real-world pathfinding problems Overview of graphs: A graph is a structure made of:
  • Vertices (nodes): Represent entities (like cities, people, or webpages). \
  • Edges (links): Represent relationships or connections (like roads, friendships, or hyperlinks).
    Graphs can model networks of all kinds and are essential in solving problems where entities are connected and movement or influence happens along those connections. Graph Example

    Types of Graphs

  • **Directed vs. Undirected:
    **
    • Directed graphs have arrows (A → B), used in things like web crawlers or dependency management. \
    • Undirected graphs (A—B) are more like roads without one-way restrictions. \
  • **Weighted vs. Unweighted:
    **
    • Weighted graphs assign a “cost” to edges (distance, time, risk). \
    • Unweighted graphs treat all edges as equal. Popcorn Hack #1: A robot is placed at the entrance of a complex maze and must find its way to the exit as efficiently as possible. The maze is laid out on a grid, with walls blocking certain paths. The robot can move one step at a time in the four cardinal directions (up, down, left, right), and each movement takes the same amount of time.
      1. What are the nodes and edges in the graph that models this maze? \
      2. Is the graph directed, undirected, weighted, or unweighted? Why?

        Introduction to Graph Heuristics

        Graph heuristics are estimation-based strategies used to solve graph problems efficiently when finding an exact solution would be computationally expensive or time-consuming. Unlike traditional algorithms that guarantee optimal solutions, heuristics prioritize speed and practicality by making educated guesses about the best path forward.

        Key Concept: Heuristic = Estimation

        A heuristic function estimates the cost or distance from a current state to the goal. It doesn’t guarantee accuracy but provides a reasonable approximation to guide decision-making.

        Real-World Applications

        GPS Navigation Systems

        When you request directions from point A to point B, your GPS doesn’t examine every possible route (which could take hours for complex road networks). Instead, it uses heuristics to estimate which roads are most likely to lead to faster routes, considering factors like:

  • Straight-line distance to destination
  • Speed limits on different road types
  • Historical traffic patterns

    Social Network Analysis

    Platforms like Facebook and LinkedIn use graph heuristics to:

  • Suggest friends based on mutual connections
  • Group users into communities
  • Recommend content based on network proximity

    Task Scheduling and Project Management

    Project management software uses heuristics to:

  • Organize task dependencies
  • Estimate project completion times
  • Allocate resources efficiently

    Traditional vs. Heuristic Approaches

    Dijkstra’s Algorithm (Traditional)

    Dijkstra’s algorithm is a systematic, exhaustive search that:b

  • Explores all possible paths in order of increasing cost
  • Guarantees the optimal solution
  • Does NOT use estimation - it calculates exact distances
  • Time complexity: O((V + E) log V) where V = vertices, E = edges

    The Problem with Traditional Methods

    For large graphs (like road networks with millions of intersections), Dijkstra’s algorithm becomes impractical because it must explore too many possibilities.

    Common Graph Heuristics

    Greedy Best-First Search makes decisions based solely on the heuristic estimate to the goal, ignoring the actual cost traveled so far. It is “greedy” because it focuses on immediate gains rather than exploring all possible paths.

    Mathematical Foundation

  • Heuristic Function h(n): Estimates cost from node n to goal
  • Selection Criteria: Always choose the node with the smallest h(n) value
  • Trade-off: Speed vs. optimality (may not find the best path)

    Example: Manhattan Distance Heuristic

    For grid-based pathfinding, the Manhattan distance serves as an excellent heuristic: h(current) = |current.x - goal.x| + |current.y - goal.y|

    Greedy Best-First Analysis

  • Time Complexity: O(b^d) where b = branching factor, d = depth
  • Space Complexity: O(b^d)
  • Optimality: Not guaranteed - may find suboptimal paths
  • Completeness: May get stuck in infinite loops without proper cycle detection

    2. A* Algorithm (A-Star)

    A* combines the best of both worlds: the systematic approach of Dijkstra’s with the efficiency of heuristic guidance.

    Mathematical Foundation

    A* uses two key functions:

  • g(n): Actual cost from start to node n
  • h(n): Heuristic estimate from node n to goal
  • f(n) = g(n) + h(n): Total estimated cost of path through n

    The A* Selection Process

    A* always selects the node with the lowest f(n) value, balancing actual cost with estimated remaining cost. How much it’s cost so far + how much more you *think *it will cost

    A* Analysis

  • Time Complexity: O(b^d) in worst case, but typically much better
  • Space Complexity: O(b^d)
  • Optimality: Guaranteed if heuristic is admissible (never overestimates)
  • Completeness: Yes, will find a solution if one exists Popcorn Hack #2: Using the same situation for popcorn hack #1, would you choose A* or Greedy Best-First Search to guide the robot? Why?

    Heuristic Functions Deep Dive

    Requirements for Good Heuristics

    1. Admissibility

    A heuristic h(n) is admissible if it never overestimates the actual cost to reach the goal. h(n) ≤ actual_cost(n, goal) for all nodes n

    2. Consistency (Monotonicity)

    A heuristic is consistent if for every node n and successor n’: h(n) ≤ cost(n, n’) + h(n’)

    Common Heuristic Functions

    Manhattan Distance (L1 Norm)

    public static int manhattanDistance(int x1, int y1, int x2, int y2) { return Math.abs(x1 - x2) + Math.abs(y1 - y2); } Use Case: Grid-based movement (4-directional)

    Euclidean Distance (L2 Norm)

    public static double euclideanDistance(int x1, int y1, int x2, int y2) { return Math.sqrt(Math.pow(x1 - x2, 2) + Math.pow(y1 - y2, 2)); } Use Case: Free movement in continuous space

    Chebyshev Distance (L∞ Norm)

    public static int chebyshevDistance(int x1, int y1, int x2, int y2) { return Math.max(Math.abs(x1 - x2), Math.abs(y1 - y2)); } Use Case: 8-directional movement (including diagonals)

    Worked Example: Pathfinding Comparison

    Consider finding a path in a 5x5 grid from (0,0) to (4,4) with obstacles: Grid: S . . . . . X X . . . X . . . . . . X . . . . . G S = Start (0,0) G = Goal (4,4) X = Obstacle . = Open space

    Dijkstra’s Approach

    Dijkstra’s would explore nodes in this order (by actual distance):

    1. (0,0) - distance 0
    2. (1,0), (0,1) - distance 1
    3. (2,0), (0,2) - distance 2
    4. And so on… Nodes explored: ~20-25 nodes Path found: Optimal path with cost 8

      Greedy Best-First Approach

      Using Manhattan distance heuristic:

    5. Start at (0,0), h = 8
    6. Neighbors: (1,0) h=7, (0,1) h=7
    7. Choose (1,0), then (2,0) h=6
    8. Continue toward goal… Nodes explored: ~8-10 nodes Path found: May not be optimal

      A* Approach

      Using f(n) = g(n) + h(n):

    9. Start: (0,0) f=0+8=8
    10. Expand (0,0): neighbors (1,0) f=1+7=8, (0,1) f=1+7=8
    11. Choose efficiently based on combined cost Nodes explored: ~12-15 nodes Path found: Optimal path with cost 8

      Performance Analysis

      Time Complexity Comparison

Algorithm Best Case Average Case Worst Case
Dijkstra's O(V log V) O((V+E) log V) O((V+E) log V)
Greedy Best-First O(b^d) O(b^d) O(b^d)
A* O(b^d) O(b^d) O(b^d)

Where:

  • V = number of vertices
  • E = number of edges
  • b = branching factor
  • d = depth of solution

    Space Complexity

    All three algorithms have similar space complexity of O(V) for storing the frontier and visited sets.

    Homework Questions

    Multiple Choice

    1. What is the primary difference between Dijkstra’s algorithm and heuristic search methods? a) Dijkstra’s is faster b) Dijkstra’s guarantees optimal solutions but doesn’t use estimation c) Heuristic methods always find better paths d) There is no significant difference \
    2. Which heuristic function is most appropriate for 4-directional grid movement? a) Euclidean distance b) Manhattan distance c) Chebyshev distance d) Squared Euclidean distance

      Short Answer

    3. Explain why A* is often preferred over Greedy Best-First Search for pathfinding applications. \
    4. Calculate the Manhattan distance heuristic for moving from point (2,3) to point (7,1).

      Programming Problems

    5. Implement a method that compares the performance of Dijkstra’s algorithm vs A* on a given grid. \
    6. Design a heuristic function for a pathfinding problem where movement costs vary (e.g., different terrain types have different movement costs).

      Summary

      Graph heuristics represent a fundamental trade-off in computer science between optimality and efficiency. While traditional algorithms like Dijkstra’s guarantee optimal solutions, heuristic methods like Greedy Best-First Search and A* provide practical solutions for large-scale problems by using estimation to guide their search. Key takeaways:

  • Heuristics are estimations that help guide search algorithms
  • *A balances optimality and efficiency** by combining actual cost with estimated cost
  • The choice of heuristic function significantly impacts performance
  • Real-world applications require careful consideration of trade-offs between speed and accuracy Understanding these concepts prepares students for advanced topics in artificial intelligence, game development, robotics, and large-scale system optimization.