Chapter 2 -- Uninformed Search.ppt

Chapter 2 – Uninformed Search Chapter Outline Introduction  Uninformed – search is brute-force search Also called Blind or Naïve Search.  Important for AI, as problem solving in AI is predominantly search related  Does not consider the solution space  Informed search methods include some...

Chapter 2 – Uninformed Search Chapter Outline Introduction  Uninformed – search is brute-force search Also called Blind or Naïve Search.  Important for AI, as problem solving in AI is predominantly search related  Does not consider the solution space  Informed search methods include some heuristic (knowledge of the solution space) State Space Search    Search operates on a search space, with states and operates that transition between states. Can be applied to problems in a variety of ways. Graphs are an obvious representation for state spaces. Search Applied to Puzzles     Puzzles can be easily represented by state spaces (or built into state spaces). One interesting example is the “Tower of Hanoi.” Each move (operation) results in a new configuration (state) Brute-force can be used to find a specific state given an initial state (find a solution). Adversarial Search    Adversarial search allows a computer to find an effective strategy for playing against a human. The Game of Nim shown Computer/Human moves restrict the search space. –  For example, if at the start the human chooses 1 item, the left subtree is used. Search is used to identify the next move to make to ensure a win (shaded states). Representations    The graph is a useful representation for a state space. A graph is made up of vertices (nodes) connected by edges (arcs). Graphs are easily represented by adjacency matrices. Uninformed Search Algorithms  Depth-First-Search (DFS)  Depth-Limited-Search (DLS)  Iterative-Deepening Search (IDS)  Breadth-First-Search (BFS)  Bidirectional Search (BIDI)  Uniform Cost Search (UCS) Depth-First-Search (DFS)  Search each branch to its greatest depth, backtrack, explore previously unexplored branches.  LIFO-stack based for to-be-visited nodes.  Simple, but favors depth over breadth. Depth-Limited Search (DLS)  DFS with depth limitation.  Perform DFS but halt search of nodes below a specified depth. Iterative-Deepening Search (IDS)  DLS, with increasing depth until state is found.  Starts with a depth (d), if goal isn’t found, increase the depth and try again. Breadth-First-Search (BFS)  Search nodes shallowest first.  Queue-based implementation (FIFO) for to-bevisited nodes.  Favors breadth over depth. Bidirectional Search   When initial and goal states are known, and path is what is desired, bidirectional search is useful. Two concurrent searches to build path, when they meet (at a common node), a path is found. Uniform-Cost Search (UCS)     Find the least-cost path through a graph. Not all edges the same cost. Goal to find the path from start to finish with least cost (A->E). Implemented with priority queue that defines the priority of nodes to evaluate. Algorithm Summary Algorithm Time Space Optimal Complete Derivative DFS O(Bm) O(bm) No No DLS O(Bl) O(bl) No No DFS IDS O(Bd) O(bd) Yes No DLS BFS O(Bd) O(bd) Yes Yes BIDI O(Bd/2) O(Bd/2) Yes Yes BFS UCS O(Bd) O(Bd) Yes Yes BFS