Breadth first search - HiIAmTzeKean/SC3000-Artificial-Intelligence GitHub Wiki
tags:
- 🌱
- AI
- ComputerScience
- Search date: 18--Apr--2023
- Expands shallowest node by each level
- Typically use FIFO queue
- All step cost equal to guarantee optimality
- Complete
- Yes
- Optimal
- If all steps have equal cost
- Space
- Every frontier node must be kept in memory
- Explored nodes are dequeued
$O(b^d)$
- Every frontier node must be kept in memory
- Time
- Summation of nodes explored at each level
$1+b^2+b^3...+b^d=\frac{b^{d-1}-1}{d-1}=O(b^d)$
$O(b^d)$
- Summation of nodes explored at each level
Links: