Share

## The Importance of search in Artificial Intelligence and which search algorithm one should use?

Question

Lost your password? Please enter your email address. You will receive a link and will create a new password via email.

## Answer ( 1 )

This answer is edited.Problem solving is an important aspect of Artificial Intelligence. A problem can be considered to consist of a goal and a set of actions that can be taken to lead to the goal. At any given time, we consider the state of the search space to represent where we have reached as a result of the actions we have applied so far. For example, consider the problem of looking for a contact lens on a football field. The initial state is how we start out, which is to say we know that the lens is somewhere on the field, but we don’t know where. If we use the representation where we examine the field in units of one square foot, then our first action might be to examine the square in the top-left corner of the field. If we do not find the lens there, we could consider the state now to be that we have examined the top-left square and have not found the lens. After a number of actions, the state might be that we have examined 500 squares, and we have now just found the lens in the last square we examined. This is a goal state because it satisfies the goal that we had of finding a contact lens. Search is a method that can be used by computers to examine a problem space like this in order to find a goal. Often, we want to find the goal as quickly as possible or without using too many resources. A problem space can also be considered to be a search space because in order to solve the problem, we will search the space for a goal state.We will continue to use the term search space to describe this concept. In this chapter, we will look at a number of methods for examining a search space. These methods are called search methods.

The Importance of Search in AI: It has already become clear that many of the tasks underlying AI can be phrased in terms of a search for the solution to the problem at hand.

Many goal based agents are essentially problem solving agents which must decide what to do by searching for a sequence of actions that lead to their solutions.

For production systems, we have seen the need to search for a sequence of rule applications that lead to the required fact or action.

For neural network systems, we need to search for the set of connection weights that will result in the required input to output mapping.

Which search algorithm one should use will generally depend on the problem domain?There are four important factors to consider:

Completeness – Is a solution guaranteed to be found if at least one solution exists?

Optimality – Is the solution found guaranteed to be the best (or lowest cost) solution if there exists more than one solution?

Time Complexity – The upper bound on the time required to find a solution, as a function of the complexity of the problem.

Space Complexity – The upper bound on the storage space (memory) required at any point during the search, as a function of the complexity of the problem.