As a simple assignment for my Introduction to Artificial Intelligence course (CSE 586) at Miami University, we were tasked with implementing a number of simple search algorithms.
| Time Complexity | Space Complexity | Complete | Optimal |
|---|---|---|---|
| O(bd) | O(bd) | Yes (if finite) | Yes (if all edges are the same) |
Breadth-first search is a search in which nodes are expanded via the shallowest node first:
- Examine states one step away from the initial state.
- Examine states two steps away from the initial state.
- and so on...
Consequently, this does not guarantee the optimal path. However, this does guarantee that the resultant path will have the least number of edges.
| Time Complexity | Space Complexity | Complete | Optimal |
|---|---|---|---|
| O(bd) | O(bd) | Yes (if finite) | Yes |
When all step costs are equal, BFS is optimal because it always expands the shallowest unexpanded node. This is not true when step cost are not equal. By a simple extension, there is an algorithm that is optimal with any step-cost function.
Compared to BFS, Instead of expanding the shallowest node, UCS expands the node n with the lowest path cost g(n). Let g(n) = cost of path from start node s to current node n Thus, nodes are sorted by by increasing value of g using a priority queue to order nodes on the frontier list.
| Time Complexity | Space Complexity | Complete | Optimal |
|---|---|---|---|
| O(bm) | O(bm) | No (loops or infinite non-goal path) | No |
The depth-limited search expands via the deepest node first. Specifically:
- Select a direction go to the end.
- Slightly change the end
- Slightly change the end some more...
- Once a node has been expanded, it can be removed from memory as soon as all its descendants have been explored.
However, however only performs up to a certain level l where l is less than or equal to the depth of the graph.
| Time Complexity | Space Complexity | Complete | Optimal |
|---|---|---|---|
| O(bd) | O(bd) | Yes (if finite) | Yes |
As an extension of DFS, IDS becomes optimal by doing a DFS search level by level:
- Perform DFS to a depth of 1 and treat all children of the start node a leaves.
- If no solution found, do DFS to a depth of 2.
- Repeat by increasing depth bound until a solution is found.
Trades a little time for a huge reduction in space: lets you do a BFS search with a (more space efficient) depth-first search.
| Time Complexity | Space Complexity | Complete | Optimal |
|---|---|---|---|
| O(bd) | O(bd) | Yes (if finite) | Yes |
The A* algorithm is in many ways similar to the UCS mentioned above. However, there is a simple modification; the addition of a heuristic function. Rather than chosing the next nodes with the lowest arc weight, the next node is chosen based on the sum of the arc weight and an arbitrary heuristic function.
The aforementioned searches have been implemented using C# and the .NET 6.0 framework.
They use the following inheritance structure where are searches are derived from the UninformedSearch class.
Additionally, all implementations make use of Object-Oriented approach that makes extensive use of a Node and Arc class instead of matrices and adjacency lists. The classes were used to avoid overhead in non-sparse graphs.
All source files can be found in UninformedSearches/.
The specific implementations for each search can be found in UninformedSearches/Searches.
The following graph can be built using Nodes and Arcs as follows.
The Graph
Source Code
Node<char> a = new('A');
Node<char> b = new('B');
Node<char> c = new('C');
Node<char> d = new('D');
Node<char> e = new('E');
Node<char> f = new('F');
a.AddArc(b, 2);
a.AddArc(c, 1);
b.AddArc(d, 1);
b.AddArc(e, 3);
c.AddArc(e, 3);
d.AddArc(e, 1);
d.AddArc(f, 2);
e.AddArc(f, 4);Once a graph is constructed, simply pass the start node and destination node in a class derived from UninformedSearch.
UninformedSearch<T> ucs = new UniformCostSearch<T>();
.
.
.
Build your graph here
.
.
.
List<Node<T>>ucs.GetPath(start, destination);
For instance, in the case of the section 2.1 graph, if you wanted to find the path from 'A' to 'E', the code would like:
UninformedSearch<char> ucs = new UniformCostSearch<char>();
Node<char> a = new('A');
Node<char> b = new('B');
Node<char> c = new('C');
Node<char> d = new('D');
Node<char> e = new('E');
Node<char> f = new('F');
a.AddArc(b, 2);
a.AddArc(c, 1);
b.AddArc(d, 1);
b.AddArc(e, 3);
c.AddArc(e, 3);
d.AddArc(e, 1);
d.AddArc(f, 2);
e.AddArc(f, 4);
List<Node<T>>ucs.GetPath(a, e);