# AI - lesson 04
#### Francesco Arrigoni
###### 16 October 2015
## Searching for solutions
#### Steps:
1. select the __root node__
2. select the __next node__
3. apply the __goal function__ to the selected node
    - If function is true: end
    - if function is false, 4. generate the __successor nodes__

#### Steps in detail
- First, The root is created
- After chosing the first node, i have to choose another node, different than the root,  
for doing this we define a __frontier__ containing the nodes that are reachable but are not yet analized.
- Next, i chose a node from the frontier, eliminating it from the latter, i applicate the goal function, and if the function is false, i expand the node, creating the next nodes and add them to the frontier.

> The frontier contains only leaf nodes of the tree (but not all leafs, see next def.)  

> There can be leaf nodes that are not in the frontier, for example already analized nodes with no childrens

*Search tree* __nodes__ and *State space* __states__ are __different!__

For example the same state in the state space can be represented by multiple nodes in the search tree.

__nodes__ in the search tree correspond to __paths__ in the *state space*, the state space __path__ is composed by nodes from the root to the node in the __search tree__

#### Informations contained in a node data structure:
- The corresponding __state__  
ex: 1, 1
- The pointer to the __father__  
ex: null, node 4
- The __action__ that has brought to that node  
ex: null, action a
- The __path cost__ $g(n)$ to reach that node  
ex: 0, 3

As we have seen both nodes correspond to state 1 but they are different entities.

#### Choosing the next node from the frontier
- I can choose the node corresponding to the smallest state (not clever)
- It is better to keep the frontier ordered to some criteria and select the first node in that order (no need to implement policies)
- For example the frontier can be implemented as a __priority queue__

#### Is it necessary to keep different path to the same states?
No, it is not but we have some constraints.

#### How can i do to eliminate multiple paths to the same state in the search tree
I can use a data structure historically called __closed list__ (or explored set)

In the __closed list__ you keep the __states__ for with you have already selected a node.  
For example:
- When i select the node 1, the goal test fails, i will expand it and add to the closed list.
- Next i select node 2 from the frontier, the goal test fails and __before expanding__ i will __check if node 2 is already in closed list__, otherwise i expand it and add to the closed list.
- If i find a node that is __already on the closed__ list i will __not expand it__ and select another node from the frontier.

To be sure to find an __optimal solution__ i need to be sure that the first path that i find to the state is the __minimum cost path__.

#### The use of closed list ensures:
- Every time you expand a node, you add to the closed list
- Before expanding a node, you check first if it is on the closed list.

#### Versions of the tree search algorithm
- __With closed list__ (with elimination of repeated states) in book is called GRAPH-SEARCH
- __Without closed list__ (without elimination of repeated states) in book is called TREE-SEARCH

The definitions in parenthesis are wrong because states are not repeated, we eliminate nodes that lead to the same states.  
The upcase names indicates that the second algorithm is optimal for states spaces that are trees (quite twisted naming convention from the book).

#### When I can say that i have no solutions?
If the frontier is empty.
In the *closed list version* of the algorith i can detect that the problem has no solutions, while with the version *without closed list* i can not detect that the problem has no solutions before exploring all the different paths.

#### Why is the version without closed list used?
Because the closed list can take a lot of space in memory, while the version without it uses way less memory.

#### Search strategies
Ways of selecting nodes from the frontier, can be:
- __completeness__: when i can guarantee that if the solution exists, i will find it.
- __optimality__: when i can guarantee that i can find the minimum cost solution.
- __complexity__: can be measured as
    - __space complexity__: number of nodes generated in the search tree
    - __time complexity__:

These properties can be evaluated according to four parameters:
- __Branching factor__ $b$: the maximum number of children that a node can have
- __Depth of the less deep solution__ $d$: solutiuon which is closest to the root
- __Maximum path length in state space__ $m$: can be infinite
- __Cost of the optimal solution__ $c^*$
If all the costs are 1 i can claim that $d$ and $c^*$ are the same