A* Search

A* Search

Introduction

Generally, to find a single destination, we can use the following method:

BFS
1. We equally explore all the directions, push all the next visit point to a queue
Dijkstra
1. Apart from pushing to a queue, we push to a priority queue with a priority of distance from the starting point. For example, if we go to next available cell with different costs, we can prioritize this.
A* search
1. Based on Dijkstra, we also take the heuristic distance to the destination, which means the weight in pq should consider the distance from src and the distance to the target

Example Question

Sliding Puzzle

Detail Implementation

Here

Pseudo code

frontier = PriorityQueue()
frontier.put(start, 0)
came_from = {}
cost_so_far = {}
came_from[start] = None
cost_so_far[start] = 0

while not frontier.empty():
   current = frontier.get()

   if current == goal:
      break
   for next in graph.neighbors(current):
      new_cost = cost_so_far[current] + graph.cost(current, next)
      if next not in cost_so_far or new_cost < cost_so_far[next]:
         cost_so_far[next] = new_cost
         priority = new_cost + heuristic(goal, next)
         frontier.put(next, priority)
         came_from[next] = current

The heuristic usually can be calculate Manhattan distance

Proof of Using Manhattan Distance

When we come to the same point to compare, the heuristic distance is the same, but the starting distance can be different. Therefore, if the cost is higher, it's definitely not the most optimized solution

Possible Heuristic

Check (B) Approximation Heuristics

Advanced Tips

Proof 看Mathematical Proof. Section

提出一个观点，对于所有(R, C) 最终可以分为两类，一种是达不到的，一种是能达到target的。而不能够达到target的，都是互相transformable的

利用上述这一特点，我们可以任意选择一个reach不到的target，然后如果碰到，直接返回-1

A* search