A* Search Algorithm

Ibrahim Habib
Zeyad Mohamed
Mohamed Essam
Youssef Ahmed
Youssef Mahmoud

2025-10-26

1 The A* Search Algorithm

1.1 Search Problems Refresher

Goal: Find a path from a start state to a goal state in a state space.

Components:

  • States: Possible configurations of the problem.
  • Actions: Possible moves from one state to another.
  • Transition Model: Describes the result of applying an action to a state.
  • Cost Function: Assigns a cost to each action.
  • Goal Definition: Determines if a state is a goal state.

1.2 Problems Solvable by Search Algorithms

  • Pathfinding (e.g., GPS navigation)
  • Puzzle solving (e.g., 8-puzzle, Sudoku)
  • Game playing (e.g., chess, go)
  • Task scheduling (e.g., university timetabling)

1.3 The Best-First Search Algorithm

Idea: Explore the most promising node first based on a given evaluation function.

Very Generic: Can be adapted to various search strategies each with its own evaluation function.

1.4 Best-First Search Steps

Data Structures:

  • Frontier: Priority Queue ordered by evaluation function (\(f(u)\), lower values have higher priority).
  • Explored Set: To keep track of visited nodes.

1.5 Best-First Search Steps

Algorithm Steps:

  1. Initialize the frontier with the start node.

1.6 Best-First Search Steps

Algorithm Steps:

  1. Loop until the frontier is empty:
    • Remove the node \(u\) with the lowest \(f(u)\) from the frontier.
    • If \(u\) is a goal state, return the solution.
    • Expand \(u\) to generate the connected nodes.
    • For each connected node if it is unexplored or explored with a higher path cost, add it to the frontier and update explored set.

1.7 Best-First Search Steps

Algorithm Steps:

  1. If the frontier is empty, return failure (no solution found).

1.10 Time and Space Complexity of A*

  • Time Complexity: \(O(b^{d})\)
  • Space Complexity: \(O(b^{d})\)

where \(b\) is the branching factor and \(d\) is the depth of the goal node.

2 A* Example Walkthrough

2.1 Problem Setup

AStarSearch_Step0 Initial State Explored: {} Frontier: {S} S S g=0, h=5, f=5 A A h=4 S->A 1 B B h=2 S->B 5 C C h=3 A->C 2 D D h=1 A->D 5 B->D 1 E E h=2 C->E 1 G G h=0 D->G 2 E->G 2

  • \(g\) = Cost to reach current node from start
  • \(h\) = Estimate to the cost from current node to goal
  • \(f\) = \(g\) + \(h\)

2.2 Step 1: Expand S

AStarSearch_Step1 Step 1 (Expand S) Explored: {S} Frontier: {A=5, B=7} S S g=0, h=5, f=5 A A g=1, h=4, f=5 S->A 1 B B g=5, h=2, f=7 S->B 5 C C h=3 A->C 2 D D h=1 A->D 5 B->D 1 E E h=2 C->E 1 G G h=0 D->G 2 E->G 2

  • \(g\) = Cost to reach current node from start
  • \(h\) = Estimate to the cost from current node to goal
  • \(f\) = \(g\) + \(h\)

2.3 Step 2: Expand A

AStarSearch_Step2 Step 2 (Expand A) Explored: {S, A} Frontier: {C=6, B=7, D=7} S S g=0, h=5, f=5 A A g=1, h=4, f=5 S->A 1 B B g=5, h=2, f=7 S->B 5 C C g=3, h=3, f=6 A->C 2 D D g=6, h=1, f=7 A->D 5 B->D 1 E E h=2 C->E 1 G G h=0 D->G 2 E->G 2

  • \(g\) = Cost to reach current node from start
  • \(h\) = Estimate to the cost from current node to goal
  • \(f\) = \(g\) + \(h\)

2.4 Step 3: Expand C

