Comp 3710程序语言代做、algorithms编程代写、代做Java，c++，Python程序

日期：2021-02-08 11:11

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.