Uniform cost search - HiIAmTzeKean/SC3000-Artificial-Intelligence GitHub Wiki
tags:
- 🌱
- AI
- ComputerScience
- Search date: 18--Apr--2023
Also known as Dijkstra or shortest-path algorithm.
- Considers edge cost unlike Breadth first search of
$g(n)$ -
Breadth first search of
$Depth(n)$ = Uniform cost search of$g(n)$
-
Breadth first search of
- Priority queue instead of FIFO in Breadth first search
- Complete
- Yes
- Optimal
- Yes
- Time
- Number of nodes with path cost shorter than cost of optimal path = Number of nodes pop from priority queue
- Worse case size of priority queue is
$O(b^d)$ at lowest level- Fix heap cost
$O(lg(n))$ $1+b+lg(b)+b^2+lg(b^2)+...=1+b+b^2...+lg(b)+lg(b^2)+...=\sum_{i=0}{b^i}+\sum_{i=1}{lg(b^i)}$ - Simplified to
$O(b^d)$
- Fix heap cost
- Space
- Number of nodes with path cost shorter than cost of optimal path
- Worse case it will be similar to the FIFO queue size in Breadth first search
$O(b^d)$
Links: