search algorithms are judged on the basis of:
- completeness - find an answer if it exists
- optimality - find the best solution
- time complexity - # of nodes generated, BigO
- space complexity - # of nodes stored in memory
complexity depends on
- b - branching factor
- d - depth of the shallowest solution
- m - maximum depth of any path in the state space
Naive / blind search algorithms (b = branching factor, d = depth of solution, m = max depth of search tree, l = depth limit):
----------------------------------------------------------
- breadth-first search - can be memory intensive, time and space complexity O(b^d), complete and optimum
-- uniform-cost - breadth first but expands the lowest path cost first (greedy), same complexity as breadth-first
- depth-first search - not complete, not optimal, can take a long time, time complexity O(b^m), space complexity is good O(b*m) only -- only keeps node of a single path in memory
-- depth-limited search - has a limit l to the depth, but don't know limiting constant
- iterative deepening search - calls depth-limited with increasing limits, complete and optimal, same complexity as DFS
- bidirectional search, start from begininning and end until they meet halfway, O(b^(d/2))
informed search algorithms:
- best-first / greedy search
- A*
- local beam search - like breadth first search
consistent (triangle inequality): h(n) <= c(n, a, gn) + h(gn)
- n is starting node
- gn is the destination node, in this case, the goal node
- h(gn) = 0
- non-decreasing function
- c(n, a, gn) - cost of action a going from n to gn
- h(n) = cost from node n to goal
admissible - underestimating true (minimum) cost, so it never overestimates the cost
No comments:
Post a Comment