unit 2 ai artificial intelligence 1.pptx

Ai sums

1. UNIT II PROBLEM SOLVING METHODS Problem solving Methods - Search Strategies- Uninformed - Informed - Heuristics - Local Search Algorithms and Optimization Problems - Searching with Partial Observations - Constraint Satisfaction Problems – Constraint Propagation - Backtracking Search - Game Playing - Optimal Decisions in Games – Alpha - Beta Pruning - Stochastic Games. I. Problem Solving Methods Search Strategies Defn : Search algorithms that share basic structure to choose which node/state to be expanded next Classification of Search strategies. The searching algorithms are divided into two categories Uninformed Search Algorithms (Blind Search) Informed Search Algorithms (Heuristic Search) Measuring problem solving performance/ properties of search algorithms Completeness: is 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(Measured as number of nodes generated) Space Complexity : How much memory is needed to perform the search(Measured as maximum number of nodes stored in memory)

2. Uninformed Search Algorithms While searching, there is no clue whether one non-goal state is better than the other. Have no additional information about states beyond that provided in the problem definition All they can do is 1) generate successors ii) differentiate a goal state from non-goal state These algorithms solve any solvable problems

3. Types of Uninformed search are Breadth First Search Uniform-cost search Depth-first search Depth-limited search Iterative deepening depth-first search Bidirectional Search

4. Breadth First Search is a simple strategy in which the root node is expanded first, then all the successors of the root node are expanded next, then their successors, and so on. Is a general graph-search algorithm in which the shallowest unexpanded node is chosen for expansion Is achieved by using queue Example : Route finding problem Task: Find a path from S to G using BFS

5. Performance Measure Complete : Yes Optimal: No Time complexity = 1 +b + b 2 + + b d = O(b d ) Space Complexity : O( b d ) Advantage Guaranteed to find the single solution Not follow unfruitful path for a long time   Disadvantage: Suitable for only smallest instances problem (because it occupies more space)

6. Uniform-cost search[Known as Dijkstra’s Algorithm] An algorithm that is optimal with step cost function Expands the node ‘n’ with the lowest path cost Achieved by using priority queue

7. Note: if all step costs are equal , Uniform cost search is similar to breadth first search Difference between BFS and Uniform Cost Search BFS Uniform cost search Follows FIFO Follows Priority Queue Goal test is applied to the node when it is first generated Goal test is applied to the node when it is selected for expansion No such test Test is added to find better path to a node Uniform-cost search does not care about depth of a path but only about their total cost. Performance Measure Complete : Yes( when the cost is positive number) Optimal: yes Time complexity := O(b [1+C*/e] ) Space Complexity : O(b [1+C*/e] )

8. SBG is the path with minimum path cost. No need to expand the next path SC, because its path cost is high to reach C from S, as well as goal state is reached in the previous path with minimum cost.

9. Depth-first search Peruse a single branch of tree until it yields solution or until a decision to terminate the path is made. Terminating a path happens when it Reaches the dead end Produces a previous state is longer than some pre-specified “ futility limit”

10. therefore DFS always expands the deepest node of the search tree To avoid termination of a path, backtracking is applied. i.e., most recently generated node is chosen for expansion uses last-in-first-out (LIFO) called as a stack. Example: Route finding problem

11. Algorithm Advantages No extra memory Finds the solution without examining much of the search space If more than one solution exists (or) number of levels is high then DFS is best

12. Disadvantages Not guaranteed to find a solution because it might get stuck going down a very long(infinite) path Performance measure Completeness: No Optimal : No Time complexity: O( b m ). Space complexity: O( b m ).

13. Depth - limited search is a variant of DFS with the pre-specified depth limit. Nodes at depth level ‘l’ are treated as if they have no successors Solve infinite path problem which exists in DFS DLF terminates with 2 kinds of failure The standard failure value indicates no solution No solution within depth limit=> cutoff