Heuristics for Problem Solving

Overview

Heuristics are problem-solving techniques that use practical, experience-based methods to find solutions more quickly when traditional methods are too slow or fail to provide an exact answer. In computational contexts, heuristics help programs make efficient decisions by providing good enough solutions rather than optimal ones.

Heuristics are particularly useful in complex or large-scale problems where finding the perfect solution would take too long or require too much computational power.

What is a Heuristic?

• Definition: A heuristic is a problem-solving approach that employs a practical method to find a solution quickly, even if it's not the most accurate or optimal.
• Purpose: To improve efficiency by reducing the search space and focusing on promising solutions.
• Example Problems:
  • Pathfinding
  • Optimisation problems
  • Game strategies

How Heuristics Work in Programs

Heuristics guide algorithms to make decisions based on estimates or rules of thumb rather than exhaustive searches.

Example: Pathfinding Using A* Algorithm

Problem: Find the shortest path between two points on a grid.

1. A* Algorithm:

• Combines Dijkstra's algorithm (shortest path) with a heuristic to improve efficiency.
• Uses two main components:

1. g(n): The actual cost to reach node n from the start.
2. h(n): The heuristic estimate of the cost to reach the goal from node n.

• Total cost function:

$$f(n) = g(n) + h(n)$$

2. Heuristic Function ($h(n)$):

• Example: Manhattan Distance for grid-based pathfinding:

$$h(n) = |x_1 - x_2| + |y_1 - y_2|$$

• This estimates the distance to the goal, helping the algorithm prioritise exploring nodes closer to the goal. Pseudocode for A* Algorithm:

FUNCTION AStar(start, goal):
    OPEN_SET = {start}
    CLOSED_SET = {}
    g_score[start] = 0
    f_score[start] = h(start)

    WHILE OPEN_SET is not empty:
        current = node in OPEN_SET with lowest f_score
        IF current == goal THEN
            RETURN reconstruct_path(current)

        MOVE current from OPEN_SET to CLOSED_SET

        FOR each neighbor of current:
            IF neighbor in CLOSED_SET:
                CONTINUE

            tentative_g_score = g_score[current] + distance(current, neighbor)

            IF neighbor not in OPEN_SET OR tentative_g_score < g_score[neighbor]:
                g_score[neighbor] = tentative_g_score
                f_score[neighbor] = g_score[neighbor] + h(neighbor)
                IF neighbor not in OPEN_SET:
                    ADD neighbor to OPEN_SET

    RETURN failure

Purpose and Benefits of Using Heuristics

1. Efficiency:

• Reduces the time and computational resources required to find a solution by narrowing down the search space.

2. Practical Solutions:

• Provides solutions that are "good enough" for real-world problems, especially when an exact solution isn't necessary.

3. Flexibility:

• Can be adapted to a variety of problem domains by changing the heuristic function.

4. Solving Intractable Problems:

• Enables solving problems that are otherwise computationally infeasible due to their size or complexity.

Example Scenarios

Route Optimisation (Pathfinding)

• Problem: Find the shortest route for a delivery truck between multiple locations.
• Heuristic: Use estimated travel time (e.g., straight-line distance) to prioritise routes.

Game AI (Chess)

• Problem: Determine the best move in a chess game.
• Heuristic: Evaluate the board based on material balance, piece mobility, and control of the centre.

Scheduling and Timetabling

• Problem: Assign tasks to time slots or resources with minimal conflict.
• Heuristic: Assign tasks with the highest priority first or those that have the fewest compatible time slots.

Benefits and Drawbacks of Heuristics

Aspect	Benefits	Drawbacks
Efficiency	Reduces time and computational requirements.	May not always produce the optimal solution.
Practicality	Useful for real-world problems with time constraints.	Can result in suboptimal or incorrect solutions.
Simplicity	Easier to implement compared to exhaustive methods.	Requires careful design and tuning of the heuristic.
Applicability	Can be adapted for different types of problems.	May be problem-specific and not generalisable.

Programming a Simple Heuristic

Scenario: A maze-solving program using a heuristic to find the shortest path.

Python Implementation:

import heapq

def heuristic(a, b):
    # Manhattan distance
    return abs(a[0] - b[0]) + abs(a[1] - b[1])

def a_star_search(maze, start, goal):
    open_set = []
    heapq.heappush(open_set, (0, start))
    came_from = {}
    g_score = {start: 0}

    while open_set:
        current = heapq.heappop(open_set)[1]

        if current == goal:
            return reconstruct_path(came_from, current)

        for neighbor in get_neighbors(maze, current):
            tentative_g_score = g_score[current] + 1  # Assuming uniform cost

            if neighbor not in g_score or tentative_g_score < g_score[neighbor]:
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g_score
                f_score = tentative_g_score + heuristic(neighbor, goal)
                heapq.heappush(open_set, (f_score, neighbor))

    return None

def reconstruct_path(came_from, current):
    path = []
    while current in came_from:
        path.append(current)
        current = came_from[current]
    path.reverse()
    return path

Note Summary