AI with Python – Heuristic Search

AI with Python – Heuristic Search

Heuristic search is a fundamental technique in artificial intelligence for solving complex problems efficiently. This chapter explores its concepts and applications.

Understanding Heuristic Search in AI

A heuristic is an educated guess, or a ‘rule of thumb’, designed to guide a search algorithm towards a likely solution more quickly than exhaustive methods. Many AI problems involve vast search spaces, making it impractical to explore every possibility. Heuristics help prune this search space by prioritizing promising paths.

The effectiveness of a heuristic is determined by its ability to estimate the ‘closeness’ to a goal. A good heuristic significantly reduces search time, though it doesn’t always guarantee finding the absolute best solution (unless the heuristic has specific properties like admissibility in A* search).

Uninformed vs. Informed Search

Search strategies are broadly categorized based on whether they use problem-specific knowledge (heuristics):

Uninformed Search (Blind Search)

Uninformed search algorithms operate without any domain-specific knowledge beyond the problem definition (states, operators, goal test). They systematically explore the search space. Examples include:

• Breadth-First Search (BFS): Explores level by level.
• Depth-First Search (DFS): Explores one branch as far as possible before backtracking.

These methods are exhaustive and can be very inefficient for large state spaces.

Informed Search (Heuristic Search)

Informed search algorithms use a heuristic function, h(n), which estimates the cost from a state ‘n’ to the nearest goal. This guides the search towards more promising states. Examples include:

• Greedy Best-First Search: Expands the node that appears to be closest to the goal according to the heuristic.
• A* Search: Combines the cost to reach the node, g(n), with the estimated cost to goal, h(n). It uses f(n) = g(n) + h(n). A* is optimal and complete if the heuristic h(n) is admissible (never overestimates the true cost to the goal) and consistent (for any node n and successor n’ generated by action a, h(n) <= cost(n,a,n’) + h(n’)).
• Beam Search: A variation of best-first search that keeps only a fixed number (‘beam width’) of best paths at each step.

Common heuristic examples include Manhattan distance or Euclidean distance in pathfinding problems.

Constraint Satisfaction Problems (CSPs)

Constraint Satisfaction Problems are a class of problems where the goal is to find a state or a set of values for variables that satisfy a given set of constraints (rules or limitations). CSPs are defined by:

• A set of variables (X = {X1, …, Xn})
• A set of domains for each variable (D = {D1, …, Dn}), defining possible values.
• A set of constraints (C = {C1, …, Ck}) that specify allowable combinations of values.

A solution to a CSP is a complete assignment of values to variables such that all constraints are satisfied. Backtracking search is a common algorithm for solving CSPs.

Illustrating Constraint Satisfaction: An Algebraic Relation

Let’s consider a simple algebraic relation as a CSP: a * 2 = b, where ‘a’ and ‘b’ are integers within a specific range, say 0 to 9.

Here:

• Variables: a, b
• Domains: Da = {0, 1, ..., 9}, Db = {0, 1, ..., 9}
• Constraint: a * 2 == b

We can solve this by systematically checking values from the domains:

def solve_algebraic_csp():
    solutions = []
    domain = range(10)
    for a_val in domain:
        for b_val in domain:
            # Check constraint
            if a_val * 2 == b_val:
                solutions.append({'a': a_val, 'b': b_val})
    return solutions

# Get solutions
solutions = solve_algebraic_csp()
print(solutions)

The Python code above defines a function that iterates through possible values for ‘a’ and ‘b’ and appends valid pairs to the solutions list. The output would be:

[{'a': 0, 'b': 0}, {'a': 1, 'b': 2}, {'a': 2, 'b': 4}, {'a': 3, 'b': 6}, {'a': 4, 'b': 8}]

For more complex CSPs, general-purpose solvers or libraries implementing algorithms like backtracking with forward checking or arc consistency (e.g., Google OR-Tools) are often used.

Application: Magic Square Verifier

A magic square is a grid of distinct numbers where the sum of numbers in each row, each column, and both main diagonals is the same (the “magic constant”). Verifying if a given square is magic is a constraint-checking problem.

The following Python function checks if a given matrix is a magic square:

def is_magic_square(matrix):
    n = len(matrix)
    if n == 0 or any(len(row) != n for row in matrix):
        print("Matrix must be square and non-empty.")
        return False

    sum_list = []

    # Row sums
    for r in range(n):
        sum_list.append(sum(matrix[r]))

    # Column sums
    for c in range(n):
        current_col_sum = 0
        for r in range(n):
            current_col_sum += matrix[r][c]
        sum_list.append(current_col_sum)

    # Main diagonal sum (top-left to bottom-right)
    main_diag_sum = 0
    for i in range(n):
        main_diag_sum += matrix[i][i]
    sum_list.append(main_diag_sum)

    # Anti-diagonal sum (top-right to bottom-left)
    anti_diag_sum = 0
    for i in range(n):
        anti_diag_sum += matrix[i][n - 1 - i]
    sum_list.append(anti_diag_sum)

    # Check if all sums are the same
    if len(set(sum_list)) > 1:
        return False
    return True

Let’s test with some examples:

non_magic = [[1, 2, 3], [4, 5, 6], [7, 8, 9]]
print(f"Is {non_magic} a magic square? {is_magic_square(non_magic)}")

# A known 3x3 magic square (magic constant = 15)
magic_3x3 = [[8, 1, 6], [3, 5, 7], [4, 9, 2]]
print(f"Is {magic_3x3} a magic square? {is_magic_square(magic_3x3)}")

# Another example that is not a magic square
not_magic_either = [[3, 9, 2], [3, 5, 7], [9, 1, 6]]
print(f"Is {not_magic_either} a magic square? {is_magic_square(not_magic_either)}")

Output:

Is [[1, 2, 3], [4, 5, 6], [7, 8, 9]] a magic square? False
Is [[8, 1, 6], [3, 5, 7], [4, 9, 2]] a magic square? True
Is [[3, 9, 2], [3, 5, 7], [9, 1, 6]] a magic square? False