L_02_Searching Algorithms in AI.pdf

Artificial Intelligence (AI) Search Algorithms in AI Lecture 02 11-05-2024 Bachelor of Science (Hons) in Computer Science...

Artificial Intelligence (AI) Search Algorithms in AI Lecture 02 11-05-2024 Bachelor of Science (Hons) in Computer Science | Software Engineering Department of Computing Faculty of Computing and Technology Saegis Campus Nugegoda 1 MS. DMS Sathsara Saegis Campus Session outline Searching Algorithms Problem solving Agents Searching Algorithm Techniques Properties of Search Algorithms Types of Search Algorithms ✓Uniformed/Blind Search ✓Informed Search 2 MS. DMS Sathsara Saegis Campus  Searching Algorithms Search algorithms are fundamental in the field of artificial intelligence (AI) as they provide the means for navigating through different paths in problem solving, optimization tasks, and decision-making processes. They are particularly critical in domains such as game theory, robotics, scheduling, network analysis, and many others. 3 MS. DMS Sathsara Saegis Campus  Problem solving agents In Artificial Intelligence, Search techniques are universal problem-solving methods. Rational agents or Problem-solving agents in AI mostly used these search strategies or algorithms to solve a specific problem and provide the best result. Problem-solving agents are the goal-based agents and use atomic representation. 4 MS. DMS Sathsara Saegis Campus  Search Algorithm Technologies Search: Searching is a step by step procedure to solve a search-problem in a given search space. A search problem can have three main factors: Search Space: Search space represents a set of possible solutions, which a system may have. Start State: It is a state from where agent begins the search. Goal test: It is a function which observe the current state and returns whether the goal state is achieved or not. 5 MS. DMS Sathsara Saegis Campus  Search Algorithm Technologies Search tree: A tree representation of search problem is called Search tree. The root of the search tree is the root node which is corresponding to the initial state. Actions: It gives the description of all the available actions to the agent. Transition model: A description of what each action do, can be represented as a transition model. Path Cost: It is a function which assigns a numeric cost to each path. Solution: It is an action sequence which leads from the start node to the goal node. Optimal Solution: If a solution has the lowest cost among all solutions. 6 MS. DMS Sathsara Saegis Campus  Properties of search Algorithms Following are the four essential properties of search algorithms to compare the efficiency of these algorithms: Completeness: A search algorithm is said to be complete if it guarantees to return a solution if at least any solution exists for any random input. Optimality: If a solution found for an algorithm is guaranteed to be the best solution (lowest path cost) among all other solutions, then such a solution for is said to be an optimal solution. 7 MS. DMS Sathsara Saegis Campus  Properties of search Algorithms Time Complexity: Time complexity is a measure of time for an algorithm to complete its task. Space Complexity: It is the maximum storage space required at any point during the search, as the complexity of the problem. 8 MS. DMS Sathsara Saegis Campus  Types of search Algorithms Based on the search problems we can classify the search algorithms into two main categories: 1. Uninformed (or blind) search 2. Informed (or heuristic) search. 9 MS. DMS Sathsara Saegis Campus  Uniformed/Blind Search The uninformed search does not contain any domain knowledge such as closeness, the location of the goal. It operates in a brute-force way as it only includes information about how to traverse the tree and how to identify leaf and goal nodes. Uninformed search applies a way in which search tree is searched without any information about the search space like initial state operators and test for the goal, so it is also called blind search. It examines each node of the tree until it achieves the goal node. 10 MS. DMS Sathsara Saegis Campus  Uniformed/Blind Search It can be divided into five main types: 1. Breadth-first search 2. Depth-first search 3. Uniform cost search 4. Depth Limited Search 5. Iterative deepening depth-first search 11 MS. DMS Sathsara Saegis Campus  Uniformed/Blind Search Breadth-First Search (BFS): Explores all nodes at the present depth prior to moving on to nodes at the next depth level. Guarantees the shortest path in an unweighted graph. Uses significant memory to store the frontier. 12 MS. DMS Sathsara Saegis Campus  Uniformed/Blind Search Breadth-First Search (BFS): 13 MS. DMS Sathsara Saegis Campus  Uniformed/Blind Search Breadth-First Search (BFS): 14 MS. DMS Sathsara Saegis Campus  Uniformed/Blind Search Breadth-First Search (BFS): 15 MS. DMS Sathsara Saegis Campus  Uniformed/Blind Search Breadth-First Search (BFS): 16 MS. DMS Sathsara Saegis Campus  Uniformed/Blind Search Breadth-First Search (BFS): 17 MS. DMS Sathsara Saegis Campus  Uniformed/Blind Search Breadth-First Search (BFS): 18 MS. DMS Sathsara Saegis Campus  Uniformed/Blind Search Breadth-First Search (BFS): 19 MS. DMS Sathsara Saegis Campus  Uniformed/Blind Search Depth-First Search (DFS): Explores as deep as possible along each branch before backtracking. Uses less memory than BFS. Does not guarantee the shortest path. 20 MS. DMS Sathsara Saegis Campus  Uniformed/Blind Search Depth-First Search (DFS): 21 MS. DMS Sathsara Saegis Campus  Uniformed/Blind Search Depth-First Search (DFS): 22 MS. DMS Sathsara Saegis Campus  Uniformed/Blind Search Depth-First Search (DFS): 23 MS. DMS Sathsara Saegis Campus  Uniformed/Blind Search Depth-First Search (DFS): 24 MS. DMS Sathsara Saegis Campus  Uniformed/Blind Search Depth-First Search (DFS): 25 MS. DMS Sathsara Saegis Campus  Uniformed/Blind Search Depth-First Search (DFS): 26 MS. DMS Sathsara Saegis Campus  Uniformed/Blind Search Uniform Cost Search: Expands the least cost node first. Essentially a breadth-first search that accounts for varied step costs. Provides a path with the lowest total cost. 27 MS. DMS Sathsara Saegis Campus  Uniformed/Blind Search Depth-Limited Search: A variation of DFS that limits the maximum depth to prevent infinite loops and reduce memory overhead. For more: https://ai-master.gitbooks.io/classic-search/content/what-is-depth- limited-search.html 28 MS. DMS Sathsara Saegis Campus  Uniformed/Blind Search Iterative Deepening Depth-First Search (IDDFS): Combines depth-first’s memory efficiency and breadth-first’s completeness (guarantee of finding a solution if it exists). Repeatedly deepens the limit until a solution is found. 1'st repetition-----> A 2'nd repetition----> A, B, C 3'rdrepetition-----> A, B, D, E, C, F, G 4'th repetition------>A, B, D, H, I, E, C, F, K, G 29 MS. DMS Sathsara Saegis Campus  Informed Search Informed search algorithms use domain knowledge. In an informed search, problem information is available which can guide the search. Informed search strategies can find a solution more efficiently than an uninformed search strategy. Informed search is also called a Heuristic search. 30 MS. DMS Sathsara Saegis Campus  Informed Search A heuristic is a way which might not always be guaranteed for best solutions but guaranteed to find a good solution in reasonable time. Informed search can solve much complex problem which could not be solved in another way. An example of informed search algorithms is a traveling salesman problem. Greedy Search, A* Search 31 MS. DMS Sathsara Saegis Campus  Informed Search Greedy Best-First Search: Chooses nodes based on a heuristic function that estimates the cost from a node to the goal. Not guaranteed to find the shortest path but tends to be fast. More: https://www.geeksforgeeks.org/greedy-best-first-search-algorithm/ 32 MS. DMS Sathsara Saegis Campus  Informed Search A Search: Extends Greedy Best-First Search by incorporating both the heuristic and the cost so far to determine which node to expand. Guarantees the shortest path with an admissible and consistent heuristic. Widely used due to its effectiveness and efficiency. More: https://www.geeksforgeeks.org/a-search-algorithm/ 33 MS. DMS Sathsara Saegis Campus  Summary…. Searching Algorithms Problem solving Agents Searching Algorithm Techniques Properties of Search Algorithms Types of Search Algorithms 34 Lecturer MS. DMSName Sathsara Saegis Campus