Heuristics

Heuristic Classifications in Problem Solving

---

What are Heuristics?

• Problem-solving strategies that use readily accessible information to control problem-solving processes
• "Rules of thumb" that guide decision-making and reasoning
• Methods that help find good-enough solutions when finding optimal solutions is impractical
• Informal, intuitive, and judgmental knowledge

---

Why Use Heuristics?

• Reduce the complexity of difficult problems
• Make problem-solving more efficient
• Help navigate large search spaces
• Allow decisions with incomplete information
• Trade perfect accuracy for speed and practicality

---

Heuristic Classifications

Heuristics can be classified into several major categories:

1. State Evaluation Heuristics
2. Rule of Thumb Heuristics
3. Simplification Heuristics
4. Meta-Heuristics
5. Domain-Specific Heuristics

---

1. State Evaluation Heuristics

• Estimate "distance" or "cost" to reach a goal state
• Used extensively in search algorithms
• Typically return a numerical value

Examples:

• Manhattan distance in path-finding
• Number of misplaced tiles in 8-puzzle
• Material value in chess

---

State Evaluation Heuristic Example: 8-Puzzle

┌───┬───┬───┐    ┌───┬───┬───┐
│ 2 │ 8 │ 3 │    │ 1 │ 2 │ 3 │
├───┼───┼───┤    ├───┼───┼───┤
│ 1 │   │ 4 │    │ 8 │   │ 4 │
├───┼───┼───┤    ├───┼───┼───┤
│ 7 │ 6 │ 5 │    │ 7 │ 6 │ 5 │
└───┴───┴───┘    └───┴───┴───┘
  Current State     Goal State

Misplaced Tiles Heuristic: Count tiles not in final position (here: 1) Manhattan Distance Heuristic: Sum of horizontal and vertical distances each tile must move (here: 3)

---

2. Rule of Thumb Heuristics

• General guidelines based on experience
• Often expressed as IF-THEN statements
• Typically qualitative rather than quantitative

Examples:

• "If a problem seems too difficult, break it into smaller parts"
• "When debugging, check the most recently changed code first"
• "In resource allocation, prioritize based on urgency and importance"

---

Rule of Thumb Heuristic Example: Medical Diagnosis

                  ┌───────────────┐
                  │ Patient with  │
                  │ sore throat   │
                  └───────┬───────┘
                          │
                          ▼
                 ┌────────────────┐
                 │ Is fever      │
                 │ present?      │
                 └───┬──────┬────┘
                     │      │
                     │      │
           ┌─────────▼──┐   └────────┐
           │            │            │
           ▼            │            ▼
┌────────────────────┐  │   ┌────────────────────┐
│ If fever > 101°F   │  │   │ If no fever, check │
│ consider influenza │  │   │ for strep throat   │
└────────────────────┘  │   └────────────────────┘
                        │
                        ▼
              ┌────────────────────┐
              │ If fever + rash,   │
              │ check for measles  │
              └────────────────────┘

---

3. Simplification Heuristics

• Reduce problem complexity by ignoring certain constraints
• Solve the simplified version first
• Use that solution to guide solving the full problem

Examples:

• Ignoring air resistance in physics problems
• Assuming perfect information in game theory
• Working with averages instead of distributions

---

Simplification Heuristic Example: Traveling Salesman Problem

Original Problem: Find the shortest route visiting all cities exactly once

Simplification Heuristic - Nearest Neighbor:

1. Start at any city
2. Repeatedly visit the nearest unvisited city
3. Return to the starting city

    A•          •D
      \        /
       \      /
        \    /
         \  /
          •B
         /  \
        /    \
       /      \
    C•         •E

Path using Nearest Neighbor from A: A→B→C→E→D→A
(Not necessarily optimal but quick to compute)

---

4. Meta-Heuristics

• General-purpose optimization algorithms
• Applicable across different problem domains
• Often inspired by natural processes

Examples:

• Genetic Algorithms
• Simulated Annealing
• Ant Colony Optimization
• Particle Swarm Optimization

---

Meta-Heuristic Example: Genetic Algorithm

┌───────────────────────────────────────────────────┐
│ Initial Population                                │
│ [Solution 1] [Solution 2] [Solution 3] [Solution 4]│
└─────────────────────┬─────────────────────────────┘
                      │
                      ▼
┌───────────────────────────────────────────────────┐
│ Fitness Evaluation                                │
│ How good is each solution?                        │
└─────────────────────┬─────────────────────────────┘
                      │
                      ▼
┌───────────────────────────────────────────────────┐
│ Selection                                         │
│ Choose parents based on fitness                   │
└─────────────────────┬─────────────────────────────┘
                      │
                      ▼
┌───────────────────────────────────────────────────┐
│ Crossover & Mutation                              │
│ Create new solutions                              │
└─────────────────────┬─────────────────────────────┘
                      │
                      ▼
┌───────────────────────────────────────────────────┐
│ New Generation                                    │
│ [Solution A] [Solution B] [Solution C] [Solution D]│
└─────────────────────┬─────────────────────────────┘
                      │
                      ▼
                 Repeat Process

---

5. Domain-Specific Heuristics

• Tailored to particular fields or problem types
• Leverage specialized knowledge
• Often more effective than general-purpose heuristics

Examples:

• Chess opening strategies
• Scheduling algorithms for specific industries
• Financial investment decision rules

---

Domain-Specific Heuristic Example: Chess