AStarSearch_Step3 Step 3 (Expand C) Explored: {S, A, C} Frontier: {E=6, B=7, D=7} S S g=0, h=5, f=5 A A g=1, h=4, f=5 S->A 1 B B g=5, h=2, f=7 S->B 5 C C g=3, h=3, f=6 A->C 2 D D g=6, h=1, f=7 A->D 5 B->D 1 E E g=4, h=2, f=6 C->E 1 G G h=0 D->G 2 E->G 2

  • \(g\) = Cost to reach current node from start
  • \(h\) = Estimate to the cost from current node to goal
  • \(f\) = \(g\) + \(h\)

2.5 Step 4: Expand E

AStarSearch_Step4 Step 4 (Expand E) Explored: {S, A, C, E} Frontier: {G=6, B=7, D=7} S S g=0, h=5, f=5 A A g=1, h=4, f=5 S->A 1 B B g=5, h=2, f=7 S->B 5 C C g=3, h=3, f=6 A->C 2 D D g=6, h=1, f=7 A->D 5 B->D 1 E E g=4, h=2, f=6 C->E 1 G G g=6, h=0, f=6 D->G 2 E->G 2

  • \(g\) = Cost to reach current node from start
  • \(h\) = Estimate to the cost from current node to goal
  • \(f\) = \(g\) + \(h\)

2.6 Step 5: Expand G

Once G is expanded, the algorithm determines that it is a goal state and returns the solution path.

3 The Heuristic Function \(h(u)\)

3.1 What is a Heuristic Function?

A heuristic function \(h(u)\) is an educated guess of the cost to reach the goal from node \(u\).

3.2 Heuristic Function Examples

  • Straight-Line Distance: In pathfinding problems, the straight-line distance to the goal.
  • Number of Misplaced Tiles: In the 8-puzzle problem, the number of tiles that are not in their goal position.

3.3 Why Should We Care About Heuristics?

Efficiency

A good heuristic function can significantly decrease the effective branching factor \(b^*\), leading to faster search times and reduced memory usage.

3.4 Why Should We Care About Heuristics?

Optimality

Depending on the properties of the heuristic function, A* can guarantee finding the optimal solution.

3.5 Why Should We Care About Heuristics?

No Repeat States

A good heuristic can help avoid re-expanding nodes.

3.6 Admissible Heuristics

A heuristic function \(h(u)\) is admissible if it never overestimates the true cost to reach the goal from node \(u\).

\[h(u) \leq h^*(u)\]

where \(h^*(u)\) is the actual cost to reach the goal from node \(u\).

Example: Straight-line distance in pathfinding problems, no. of misplaced tiles in 8-puzzle.

Properties

3.7 Admissible Heuristics Example

AdmissibleHeuristicNew Check all nodes: S:  h(S) <= h*(S)   ;  5 <= 8 A:  h(A) <= h*(A)  ;  4 <= 7 B:  h(B) <= h*(B)  ;  3 <= 5 C:  h(C) <= h*(C)  ;  2 <= 6 G:  h(G) <= h*(G)  ;  0 <= 0 S S (Start) h(S) = 5 A A h(A) = 4 S->A c=1 B B h(B) = 3 S->B c=4 C C h(C) = 2 A->C c=2 G G (Goal) h(G) = 0 A->G c=7 B->C c=3 B->G c=5 C->G c=6

3.8 Consistent Heuristics

A heuristic function \(h(u)\) is consistent if, for every node \(u\) and every successor \(v\) of \(u\), the following holds:

\[h(u) \leq c(u, v) + h(v)\]

where \(c(u, v)\) is the cost of the edge from \(u\) to \(v\).

Example: Straight-line distance in pathfinding problems.

Properties

  • A consistent heuristic is always admissible.
  • A* with a consistent heuristic never re-expands nodes.

3.9 Consistent Heuristics

ConsistentHeuristicDefinition h(u) <= c(u, v) + h(v) U u h(u) V v h(v) U->V c(u, v) G G (Goal) h(G)=0 U->G h(u) V->G h(v)

3.10 Consistent Heuristics Example

