Chapter 4 - Searching the Knowledge Space I (1).pptx

Department of Computer Sciences College of Computers & Information Technology 501481-3 Artificial Intelligence Chapter 4: Searching the Knowledge Space – Uninformed Search 1 ...

Department of Computer Sciences College of Computers & Information Technology 501481-3 Artificial Intelligence Chapter 4: Searching the Knowledge Space – Uninformed Search 1  Introduction When solving a problem, it’s convenient to think about the solution space in terms of a number of actions that we can take, and the new state of the environment as we perform those actions The space problem is represented by graph To find a solution is equivalent to searching a path in graph  Introduction While solving the problem, some paths may lead to dead-ends while others lead to solutions there may also be multiple solutions, some better than others. The problem of search is to find a sequence of operators that transit from the start to goal state. That sequence of operators is the solution.  Types of Search in AI We have two types of search: Uninformed or blind search and, Informed or heuristic search. In this chapter we are going to study different types of uninformed or blind search. Artificial Intelligence 4 02:28 PM  /Evaluating Search Strategies Completeness: Is the strategy guaranteed to find a solution if one exists? Optimality: Does the solution have low cost or the minimal cost? Complexity: What is the search cost associated with the time and memory required to find a solution? Time complexity: Time taken (number of nodes expanded) (worst or average case) to find a solution. Space complexity: Space used by the algorithm measured in terms of the maximum size of fringe  Evaluating Search Strategies Big-O is used to compare the algorithms. – Defines asymptotic upper bound given: Depth of tree (d). Average number of branches (b) (branch factor).  /Uninformed Search The uninformed search methods offer a variety of techniques for graph search, each with its own advantages and disadvantages Uniformed search, also called blind search and naïve search, is a class of general purpose search algorithms that operate in a brute force way. Outline of Search Algorithm 1. Initialize: Open ={s} 2. Fail: If Open={} then return FAIL. 3. Select: select a state n from Open. 4. Terminate: If n ∈ G then terminate with success. 5. Expand: Generate the successor of n using the operators O and insert them in Open. 6. Loop: Go to step 2. Artificial Intelligence 8 02:28 PM  Improvement on the Search Algorithm 1. Initialize: Open ={s} closed={} 2. Fail: If Open={} then return FAIL. 3. Select: select a state n from Open. Save n in closed 4. Terminate: If n ∈ G then terminate with success. 5. Expand: Generate the successor of n using the operators O. For each successor m, insert them in Open if m ∉ (Open ∪ Closed). 6. Loop: Go to step 2. Artificial Intelligence 9 02:28 PM  Comments on Depth First Search DFS is complete If no cycles in graph DFS is not complete if cycles exist. – If there are cycles in the graph, DFS may get “stuck” in one of them. Solve by checking visited nodes. Disadvantages: – Can get stuck into wrong path, too deep. Artificial Intelligence 10 02:28 PM  Comments on Depth First Search DFS is not optimal. It can “stumble” on longer solution paths before it gets to shorter ones. E.g., goal nodes: red boxes  Comments on Depth First Search Space Complexity - for every node in the path currently explored, DFS maintains a path to its unexplored siblings in the search tree - Alternative paths that DFS needs to explore - The longest possible path is m, with a maximum of b-1 alterative paths per node  Comments on Depth First Search Time Complexity: - In the worst case, must examine every node in the tree E.g., single goal node -> red box  Comments on Breadth First Search BFS is complete (The strategy guaranteed to find a solution if one exists) BFS is optimal (it can find the best goal, in terms of shortest path to the node) Artificial Intelligence 14 02:28 PM Comparison of DFS and BFS Complete Optimal Time Space DFS N N O(bm) O(bm) No cycles: Y BFS Y Y O(bm) O(bm) /Comparison of DFS and BFS