CS156 Homework Assignment 4 - (Uninformed Search Solved

The objective of this homework assignment is to understand and visualize how different uninformed search algorithms work. Specifically, we will implement and compare the performance of three different uninformed search algorithms:

1.      Depth First Search (DFS)

2.      Breadth First Search (BFS)

3.      Uniform Cost Search (UCS)

 

We will explore these algorithms in a gaming environment where the Spartan Sammy will try to collect medals in a maze in the shortest possible time.

These are the following files for this assignment:

1.      data_structures contains all the Class definitions for data structures to be used by the search algorithms

2.      graphics contains Visualization of the maze and solution for the Spartan's quest

3.      noway, questA, questB, questC, questD and SJSU are txt files containing the description of different mazes with walls, starting position of Sammy and the starting positions of the medals that will be collected by Sammy

4.      Sammy is the Spartan (mascot).

5.      Spartanquest has the Main program that guides Sammy the Spartan on a quest within a given maze. It is invoked using: spartanquest.py maze_file search_algoritm where

 

               

               The maze_file is a text file such as SJSU.txt

               The search_algorithm in homework 4 is:

                               dfs: for depth first search (coded for you)

                               bfs: for breadth first search

                               ucs for uniform cost search

               Example:  spartanquest.py SJSU.txt dfs

6.      Uninformed_search_only_dfs has the implementation of the dfs algorithm and place holders for bfs and ucs algorithms that you have to write for this homework assignment.

 

Assignment:

A.      Tabulate the results showing 

(a) Path length, (b) Path cost, (c) Number of nodes expanded and (d) Processing time from all three searches dfs, bfs and ucs for the following scenarios:

a.      questA

b.      questB

c.       questC

d.      questD 

e.      SJSU

f.        Noway

 

Depth First Search
 
Quest A 
Quest B
Quest C
Quest D
SJSU
No Way
Path Length
99
992
70
256
202
0
Path Cost
252
2336
202
499
421
0
No. Nodes Expanded
207
1177
274
256
304
78
Processing Time (secs)
0.0059
0.0143
0.0034
0.0037
0.0036
0.0009
 

Breadth First Search
 
Quest A
Quest B
Quest C
Quest D
SJSU
No Way
Path Length
17
100
47
31
45
0
Path Cost
49
301
166
134
157
0
No. Nodes Expanded
97
393981
284
723
533
78
Processing Time (secs)
0.0012
23.5377
0.0034
0.0091
0.0060
0.0009
 

Uniform Cost Search
 
Quest A
Quest B
Quest C
Quest D
SJSU
No Way
Path Length
17
113
48
31
52
0
Path Cost
49
281
157
134
144
0
No. Nodes Expanded
85
398525
303
1251
553
78
Processing Time (secs)
0.0024
14.3876
0.0036
0.0191
0.0075
0.0010
 

B.      Which search algorithm performed the best? Why do you think so?

Overall, Breadth First Search performed the best compared to Depth-First Search and Uniform Cost Search. BFS consistently had the shortest path length, with UCS coming in close behind. Additionally, BFS had the shortest processing time. BFS was a laggard compared to UCS in terms of path cost. UCS consistently had the smallest path cost. 

 

C.      Did the performance of the algorithms vary with the type of the maze file? Why?

QuestB seemed to perform the worst among all three search algorithms; the goal state most likely was towards the end of the maze. Otherwise, the performance did not vary with the type of maze file(s). Slight discrepancies can be attributed to the size of the maze and the location of the goal state. 

 

Additional Quests (Extra Credit)

Depth First Search
 
Quest E 
Quest F
Quest G
Quest H
Quest J
 
Path Length
156
1233
1903
100
739
 
Path Cost
314
2431
3780
243
1407
 
No. Nodes Expanded
164
1322
2411
175
750
 
Processing Time (secs)
0.0025
0.0151
0.0275
0.0018
0.0089
 
 
 
 

Breadth First Search
 
Quest E 
Quest F
Quest G
Quest H
Quest J
 
Path Length
12
73
DNC
40
40
 
Path Cost
30
133
DNC
106
185
 
No. Nodes Expanded
188
106463
DNC
1422
4193
 
Processing Time (secs)
0.0021
3.9901
DNC
0.0161
0.0598
 
 

Uniform Cost Search
 
Quest E 
Quest F
Quest G
Quest H
Quest L
 
Path Length
12
73
98
40
47
 
Path Cost
30
133
2173
106
137
 
No. Nodes Expanded
310
47621
1941519
1154
3859
 
Processing Time (secs)
0.0048
1.0241
113.1236
0.0146
0.0604
 
 

DNC = Did Not Complete