ConsistentHeuristic Edges Check: S -> A:  h(S) <= c(S,A) + h(A)  ;  7 <= 3 + 4  (7 <= 7) S -> B:  h(S) <= c(S,B) + h(B)  ;  7 <= 2 + 5  (7 <= 7) B -> A:  h(B) <= c(B,A) + h(A)  ;  5 <= 2 + 4  (5 <= 6) B -> G:  h(B) <= c(B,G) + h(G)  ;  5 <= 6 + 0  (5 <= 6) A -> G:  h(A) <= c(A,G) + h(G)  ;  4 <= 5 + 0  (4 <= 5) S S (Start) h(S) = 7 A A h(A) = 4 S->A c=3 B B h(B) = 5 S->B c=2 G G (Goal) h(G) = 0 A->G c=5 B->A c=2 B->G c=6

3.11 Heuristic Function Design Tips

  • Solve a relaxed version of the problem.
  • Use domain-specific knowledge.
  • Ensemble multiple heuristics.
  • Benchmark and iterate.

3.12 Heuristic Function Design Tips

  • If you’re looking for the path to the goal
    • Try an admissible heuristic
    • Try solving a relaxed version
  • If you’re more concerned with the goal itself (not the path)
    • Try a penalty-based heuristic
    • Focus on avoiding bad states

4 Implementation

4.1 Problem Representation (Action)

class SearchProblemAction(ABC):
    @abstractmethod
    def get_cost(self) -> float:
        """
        Get the cost associated with this action.
        """
        pass

4.2 Problem Representation (State)

class SearchProblemState(ABC):
    @abstractmethod
    def get_actions(self) -> Iterable[SearchProblemAction]:
        """
        Get a list of possible actions from this state.
        """
        pass

4.3 Problem Representation (Problem)

class SearchProblem(ABC):
    @abstractmethod
    def is_goal(self, state: SearchProblemState) -> bool:
        """
        Check if the given state is a goal state.
        """
        pass

    @abstractmethod
    def transition(
        self, state: SearchProblemState, action: SearchProblemAction
    ) -> SearchProblemState:
        """
        Given a state and an action, return the
        resulting state after applying the action.
        """
        pass

    @abstractmethod
    def get_initial_state(self) -> SearchProblemState:
        """
        Return the initial state of the search problem.
        """
        pass

4.4 Search Node Representation

class SearchNode:
    def __init__(
        self,
        state: SearchProblemState,
        parent: Self | None = None,
        action: SearchProblemAction | None = None,
        path_cost: float = 0.0,
    ):
        self.state = state
        self.parent = parent
        self.action = action
        self.path_cost = path_cost

4.5 Best-First Search Implementation

def best_first_search(
    problem: SearchProblem,
    search_function: BestFirstSearchFunction,
) -> tuple[SearchNode | None, int]:
    root_node = SearchNode(state=problem.get_initial_state(),path_cost=0)
    frontier = PriorityQueue()
    frontier.put((search_function.evaluate(root_node), 0, root_node))
    explored: dict[SearchProblemState, SearchNode] = {}

    no_explored = 0
    no_frontier_updates = 0

    while frontier.qsize() > 0:
       # ... [upcoming code] ...

    return None, no_explored

4.6 Best-First Search Implementation (Contd.)

# ... [previous code] ...
_, _, current_node = frontier.get()
no_explored += 1
if problem.is_goal(current_node.state):
    return current_node, no_explored

explored[current_node.state] = current_node

for action in current_node.state.get_actions():
    child_node = SearchNode(
        state=problem.transition(current_node.state, action),
        parent=current_node,
        action=action,
        path_cost=current_node.path_cost + action.get_cost(),
    )
    # ... [upcoming code] ...
# ... [previous code] ...

4.7 Best-First Search Implementation (Contd.)

# ... [previous code] ...

