Please enable JavaScript.

Coggle requires JavaScript to display documents.

Pathfinding Algorithms - Coggle Diagram

- - - - Representation of all possible states and transitions in the problem.
    - - Tree-like structure generated by expanding states (nodes) and actions (branches).
      - Root: Initial state.
      - Goal Test: Checks if a node represents a goal state.
      - Expansion: Generating successor states from a node.
    - - Set of nodes to be explored.
    - - Set of already visited nodes to avoid loops.
    - - Node State (location)
      - Node Parent (for backtracking)
      - Node Action (how to get there)
      - Node Path Cost (cumulative cost)
    - - Completeness: Guaranteed to find a solution if one exists.
      - Optimality: Finds the lowest-cost path.
      - Time Complexity: Time taken to find a solution.
      - Space Complexity: Memory usage.
- - - - Breadth-First Search (BFS): FIFO (queue), explores level by level.
      - Uniform Cost Search: Expands node with the lowest path cost, prioritizes queue based on cost.
      - Depth-First Search (DFS): LIFO (stack), explores a path deeply before backtracking.
      - Depth-Limited Search: DFS with a depth limit.
      - Iterative Deepening Depth-First Search: Repeatedly performs depth-limited searches with increasing limits.
      - Bidirectional Search: Searches from both the start and goal states simultaneously.
    - - Best-First Search:
        
        Uses an evaluation function f(n) to guide the search.
      - Heuristic Function h(n):
        
        Estimates cost from node n to the goal.
    - - Expands node closest to the goal (using only the heuristic, f(n) = h(n)); may not be optimal.
    - - Combines cost to reach a node g(n) and heuristic estimate h(n), often optimal and efficient (f(n) = g(n) + h(n)).
    - - Never overestimates the cost to reach the goal, guarantees optimality.
- - - - Finds the shortest path in weighted graphs (similar to uniform-cost but for graphs).
      - Edge Relaxation: Updates the cost of reaching a node if a shorter path is found.
    - - Inspired by evolution; solutions are "evolved" over generations through mutation and selection.
      - Fitness Function: Evaluates the quality of a solution (path).