Please enable JavaScript.
Coggle requires JavaScript to display documents.
Path Finding Algorithms - Coggle Diagram
Path Finding Algorithms
Definition and importance
Path finding algorithms are computational methods used to determine the most efficient route from a starting point to a destination within a defined space. Their significance lies in optimizing navigation processes across various applications, embodying a core element of artificial intelligence systems that require spatial reasoning.
Types of Path Finding Algorithms
Informed Search Algorithms
Greedy Best-First Search
: This algorithm selects nodes based on the lowest heuristic cost, focusing on immediate gains in proximity to the target, which can lead to faster solutions but not necessarily the most optimal path.
A* Algorithm
: The A* algorithm is a popular pathfinding method that finds the shortest path between two points by combining the actual cost to reach a node and a heuristic estimate of the remaining distance to the goal, making it both fast and accurate.
Dijkstra's Algorithm
: Dijkstra's Algorithm guarantees the shortest path in a weighted graph by systematically exploring all possible routes until the destination is reached, ensuring that the path chosen is the least costly.
Uninformed Search Algorithms
Depth-First Search (DFS)
: DFS explores as far down a branch as possible before backtracking. While it's space-efficient, it may lead to longer paths, especially in weighted graphs, because it doesn't guarantee finding the shortest path.
Uniform Cost Search
: This algorithm expands the nodes with the least cost first, ensuring that it finds the path with the lowest total cost. It’s particularly effective in graphs where the edges have varying weights.
Breadth-First Search (BFS)
: BFS explores all nodes at the current depth level before moving on to nodes at the next level. This ensures that it finds the shortest path in terms of the number of edges, making it well-suited for unweighted graphs.
Search Tree
The root node is the starting point (initial state).
Branches represent actions or choices that lead to new states.
Leaf nodes may represent goal states or dead ends.
Each node represents a state or a possible situation.
Used in pathfinding, decision-making, game AI, and problem solving.
Algorithm Characteristics
Space complexity
Time complexity
Optimality
Completeness
The Frontier
Parent node
Child node
Leaf node