lesson_05.md 4.0 KB

AI - lesson 05

Francesco Arrigoni

21 October 2015

Search Strategies

Ways to select the elements from the frontier

Uninformed search strategies

Know only information from the formulation of the problem.

breadth-first search

Select the element of the frontier which is closest to the root (shallowest solution)
Given the example |A|5|B|5|E|1|D|1|C|1|A| |---|---|---|---|---|---|---|---|---|---|---| Steps:

  1. We select the root of the space-state (state A)
  2. We apply the goal function which results to be false
  3. We expand the selected node and add adjacent items (B,C) to the frontier
  4. We have to select the nearest node to the root, we have a tie so we use the lexycographic order (B)
    • In case of tie we can apply any principle to choose the node
  5. We expand the chosen node (B), adding the adjacent nodes (A,E) to the frontier
  6. We select the shallowest solution like in step 3, (C )
  7. We expand the selected node C, we have another tie in which we select the oldest node (A) ...

If there are no ties, we can manage the frontier as a FIFO queue.

Properties

Is breadth-first search a complete strategy? yes

There is anyway a degerate case in which we have a state space with infinite children, in which we cannot find a solution.

Is this search strategy optimal? no

This strategy finds the solutions which are closest to the root.
In the case in which all the costs are unitary, or in general when the path costs are a non decreasing function of the depth from the root, the closest solution to the root (provided by this algorithm) is also optimal.

Complexity

Time Complexity

Number of nodes that are generated in the worst case

In the worst case (solution in node D) we are generating (nodes at level d) $$1+b+b^2+...+b^d$$ $b$= branching factor: maximum number of children
The time complexity is: $$O(b^{d+1})$$

Improving time complexity The solution node (E) was put in the frontier early but recognized as a solution only later, we apply the goal test when i generate the node rather than when i choose from the frontier. The resulting complexity consists in half the nodes. $$O(b^{d})$$

Space Complexity

The nodes to be kept in memory until a solution is found $$O(b^d)$$

This result if for both version with duplicated list elimination and without it.

Uniform-cost search

The frontier is ordered according to the path cost, according to the space-state weights. Is is called like that because is a special case of another strategy.

Properties

Is breadth-first search a complete strategy? yes

Also in this case there is a degenerated state in which one or more costs are zero and then i keep expanding the same nodes.

Is this strategy optimal? yes

Time Complexity $$O(b^{\lceil C/\varepsilon\rceil})$$ Space Complexity $$O(b^{\lceil C/\varepsilon\rceil})$$

Depth-first search

Select the nodes that are farthest from the root.

This can be seen as a LIFO queue

Propertires

Is breadth-first search a complete strategy? no

If we use the closed list (never expanding two nodes corresponding to the same state), this search trategy is complete

Is this strategy optimal? no

Time Complexity $$O(b^{n})$$ Space Complexity
If we have not found any solution along a branch, we can remove the content of the branch from the memory, we need to keep in memory only one branch at time $$O(bm)$$

Backtracking (dfs variant)

I keep in memory only one node with some informations about the chosen nodes

Depth limited search

I fix a number $l$ which becomes the maximum depth of my search tree

Propertires

Is breadth-first search a complete strategy? yes

Only when $e\ge d$

Is this strategy optimal? no

Time Complexity $$O(b^{e})$$ Space Complexity
$$O(bl)$$

Iterative deepening search

Propertires

Is breadth-first search a complete strategy? yes

Is this strategy optimal? no

Unless costs are all 1

Time Complexity $$O(b^{d})$$ Space Complexity
$$O(bd)$$