University of Windsor Winter 2021
Comp 3710 Artificial Intelligence Concepts.
Assignment 1 (Points 10)
Due on 04/02/2021 Before 11:59pm
Part I: (Points 8)
The graph search algorithms are important in AI. This assignment considers the following uninformed
graph search algorithms in a given graph.
1. Breadth First Search (BFS) (2 points)
2. Depth First Search (DFS) (2 points)
3. Iterative Deepening Search (IDS) (2 points)
4. Uniform Cost Search (UCS) (2 points)
Your task is to implement the above algorithms to find the traversal path and exact path of any given
graph (State Space Graph). You can use any programming language.
Hint: A state-space graph can be represented as a search tree; the start state is the root node, and
children correspond to successors. There are two popular options for representing a graph: adjacency
matrix and adjacency list. You can insert the given graph using either of these options. Using an
adjacency list is easy for smaller graph representation.
Consider the following two graphs to test your algorithms:
Sample Output of Graph a:
BFS:
Traversal path: SABBDCDCDG
Exact path: SADG
DFS:
Traversal path: SABCDG
Exact path: SABCDG
IDS:
Traversal path: S SAB SABDBCD SABCDDG
Exact path: SADG
UCS:
Traversal path: SBABCDG
Exact path: SBDG
University of Windsor Winter 2021
Part I: (Points 2)
Implement the algorithms in the first part on a randomly generated space graph. To generate a random
space graph, you can send two parameters to decide the number of edges and number of nodes. Then
you can set the start and goal state.
For your Knowledge:
How will you solve the famous Toy Problem, missionary-cannibal problem using BFS and DFS
algorithms? Understand the states clearly to represent in a table or a diagram.
Practice the implement to solve the missionary-cannibal problem using BFS and DFS.