lesson_04.md 4.7 KB
AI - lesson 04
Francesco Arrigoni
16 October 2015
Searching for solutions
Steps:
- select the root node
- select the next node
- 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