CS156 Homework #4-Uninformed Search Solved

Description

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:

1. 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:

1. questA
2. questB
3. questC
4. questD
5. SJSU
6. Noway

1. 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.

1. 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)

DNC = Did Not Complete