Please enable JavaScript.
Coggle requires JavaScript to display documents.
Path-Finding Algorithms (Search Trees (The Frontier (Also known as Open…
Path-Finding Algorithms
Search Trees
Hierarchy of linked Node
Represent particular stage of Node
Node Represent State
Branch represent Action
After reached goal, search will not expand
The Frontier
Also known as Open List
Frontier has Many nodes Known as
LEAF NODE
Each LEAF NODE has
PARENT NODE
and
CHILD NODES
Separate Explored and Unexplored regions
Maintain
Closed list
for Already explored regions to avoid repeat
Infrastructure
Require for keep track
NODE
State
Parent
Action
Cost
Performance Measure
Completeness
Optimality
Time Complexity
Space Complexity
Search
Uninformed Search
Breadth first
Use Queue (First in first out)
Memory problem can be occur
Uniform cost
Expand path using lowest Cost
Change order of queue
Depth first
Use Queue (First in first out)
Less Memory for back tracing
Depth limited
Per determine limit
Concern diameter of the problem
Iterative deepening depth first
Limit of the search increase slowly
Bidirectional
Informed Search
Best first search
expanded based on evaluation function
Function Decide the search strategy Includes heuristic
Heuristic estimate the cost of cheapest path to achieve the goal
Greedy best first search
Use only Heuristic
Expand the closest node to goal
Doesn't go back to explore other nodes
f(n) = h(n)
A*
Cost of each node = (cost of edge + previous cost )+ estimated cost to reach target
f(n) = g(n) + h(n)
Take into account an estimate of cost to target
Underestimate guarantees optimal path
Stops you heading in wrong direction