The A* Search Algorithm is a popular pathfinding and graph traversal algorithm that finds the shortest path from a start node to a goal node by using a heuristic to prioritize exploration of nodes that appear most promising. It combines the benefits of Dijkstra's Algorithm and Greedy Best-First Search, ensuring optimal and complete solutions when the heuristic is admissible and consistent.

A* Search Algorithm

Pathfinding algorithm

graph traversal algorithm

The shortest path problem involves finding the most efficient route between two points in a graph, minimizing the total distance or cost. It is a fundamental concept in computer science and operations research, with applications in network routing, logistics, and urban planning.

shortest path

start node

goal node

A heuristic is a mental shortcut that allows people to solve problems and make judgments quickly and efficiently, often leading to solutions that are not optimal but are sufficient for immediate goals. It relies on experience-based techniques for problem-solving, learning, and discovery, and is particularly useful in situations where finding an optimal solution is impractical or impossible due to time constraints or complexity.

heuristic

exploration of nodes

Dijkstra's Algorithm is a graph search algorithm that finds the shortest path between nodes in a weighted graph, ensuring all edge weights are non-negative. It uses a priority queue to explore nodes with the smallest known distance, updating paths as shorter ones are discovered until the shortest path to the target node is identified.

Dijkstra's Algorithm

Greedy Best-First Search is a search algorithm that expands the most promising node chosen according to a specified heuristic function, aiming to find a solution quickly by prioritizing paths that appear to lead most directly to the goal. It can be efficient but is not guaranteed to find the optimal solution, as it only considers the heuristic cost and not the total cost from the start node.

Greedy Best-First Search

Optimal solutions

complete solutions

An admissible heuristic is a function used in search algorithms that never overestimates the cost to reach the goal, ensuring optimality in algorithms like A*. This property guarantees that the solution found is the best possible, as it always guides the search process in the most promising direction without missing any potentially optimal paths.

Admissible Heuristic

A consistent heuristic is one where the estimated cost from the current node to the goal is always less than or equal to the cost from the current node to a neighbor plus the estimated cost from the neighbor to the goal. This property ensures that the A* search algorithm using this heuristic is both optimal and efficient, as it prevents the algorithm from revisiting nodes unnecessarily.

Relevant Degrees

Your Lessons