CS471 Assignment 1

ASSIGNMENT > CS471 Assignment 1

Related tags

UCLA Community School-Los Angeles CS 936 CS This assignment includes both written exercises and a programming component. Please follow the submission instructions carefully. The “written” portion of the assignment must be typeset with LATEX using the provided template. Part 1: Written Assignment (40 pts) 1. (26 pts) Alice wants to travel from her home to ...[Show More]

UCLA Community School-Los Angeles
CS 936 CS
This assignment includes both written exercises and a programming component. Please follow the submission instructions carefully. The “written” portion of the assignment must be typeset with LATEX using the provided template.

Part 1: Written Assignment (40 pts)

1. (26 pts) Alice wants to travel from her home to her favorite coffee shop Cyber Caf´e. Please help

Alice plan her route using the map in Fig. 1.

Alice's Home (A)

15

Byte Boutique (B)

12

6 Data Depot (D)

11

3

Echo Electronics (E)

10

2

Infinite Ink (I)

5

4

Java Junction (J)

5

7

Luna Lounge (L)

1

1

Cyber Café (C)

0

Fusion Fitness (F)

3 9

4

Harmony Hair Salon (H)

7

6

Galaxy Groceries (G)

6

3

Kaleidoscope Kids (K)

3

1

2

12

2

1

2

Figure 1: The map from Alice’s home to Cyber Caf´e. The number shown along an edge represents its cost of going from the starting node to the ending node of that edge. The number shown on the node represents Alice’s estimation (heuristic function) of how close the node is to her goal.

(a) (20 pts) Please use each of the following search algorithms to plan the route for Alice. For

each algorithm, write down (1) the order of the nodes expanded when executing the tree search version of the algorithm, and (2) the path that Alice actually will visit according to results from the search. As you plan the routes, if multiple options are available when expanding the next node, use alphabetical order for tie-breaking. For compactness, please use the abbreviation in the parenthesis for each node, e.g., Alice’s Home → A.

i. (4pts) Breadth-first search

ii. (4pts) Depth-first search

iii. (4pts) Uniform cost search

iv. (4pts) Greedy search with the provided heuristic values v. (4pts) A* search with the provided heuristic values