# Introduction

A problem can be defined formally by several components

**Initial state**is the state that the solving agent starts in.**Actions**are the possible applicable operation that the agent can perform in a particular state**Transition model**is the description of what the action does. An action applied at a given state will produce a new state (called**successor**). A**state space**is defined using the initial state, the actions and the transitional model. It defines a graph where each node represent a state and each edge represent the action.- The
**goal test**is used to determine whether a state represent the actual goal. **Path cost**is a function that assign a numeric cost to each path (a set of nodes and edges from the initial state to the goal state). The**step cost**represent the cost of going from one state to another with a single action. Finally, a solution is defined as a set of actions that leads from initial state to goal state.

When formulation a problem, there can be two kind of formulation

**Complete**- The initial state contains the entire data to solve the problem. It’s only a matter of finding the right action that modify the data that is already available.**Incremental**- Starting from the initial state, an operator that augment the state description is used add the data to get to the goal state

## Searching for solutions

The possible actions sequence starting from the initial state represents a **search tree**. To reach a solution, the initial state is first expanded: a new set of state is generate by applying each legal action to the current state. The new state are child node of the previous state that can be in turn expanded (the set of state yet to be expanded is called **frontier** or **open list**). What differentiate a search algorithm from one another is the **search strategy**, namely the policy they use to expand new node.

It may happen that legal action bring inevitably to already seen state. A search algorithm that produce redundant path is called **three-search** algorithm, while an algorithm that avoid them is called **graph-search** algorithm and can be constructed by augment the tree-search with a new data structure to keep track of the expanded node (usually called **explored set** or **closed list**).

When analyzing a search algorithm it’s important to consider different criteria

**Completeness**: Will the algorithm always find a solution when there is one?**Optimality**: Will the algorithm find the optimal/best solution to the problem?**Time and memory complexity**: How much time and memory is required by algorithm to find the solution?