Assumptions to be made
b(branching factor): at each level what is the maximum number of nodes which you can have.
m(depth factor): The maximum depth which you can have.
Complete algorithm: If an algorithm guarantees to produce a solution if there exist one, then it is a complete
algorithm.
Optimal algorithm: When the algorithm produce a solution, it is guaranteed to be the best solution.
Fringe: the nodes that have been discovered but yet to be expanded.
DFS on graph problem
Description: In this case, DFS explore a path until there is no more nodes to be explored, and then move back
for exploring another path.
Method: Using a stack (which we don't know the order of insertion), for each node, push the branching nodes
to the stack one back one, and pop the last one to continue following.
Time complexity: Since we have a tree, start from the root we have b number of choices, at level 2 we have b +
1 operations, and then we have b^2 number of nodes to process ... then at depth m, we have b^m number of
nodes to be processed.
Therefore the time complexity overall is 1 + b + b^2 + b^3 + .... + b^m number of operations. At the end, we will
achieve O(b^m) time complexity.
Space complexity: Since at each level we will have b number of nodes, we store them, and as we move along
that one path we select, we have O(bm). As each layer contains b number of nodes and there are m levels in
total.
BFS
Description: BFS in this case explore the nodes layer by layer, until depth s (the depth of the goal), you reach
the final state.
Method: Storing nodes to a queue and dequeue one by one.
Time complexity: O(b^s) as s being the depth of the final state.
Space complexity: O(b^s) as at the final layer, your queue contains either all the nodes from the next layer or
the current layer (depending how left is the node to you at that layer). Therefore the space complexity is O(b^s)
as well.
Uniform cost search
Time complexity explanation
![[Pasted image [Link]]]
So the intuition for UCS's time complexity is, I take the lowest cost edge among the entire graph x, and then I
have the lowest cost to reach the goal z. The worst case where every step has the minimum cost x gives me z/x
steps. So that many number of steps produce b ^z/x number of operations. Now we call the solution cost as C,
and the minimum arc cost as ε, then the time complexity will be O(b^C/ε).
Heuristic (estimate)
admissible heuristic
a heuristic function is admissible if h(n) <= h*(n)
meaning it is always lower cost than the optimal solution
consistent heuristic
a heuristic is consistent if h(n) <= c(n, a, n') + h(n')
meaning the direct estimate is always smaller than going to another state and estimate again.
Find admissible heuristic
Relax the restrictions and find the optimal solution, is the admissible heuristic of the original problem.
Finding the better heuristic:
if h1(n) > h2(n), then h1 dominates h2 and h1 is a better heuristic.
For example in the path finding example, if we just relax the restriction until we can teleport (h2), it is not as
good as h1 (ignore road) as it provides a worse estimate as we apply it to the original problem.
Overall time complexity comparison
![[Pasted image [Link]]]
The proof for why A* with memory is only optimal when heuristic is consistent.
![[Pasted image [Link]]]