Artificial Intelligence-5
Measuring problem-solving problems
- Completeness: Is the algorithm guaranteed to find a solution when there is one?
- Optimality: Does the strategy find the optimal solution?
- Time complexity: How long does it take to find a solution?
- Space complexity: How much memory is needed to perform the search?
Uninformed Search Algorithms
While searching you have no clue whether one non-goal state is better than any other. Your search is blind. You don’t know if your current exploration is likely to be fruitful.
- Breadth-First Search(BFS)
- Uniform-Cost Search
- Depth-First Search
- Depth-Limited Search
- Iterative Deepening Search
- Bidirectional Search
Breadth-First Search
Expand shallowest unexpanded node
fringe is a first-in-first-out (FIFO) queue, i.e., new successors go at end of the queue.
Properties of Breadth First Search
- Complete? Yes it always reaches goal (if b is finite)
- Time? 1+b+b 2+b 3+… +b d + (b d+1 -b)) = O(bd+1) (this is the number of nodes we generate)
- Space? O(b d+1 ) (keeps every node in memory, either in fringe or on a path to fringe).
- Optimal? Yes (if we guarantee that deeper solutions are less optimal, e.g. step-cost=1).
Uniform-Cost Search
Expand node with smallest path cost g(n). “f(n)=g(n)”
fringe = queue ordered by path cost Equivalent to breadth-first if all step costs all equal.
S-A=1,S-B=5,S-C=15;S-A-G=1+10=11>5
S-B=5,S-B-G=5+5=10<11,15 so it is our path.
Properties of Uniform-Cost Search
- Complete? Yes, if step cost ≥ ε (otherwise it can get stuck in infinite loops)
- Time? # of nodes with path cost ≤ cost of optimal solution.
- Space? # of nodes with path cost ≤ cost of optimal solution.
- Optimal? Yes, for any step cost ≥ ε
Depth-First Search
Expand deepest unexpanded node
fringe = Last In First Out (LIFO) queue, i.e., put successors at front
Properties of Depth-First Search
- Complete? No: fails in infinite-depth spaces Can modify to avoid repeated states along path
- Time? O(b m ) with m=maximum depth
-terrible if m is much larger than d
-but if solutions are dense, may be much faster than breadth-first
- Space? O(bm), i.e., linear space! (we only need to remember a single path +expanded unexplored nodes)
- Optimal? No (It may find a non-optimal goal first)
Depth-Limited Search
The embarrassing failure of depth-first search in infinite state spaces can be alleviated by supplying depth-first search with a predetermined depth limit . That is, nodes at depth are treated as if they have no successors. This approach is called depth-limited search .Depth limit solves the infinite-path problem.
Iterative Deepening Search
- To avoid the infinite depth problem of DFS, we can decide to only search until depth L, i.e. we don’t expand beyond depth L.
→ Depth-Limited Search
- What if solution is deeper than L? → Increase L iteratively.
→ Iterative Deepening Search
Properties of Iterative Deepening Search
- Complete? Yes
- Time? O(b^d)
- Space? O(bd)
- Optimal? Yes, if step cost = 1 or increasing function of depth.
Bidirectional Search
Idea
◼ simultaneously search forward from S and backwards from G
◼ stop when both “meet in the middle”
◼ need to keep track of the intersection of 2 open sets of nodes
What does searching backwards from G mean
◼ need a way to specify the predecessors of G
•this can be difficult,
• e.g., predecessors of checkmate in chess?
◼ which to take if there are multiple goal states?
◼ where to start if there is only a goal test, no explicit list?
Summary of algorithms
References:
- Prateek Joshi, “Artificial Intelligence with Python : A Comprehensive Guide to Building Intelligent Apps for Python Beginners and Developers”, 1 st Ed., Packt Publishing, 2017.
- Stuart Russell and Peter Norvig, “Artificial Intelligence: A Modern Approach” , 3rd Ed., Prentice Hall, 2010.