┌─────────────────────────────────────────┐
│ Chess Position Evaluation Heuristics    │
├─────────────────────────────────────────┤
│ • Control the center                    │
│ • Protect your king                     │
│ • Develop pieces early                  │
│ • Don't move same piece twice in opening│
│ • Knights before bishops in closed games│
│ • Material values:                      │
│   - Pawn: 1 point                       │
│   - Knight/Bishop: 3 points             │
│   - Rook: 5 points                      │
│   - Queen: 9 points                     │
└─────────────────────────────────────────┘

---

Detailed Case Study: Diagnostic Heuristics

Medical diagnosis is a perfect example of heuristic classification:

1. Pattern Recognition: Matching symptoms to disease profiles
2. Hypothesis Testing: Proposing and testing possible diagnoses
3. Refinement: Narrowing down possibilities through tests
4. Confirmation: Validating the final diagnosis

---

Diagnostic Heuristics Process

┌─────────────────┐
│ Patient Data    │
│ • Symptoms      │
│ • History       │
│ • Vitals        │
└───────┬─────────┘
        │
        ▼
┌─────────────────┐     ┌─────────────────┐
│ Trigger         │     │ Disease Library  │
│ Heuristics      │────▶│ • Profiles      │
│ • If symptoms X │     │ • Patterns      │
│   consider Y    │     │ • Probabilities │
└───────┬─────────┘     └─────────────────┘
        │
        ▼
┌─────────────────┐
│ Hypotheses      │
│ Generation      │
│ • Possible      │
│   diagnoses     │
└───────┬─────────┘
        │
        ▼
┌─────────────────┐
│ Refinement      │
│ Heuristics      │
│ • Tests to order│
│ • Questions     │
└───────┬─────────┘
        │
        ▼
┌─────────────────┐
│ Final Diagnosis │
└─────────────────┘

---

Properties of Good Heuristics

• Admissibility: Never overestimates cost to goal (for search algorithms)
• Consistency: Satisfies the triangle inequality (for search algorithms)
• Informedness: Provides useful guidance toward a solution
• Computational Efficiency: Quick to calculate
• Domain Relevance: Captures important aspects of the problem

---

Creating Effective Heuristics

1. Identify patterns in the problem domain
2. Understand what makes solutions "good" or "bad"
3. Look for simplified versions of the problem
4. Consider what experts in the field do intuitively
5. Balance accuracy with computational cost
6. Test on diverse problem instances

---

Heuristics vs. Algorithms

Characteristic	Heuristics	Algorithms
Guarantees	No guarantee of optimal solution	Guaranteed to find solution if exists
Efficiency	Generally faster	May be slower but exact
Complexity	Usually simpler	Can be more complex
Applicability	Broader, more flexible	Narrower, more specific
Results	"Good enough" solutions	Optimal solutions

---

Common Applications of Heuristic Classifications

• Artificial Intelligence: Search algorithms, game playing
• Medicine: Diagnosis, treatment planning
• Business: Decision-making, resource allocation
• Engineering: Design optimization, scheduling
• Computer Science: Algorithm design, problem-solving
• Education: Teaching problem-solving strategies

---

Implementing Heuristics in Code

# A* Search Algorithm using heuristic
def a_star_search(start, goal, graph, heuristic):
    # Open set contains nodes to be evaluated
    open_set = {start}
    # Came_from keeps track of optimal path
    came_from = {}

    # g_score is cost from start to current node
    g_score = {node: float('inf') for node in graph}
    g_score[start] = 0

    # f_score is estimated total cost
    f_score = {node: float('inf') for node in graph}
    f_score[start] = heuristic(start, goal)

    while open_set:
        # Get node with lowest f_score
        current = min(open_set, key=lambda x: f_score[x])

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

        open_set.remove(current)

        for neighbor in graph[current]:
            # Tentative g_score
            tentative_g = g_score[current] + graph[current][neighbor]

            if tentative_g < g_score[neighbor]:
                # This path is better
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g
                f_score[neighbor] = g_score[neighbor] + heuristic(neighbor, goal)

                if neighbor not in open_set:
                    open_set.add(neighbor)

    return None  # No path exists

---

Advantages of Heuristic Classifications

• Reduce problem-solving time significantly
• Make complex problems tractable
• Formalize intuitive knowledge
• Allow for graceful degradation when optimal solutions are infeasible
• Often mimic human problem-solving approaches
• Highly adaptable to different problem domains

---

Limitations of Heuristic Classifications

• No guarantee of finding optimal solution
• Quality depends on the heuristic design
• May lead to systematic errors or biases
• Difficult to formally analyze or prove properties
• Performance can vary widely across different problem instances
• May get stuck in local optima for optimization problems

---

Practical Exercise: Developing Heuristics

Exercise for students:

1. Consider the problem of university course scheduling
2. Identify 5 different heuristics that might help create good schedules
3. Classify each heuristic according to the types we've discussed
4. Evaluate the potential advantages and limitations of each

---

Summary

• Heuristics are "rules of thumb" that guide problem-solving
• Heuristic Classifications include:
  • State Evaluation Heuristics
  • Rule of Thumb Heuristics
  • Simplification Heuristics
  • Meta-Heuristics
  • Domain-Specific Heuristics
• Provide efficient, "good enough" solutions to complex problems
• Trade optimality for practicality and speed
• Widely used across multiple disciplines

---

References

• Pearl, J. "Heuristics: Intelligent Search Strategies for Computer Problem Solving"
• Kahneman, D. "Thinking, Fast and Slow"
• Russell, S. & Norvig, P. "Artificial Intelligence: A Modern Approach"
• Polya, G. "How to Solve It"
• Gigerenzer, G. & Todd, P.M. "Simple Heuristics That Make Us Smart"