Search

1. UCS

1.1. Construct the tree by choosing the best node in the agenda after each expansion, according to the utility function.

1.2. It guarantees to find the solution if there is one.

1.3. It guarantees to find the best action sequence in terms of utility.

1.4. It can't guarantee to use less memory than BFS.

1.5. The aim is to find the low cost solution. Extra knowledge is provided by a heuristic which returns a number describing desirability of expanding a given node.

2. IDS

2.1. A compromise between DFS and BFS.

2.2. It's optimal.

2.3. It's complete.

2.4. Some states are expanded multiple times.

3. A*

3.1. It adopts algorithm A by using an admissible heuristic

3.2. Admissible means it never over-estimates the distance to the closest solution.

3.3. It's optimal. It's guaranteed to find a solution if there is one.

4. DFS

4.1. Construct the tree by going down it, only going across when going down fails.

4.2. Faster than BFS when the tree is bushy

4.3. Not suitable when tree is infinite deep

4.4. Not suitable when tree has loops

5. BFS

5.1. Construct the tree by going across it.

5.2. It's complete. All nodes are examined if b is finite.

5.3. It's optimal. It finds the solution with the smallest steps.

5.4. It has high memory and computational cost as it stores all the nodes in memory.

5.5. It also does not optimise utility function. So its solution does not guarantee to have the minimum cost