ALGORITHMS - SOLVING PROBLEMS BY SEARCHING

An agent is something that perceives and acts in an environment. Problem solving agents decide what to do by finding sequences of actions that lead to desirable states. The question is: how does such an agent find the best sequence of actions that achieves its goals when no single action can accomplish the task?

There are many search algorithms that can be used to solve different problems; however, some are more efficient than others. A group of general-purpose search algorithms are also known as uninformed or blind algorithms since they are not given no information about the problem other than its definition. Those include depth first search, depth first search and iterative deepening. Informed algorithms are those that have some idea of where to look for solutions to a given problem. Those include best first search and A*. These algorithms tend to make use of a heuristic to come up with a better, more accurate solution to the problem.

The first step in problem sovling is to correctly formulate the problem itself as well as the goal. The problem consists of four parts: the initial state, a set of actions, a goal test function and a path cost function. Once the problem is formulated, a solution is found by a search throughout the state space, or the set of all states reachable from the initial state. The path through the state space form the intinital state to goal state is a solution. Search algorithms are evaluated on the basis of completeness, optimality, time and space complexity.