if (
    child_node.state not in explored
    or child_node.path_cost < explored[child_node.state].path_cost
):
    no_frontier_updates += 1
    frontier.put((search_function.evaluate(child_node),
            no_frontier_updates,
            child_node,
        )
    )
    explored[child_node.state] = child_node

# ... [previous code] ...

4.8 A* Search Function

class HeuristicFunction(ABC):
    @abstractmethod
    def estimate(self, state: SearchProblemState) -> float:
        pass

class AStarSearchFunction(BestFirstSearchFunction):
    def __init__(self, heuristic: HeuristicFunction):
        self.heuristic = heuristic

    def evaluate(self, node: SearchNode) -> float:
        return node.path_cost + self.heuristic.estimate(node.state)

5 A* Search on Sample Problem (N-Queens)

5.1 N-Queens Problem

Place N queens on an N x N chessboard such that no two queens attack each other.

5.2 N-Queens Heuristic

Number of pairs of queens that are attacking each other.

Reasoning: - We care about reaching a goal more than the path cost (placing queens is cheap). - So, we use a penalty-based heuristic. - The more pairs of attacking queens, the worse the state.

5.3 N-Queens Representation

class NQueensAction(SearchProblemAction):
    def __init__(self, col: int, new_row: int):
        self.col = col
        self.new_row = new_row

    def get_cost(self) -> float:
        return 1.0

5.4 N-Queens Representation (Contd.)

class NQueensState(SearchProblemState):
    def __init__(self, board: list[int], n: int):
        assert len(board) == n
        assert all(0 <= row < n for row in board)
        # board is a list where index is column and value is row
        self.board = board
        self.n = n

    def get_actions(self) -> Iterable[SearchProblemAction]:
        for col in range(self.n):
            for row in range(self.n):
                if self.board[col] != row:
                    yield NQueensAction(col, row)

5.5 N-Queens Representation (Contd.)

class NQueensProblem(SearchProblem):
    def __init__(self, n initial_state: NQueensState | None = None):
        self.n = n
        self.initial_state = initial_state

    def transition(
        self, state: SearchProblemState, action: SearchProblemAction
    ) -> SearchProblemState:
        new_board = state.board[:]
        new_board[action.col] = action.new_row
        return NQueensState(new_board, self.n)

    def get_initial_state(self) -> SearchProblemState:
        return self.initial_state

5.6 N-Queens Representation (Contd.)

class NQueensProblem(SearchProblem):
    # ... [previous code] ...

    def is_goal(self, state: SearchProblemState) -> bool:
        board = state.board
        n = self.n
        if len(set(board)) < n:
            return False  # Two queens in the same row

        for col1 in range(n):
            for col2 in range(col1 + 1, n):
                if abs(board[col1] - board[col2]) == abs(col1 - col2):
                    return False  # Two queens on the same diagonal
        return True

5.7 N-Queens Representation (Contd.)

class NoQueenAttackHeuristic(HeuristicFunction):
    def estimate(self, state: NQueensState) -> float:
        board = state.board
        n = state.n
        attacks = 0

        for col1 in range(n):
            for col2 in range(col1 + 1, n):
                if board[col1] == board[col2] or (
                    abs(board[col1] - board[col2]) == abs(col1 - col2)
                ):
                    attacks += 1

        return float(attacks)

5.8 N-Queens Algorithm Performance

Test Setup

  • n = 8 (No. of States = 16,777,216)
  • Initial State: Randomly placed queens
  • Number of Runs: 10
Algorithm Avg. Explored
Uniform-Cost Search 171,973.2
A* Search (Row Conflicts Heuristic) 5,165.0
A* Search (Total No. of Attacks Heuristic) 52.6

5.9 Acknowledgements

  • Dr. Reham Amin: For her insightful lectures and continuous support and guidance throughout the AI course.
  • Dr. Mohamed Abdallah: For his hands-on sessions explaining search algorithms.

5.10 References

Russell, S. J., & Norvig, P. (2016). Artificial intelligence: A modern approach (Third edition, Global edition). Pearson.

Thank You!


Link to the presentation

Link to the code repo