Lesson 8

Lesson 8 Searching Techniques 8.0 Introduction 8.1 Control Strategies 8.2 Uninformed Search 8.3 Breadth First Search 8.4 Depth First Search 8.5 Advantages and Disadvantages 8.6 Uniform Cost Search 8.7 Depth Limited Search 8.8 Iterative dependency Depth First Search 8.9 Bidirectional Search 8.10 Review Questions 8.11 References

8.0 Introduction : Many of the problems that fall within the purview of artificial intelligence are too complex to be solved by direct techniques rather they must be attacked by appropriate search methods armed with what ever direct techniques available to guide the search. A frame work for describing search methods is provided in this chapter and several general purpose search techniques are given which are called heuristic search. They can be described independently of any particular task or problem domain. But when applied to particular problems their efficacy is highly dependent on the way they eploit domain-specific knowledge since in and of themselves they are unable to overcome the combinational explosion to which search processes are so vulnerable. For this reason , these techniques are often called weak methods.

Although a realizationof the limitred effectiveness of these weak methods to solve hard problems by themselves has been an important result that emerged from the last three decades of AI research , these techniques continue to provide the framework into which domain-specific knowledge can be placed, either by hand or as a result of automatic learning. The basic search techniques available are : Breadth First Search Depth First Search Some simple heuristic Search Techniques are ; • • • • • •

8.1

Generate and Test Hill Climbing Best First search Problem Reduction Constraint Satisfaction Means Ends analysis

Control Strategies :

During the process of searching for a solution to a problem a question arises of how to decide which rule to apply next when more than one rule will have its left side match the current state. Even with out a great deal of though, it is clear that how such decisions are made will have a crucial impact on how quickly and even whether, a problem is finally solved. 8.1.1 8.1.2

The first requirement of a good control strategy is that it cause motion. Control strategies that do not cause motion will never lead to a solution. The second requirement of a good control strategy is that it be systematic. Because the control strategy is not systematic, we may explore a particular useless sequence of operators several times before we finally find a solution. The requirement that a control strategy be systematic corresponds to the need for global motion as well as for local motion .

8.2 Uninformed Search : This section covers five search strategies that come under the heading of uninformed search also called blind search . The term means that they have no additional information about states beyond that provided in the problem definition . All they can do is generate successors and distinguish a goal state from a nongoal state. Strategies that know whether one non goal state is more promising than another are called informed search or heuristic search strategies. All the search strategies are distinguished by the order in which nodes are expanded. 8.2

Breadth First Search :

Suppose for any problem a tree is constructed with the initial state as its root. Generate all the offspring of the root by applying each of the applicable rules to the initial state. Now for each leaf node, generate all its successors by applying all the rules that are appropriate . Continue this process until some rule produces a goal state. This process is call breadth first search. The algorithm of Breadth First Search is as given below:

8.3.1

.Algorithm : Breadth First Search

Step 1: Create a variable called NODE-LIST and set it to the initial state. Step 2: Until a goal state is found or NODE-LIST is empty do : (a) Remove the first element from the NODE-LIST and call it E. If NODE-LIST was empty , quit. (b) For each way that each rule can match the state described in E , do : (i) Apply the rule to generate a new state. (ii) If the new state is a goal state, quit and return this state. (iii) Otherwise , add the new state to the end of NODE-LIST

8.3.2

Example : Two levels of Breadth first Search tree for water jug problem:

(0,0)

(4,0)

(4,3)

(0 , 0)

(0 , 3)

(1 , 3)

(4 , 3)

(0 , 0)

(3,0)

8.4 Depth First Search In another systematic control strategy we could pursue a single branch of the tree until it yields a solution or until a decision to terminate the path is made . It makes sense to terminate a path if it reaches a dead-end, produces a previous state or becomes longer than some prespecified “futility ” limit. In such a case, back tracking occurs. The most recently created state from which alternative moves are available will be received and a new state will be created . This form of backtracking is called chronological backtracking because the order in which steps are undone depends only on the temporal sequence in which the steps were originally made . Specifically the most recent step is always the first to be undone. This form of back tracking is what is usually meant by the simple term

backtracking . The search procedure we have just described is also called depthfirst search. The algorithm of the Depth first search is as given below.

8.4.1

Algorithm : Depth First Search:

Step 1: If the initial state is a goal state, quit and return suiccess. Step 2: Otherwise , do the following until success or failure is signaled: (a) Generate a successor, E, of the initial state. If there are no more successors, fignal failure. (b) Call Depth-First Search with E as the initial state. (c) If success is returned , signal success. Otherwise continue in this loop.

8.4.2

Example : One of the solutions of water jug problem using Depth First Search: (0,3)

(3,0)

(3,3)

(4,,2)

(0,,2)

(2,,2)

8.5

Advantages and Disadvantages

(0,,0)

8.5.1 Advantages of Breadth First Search: •

