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 11:59 AM  /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  /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.  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 7 11:59 AM  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 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 10 11:59 AM 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