A* Search Algorithm

The A* search algorithm is an informed search algorithm. Besides using a heuristic function, like the greedy best-first search algorithm, it also uses the cost of the path from the start state to the current state to guide its search. The cost of the path is also known as the g-value. As a function. it is denoted as g(n). The heuristic function is denoted as h(n). The A* search algorithm uses the following function to guide its search:

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

A* Search Optimality

A* search is guaranteed to find the optimal solution if the heuristic function is admissible and consistent.

An admissible heuristic function h(n) is one that never overestimates the cost of reaching the goal. In other words, the heuristic function should always be less than or equal to the actual cost of reaching the goal.

A heuristic function h(n) is consistent if the estimated cost of reaching the goal from the current state is no greater than the step cost of getting to the next state plus the estimated cost of reaching the goal from the next state. So, if I'm at state n, and I take an action that costs c to get to a successor state n', the estimated cost of reaching the goal from state n should be less than or equal to the step cost of getting to state n' plus the estimated cost of reaching the goal from state n'.

h(n) <= c + h(n')

In our next example, we will use the count_misplaced_tiles heuristic function to solve the 15-puzzle problem with A* search. The count_misplaced_tiles heuristic function is admissible and consistent for the 15-puzzle problem, so it is guaranteed to find the optimal solution (number of moves to solve the puzzle).

To solve the 15-puzzle problem with the A* search algorithm, we need to modify our algorithm to use both the cost of the path and the heuristic function to guide its search. The additional component we need will be the calculation of g_value which is the cost of the path from the start state to the current state.

def a_star_search(initial_board, goal_board):
  visited = set()
  priority_queue = []

  # Initial state with a cost of 0
  heapq.heappush(priority_queue, (0, 0, (initial_board, [])))

  while priority_queue:
    current_cost, _, (board, path) = heapq.heappop(priority_queue)

    if board == goal_board:
      return path

    visited.add(tuple(board))

    for move in ['up', 'down', 'left', 'right']:
      next_board = make_move(board, move)
      if next_board and tuple(next_board) not in visited:
        heuristic = manhattan_distance(next_board, goal_board)
        g_value = current_cost + 1  # Increment the cost
        if heuristic is not None:
          total_cost = heuristic + g_value
          heapq.heappush(priority_queue,
                         (total_cost, g_value, (next_board, path + [move])))

  return None

Here is the full code for the 15-Puzzle problem with A* search:

The output of the program is:

A* Solution:
# some steps omitted
.....
Move up:
[1, 2, 3, 4]
[5, 6, 11, 7]
[9, 10, 0, 8]
[13, 14, 15, 12]


Move up:
[1, 2, 3, 4]
[5, 6, 0, 7]
[9, 10, 11, 8]
[13, 14, 15, 12]


Move right:
[1, 2, 3, 4]
[5, 6, 7, 0]
[9, 10, 11, 8]
[13, 14, 15, 12]


Move down:
[1, 2, 3, 4]
[5, 6, 7, 8]
[9, 10, 11, 0]
[13, 14, 15, 12]


Move down:
[1, 2, 3, 4]
[5, 6, 7, 8]
[9, 10, 11, 12]
[13, 14, 15, 0]

24

Comparing that with the number of steps taken by the greedy best-first search algorithm, we can see that the A* search algorithm found the optimal solution with 24 steps, while the greedy best-first search algorithm found a solution with 187 steps.

A* (A-star) search is a widely used algorithm for finding the shortest path in a graph or solving optimization problems. It uses a heuristic to guide the search, making it more efficient than traditional uninformed search algorithms. There are different variations of A* search, each tailored to specific types of problems or computational constraints. Here are some notable variations:

The standard A algorithm uses a combination of the cost to reach a node (g) and a heuristic estimate of the cost to reach the goal from that node (h). The evaluation function is f(n) = g(n) + h(n). A expands nodes with the lowest f(n) value.

Weighted A* introduces a weight factor to the heuristic function, influencing the balance between the cost to reach the node and the estimated cost to the goal. This can be useful for adjusting the algorithm's behavior, favoring either optimality or speed.

In bidirectional A* search, the search is performed simultaneously from both the start and goal states. The algorithm continues until the two searches meet in the middle. This approach can be more efficient for certain types of graphs, especially when the branching factor is high.

Real-Time A* is an extension of A* designed for environments where computation time is limited. It uses an incremental approach, exploring nodes in the order of their estimated cost until the available time runs out, returning the best solution found.

These variations address different challenges and requirements, making A* adaptable to a wide range of problem domains and computational constraints. The choice of a specific variation depends on the characteristics of the problem, available resources, and the desired trade-offs between optimality and efficiency.

Summary

The A* search algorithm is an informed search algorithm that uses both the cost of the path and the heuristic function to guide its search. The A* search algorithm is guaranteed to find the optimal solution if the heuristic function is admissible and consistent.