Breadth First Search will not get trapped exploring a blind alley. This contrasts with depth – first searching , which may follow a single , unfruitful path for a very long time, perhaps forever, before the path actually terminates in a state that has no successors. This is a particular problem in depth first search if there are loops unless special care is expended to test for such a situation. If there is a solution , then breadth first search is guaranteed to find it. Furthermore, if there are multiple solutions, then a minimal solution ie. One that requires minimum number of steps will be found. This is guaranteed by the fact that longer paths are never explored until all shoirter ones have already been examined . This contrasts with depth-first search, which may find a long path to a solution in one part of the tree, when a shorter path exists in some other, unexplored part of the tree.

•

8.5.2 Disadvantages of Breadth First Search: •

8.5.3

Advantages of Depth First Search; •

Depth First Search requires less memory since only the nodes on the current path are stored. This contrasts with breadth first search, where all of the tree that has so far been generated must be stored. By chance or if care is taken in ordering the alternative successor state, depth first search may find a solution without examining much of the search space at all. This contrasts with breadth-first search in which all parts of the tree must be examined to level n before any nodes on level n+1 can be examined . This is particularly significant if many acceptable solutions exist. Depth First Search can stop when one of them is found.

•

8.5.4

More memory is required to store all the tree that has so far been generated.

Disadvantages of Depth First Search: • •

(3,3)

There is no gaurentee of getting a solution If multiple solutions exists , minimal solution is not found very easily.

8.6 Uniform Cost Search Uniform Cost Search is similar to breadth first search but expands the node with lowest path cost g(n) . It is complete and optimal if the cost of each step exceeds some positive bound € .

8.7 Depth Limited Search The problem of unbounded tree can be alleviated by supplying depth first search with a predeterminied depth limit l. That is nodes at depth l are treated as if they have no successors . This approach is called depth limited search . The depth limit solves the infinite path problem. Depth First Search can be viewed as a special case of depth limited search with l = ∞ . Some times depth limits can be based on the knowledge of problem. Depth limited search can be implemented as a simple modification to the general tree search algorithm or to the recursive depth first search algorithm . Depth limited search can terminate with two kinds of failure : The standard failure value indicates no solution. The cutoff value indicates no solution with in the depth limit. The Pseudo code for recursive depth limited search is as given below: function DEPTH – LIMITED –SEARCH (problem, limit) returns a solution, or failure/cutoff return RECURSIVE –DLS(MAKE NODE (INITIAL STATE[problem]),problem,limit) function RECURSIVE-DLS(node, problem ,limit) returns a solution , or failure/cutoff cutoff- occurred? ← false if GOAL-TEST[problem](STATE[node]) then return SOLUTION(node) else if DEPTH[node] = limit then return cutoff else for each successor in EXPAND(node, problem) do result ← RECURSIVE-DLS(Successor, problem , limit) if result = cutoff then cutoff-occurred ? ← true else if result ≠ failure then return result if cutoff-occurred ? then return cutoff else return failure

8.8

Iterative deepening Depth First Search

Iterative deepening search or iterative deepening depth first search is a general strategy often use in combination with depth first search that finds the best depth limit . It does this by gradually increasing the limit first 0 then 1 ,then 2 and so on until a goal is found .This will occur when the depth limit reaches d , the depth of the shallowest goal node.

Iterative deepening combines the benefits of depth first and breadth first search. Like depth first search its memory requirements are very modest and like breadth first search it is complete when the branching factor is finite and optimal when the path cost is a non decreasing function of the depth of the node. The iterative deepening search algorithm is as given below, which repeatedly applies depth limited search with increasing limits. It terminates when a solution is found or if the depth limited search returns failure , meaning that no solution exists. function ITERATIVE-DEEPENING-SEARCH(problem) returns a solution, or failure inputs : problem , a problem for depth ← 0 to ∞ do result ← DEPTH – LIMITED –SEARCH (problem, depth) if result ≠ cutoff then return result In general ,iterative deepening search method is preferred uninformed search method when there is a large search space and the depth of the solution is not known.

8.9 Bidirectional Search The idea behind bidirectional search is to run two simultaneous searches one forward from the initial state and the other backward from the goal , stopping when the two searches meet in the middle. Bidirectional search is implemented by having one or both of the searches check each node before it is expanded to see if it is in the fringe of the other search tree if so a solution has been found. The space requirement is the most significant weakness of bidirectional search . The algorithm is complete and optimal if both searches are breadth first other combinations may sacrifice completeness, optimality or both . The most difficult case for bidirectional search is when the goal test gives only an implicit description of some possibly large set of goal states . for example all the states satisfying the checkmate goal test in chess. A backward search would need to construct compact descriptions of “ all states that lead to checkmate by move m1” and so on. And those descriptions would have to be tested against the states generated by the forward search. There is no general way to do this efficiently.

8.10 Review Questions 1. What are Control Strategies? 2. Explain about Uninformed Search. 3. Write the algorithm for Breadth First Search and explain with an example. 4. Write the algorithm for Depth First Search and explain with an example 5. What are advantages and Disadvantages of BFS and DFS.? 6. What is Uniform Cost Search?

7. Explain Depth Limited Search. 8. Describe Iterative dependency Depth First Search. 9. Write short notes on Bidirectional Search.

8.11 References 1. 2.

Artificial Intelligence A Modern Approach by Stuart Russell and Peter Norvig Artificial Intelligence by Elaine Rich and Kevin Knight