Ways to select the elements from the frontier
Know only information from the formulation of the problem.
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:
If there are no ties, we can manage the frontier as a FIFO queue.
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.
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.
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.
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})$$
Select the nodes that are farthest from the root.
This can be seen as a LIFO queue
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)$$
I keep in memory only one node with some informations about the chosen nodes
I fix a number $l$ which becomes the maximum depth of my search tree
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)$$
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)$$