Please enable JavaScript.
Coggle requires JavaScript to display documents.
Pathfinding Algorithms (Search tree (node = state ((Frontier (Frontier…
Pathfinding Algorithms
Searching
types of searching
Graph search
A grid is also a useful way to handle the data.
Uninformed search (blind)
Breadth first
FIFO - first in first out of the queue
Memory bigger problem than execution time
Uniform cost
Expands node with lowest path cost
Changes order of QUEUE
Depth first
LIFO
Backtracking search uses less memory
Depth limited
Has a predetermined limit (no infinity)
Iterative deepening depth first
This limit gradually increases
Bidirectional
Informed search (uses heuristic)
Best first search
Greedy best first search
A*
Search tree
Branch = action
node = state
Parent node
Child node
Leaf node
Frontier
Frontier separates explored and unexplored regions
Set of leaf nodes = frontier or open list
Infrastructure of search algorithm
Require data structure to keep track of search tree = queue = lookup table
Measuring performance of an algorithm
Completeness - guarantee find solution
Optimality - lowest path cost
Time complexity - how long it takes
Space complexity - how much memory required
Genetic algorithms
Measure fitness of each possibility
Use this to determine probability of selection
Randomly match 2 parents
Swap match (like DNA) for offspring
Random mutation