CS5804-hw1-Solution
pdf
keyboard_arrow_up
School
Virginia Tech *
*We aren’t endorsed by this school
Course
2114
Subject
Mathematics
Date
Apr 3, 2024
Type
Pages
10
Uploaded by AgentFreedom13630
Homework 1 Solution
Q1 (10 pts):
How many nodes are in the complete search tree for the given state space graph?
The start state is S. You may find it helpful to draw out the search tree on a piece of paper.
A: 10
The complete search tree would look like this.
Q2 (10 pts): Consider a depth-first graph search on the graph below, where S is the start and G
is the goal state. Assume that ties are broken alphabetically (so a partial plan S->X->A would be
expanded before S->X->B and S->A->Z would be expanded before S->B->A). You may find it
helpful to execute the search on scratch paper.
Please enter the final path returned by depth-first graph search in the box below. Your answer
should be a string with S as your first character and G as your last character. Don't include
arrows or spaces in your submission. For example, if you believe the path is S->X->G, please
enter SXG in the box. (Please write your answer in uppercase letters, e.g., SXG, rather than
sxg.)
A: SAG
Explanation:
Step 1: Expand S
Fringe: S-A, S-B, S-C, S-E
Closed Set: S
Step 2: Expand S-A
Fringe: S-A-G, S-B, S-C, S-E
Closed Set: S, A
Step 3: Expand S-A-G, finding the goal
Q3 (10 pts): Consider a breadth-first graph search on the graph below, where S is the start and
G is the goal state. Assume that ties are broken alphabetically (so a partial plan S->X->A would
be expanded before S->X->B and S->A->Z would be expanded before S->B->A). You may find
it helpful to execute the search on scratch paper.
Please enter the final path returned by the breadth-first graph search in the box below. Your
answer should be a string with S as your first character and G as your last character. Don't
include arrows or spaces in your submission. For example, if you believe the path is S->X->G,
please enter SXG in the box. (Please write your answer in uppercase letters, e.g., SXG.)
A: SCG
Step 1: Expand S
Fringe: S-A, S-B, S-C
Closed Set: S
Step 2: Expand S-A
Fringe: S-A-B, S-A-C, S-B, S-C
Closed Set: S, A
Step 3: Expand S-A-B
Fringe: S-A-C, S-B, S-C
Closed Set: S, A, B
Step 4: Expand S-C
Fringe: S-A-C, S-B, S-C-G
Closed Set, S, A, B, C
Step 5: Expand S-C-G, finding the goal
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help
Q4.1 (5 pts): Consider A* graph search on the graph below. Arcs are labeled with action costs
and states are labeled with heuristic values. Assume that ties are broken alphabetically (so a
partial plan S->X->A would be expanded before S->X->B and S->A->Z would be expanded
before S->B->A.
In what order are states expanded by A* graph search? You may find it helpful to execute the
search on scratch paper.
A: Start, A, B, Goal
B: Start, A, D, Goal
C: Start, A, B, C, D, Goal
D: Start, B, A, D, B, C, Goal
E: Start, A, C, Goal
F: Start, B, A, D, C, Goal
Q4.2 (5 pts): (Following the previous question) What path does A* graph search return?
A: Start-A-B-D-Goal
B: Start-B-Goal
C: Start-A-D-Goal
D: Start-A-B-Goal
E: Start-A-C-Goal
Explanation:
Step 1: Expand S
Fringe: (S-A, 5), (S-B, 4)
Closed Set: S
Step 2: Expand S-B
Fringe: (S-A, 5), (S-B-D, 8), (S-B-G, 11)
Closed Set: S, B
Step 3: Expand S-A
Fringe: (S-B-D, 8), (S-B-G, 11), (S-A-D, 5), (S-A-C, 6)
Closed Set: S, B, A
Step 4: Expand S-A-D
Fringe: (S-B-D, 8), (S-B-G, 11), (S-A-C, 6), (S-A-D-G, 7)
Closed Set: S, B, A, D
Step 5: Expand S-A-C
Fringe: (S-B-D, 8), (S-B-G, 11), (S-A-D-G, 7), (S-A-C-G, 13)
Closed Set: S, B, A, D, C
Step 6: Expand S-A-D-G, finding the goal
Closed Set: S, B, A, D, C, G
Return: Start-A-D-Goal
Q5.1 (5 pts):
Uniform-Cost Graph Search:
Consider the graph below. Arcs are labeled with
their weights. Assume that ties are broken alphabetically (so a partial plan S->X->A would be
expanded before S->X->B and S->A->Z would be expanded before S->B->A.
In what order are states expanded by Uniform Cost Search? You may find it helpful to execute
the search on scratch paper.
A: Start, A, D, Goal
B: Start, A, C, Goal
C: Start, B, A, D, C, Goal
D: Start, A, B, Goal
E: Start, A, B, C, D, Goal
F: Start, B, A, D, B, C, Goal
Q5.2 (5 pts): (Following the previous question) What path does uniform cost search return?
A: Start-B-Goal
B: Start-A-B-Goal
C: Start-A-B-D-Goal
D: Start-A-D-Goal
E: Start-A-C-Goal
Explanation:
Step 1: Expand S
Fringe: (S-A, 2), (S-B, 1)
Closed Set: S
Step 2: Expand S-B
Fringe: (S-A, 2), (S-B-D, 6), (S-B-G, 11)
Closed Set: S, B
Step 3: Expand S-A
Fringe: (S-B-D, 6), (S-B-G, 11), (S-A-D, 3), (S-A-C, 5)
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help
Closed Set: S, B, A
Step 4: Expand S-A-D
Fringe: (S-B-D, 6), (S-B-G, 11), (S-A-C, 5), (S-A-D-G, 7)
Closed Set: S, B, A, D
Step 5: Expand S-A-C
Fringe: (S-B-D, 6), (S-B-G, 11), (S-A-D-G, 7), (S-A-C-G, 12)
Closed Set: S, B, A, D, C
Step 6: Pop S-B-D from our fringe, but do not expand it, because D is in our closed set
Fringe: (S-B-G, 11), (S-A-D-G, 7), (S-A-C-G, 12)
Closed Set: S, B, A, D, C
Step 7: Expand S-A-D-G, finding the goal
Closed Set: S, B, A, D, C, G
Return: Start-A-D-Goal
Q6.1 (10 pts):
For each of the above graph search strategies, mark the listed paths it could return. Note that
for some search strategies, the specific path returned might depend on tie-breaking behavior. In
any such cases, make sure to mark all paths that could be returned under some tie-breaking
scheme. For example, DFS can return any path A-B-D-G and A-C-D-G and A-B-C-D-F-G.
a. Breadth first search,
b. Uniform cost search,
c. A* search with heuristic h1,
d. A* search with heuristic h2
Based on your marks, select the BEST and Complete answer above.
A: a, c, d return the same possible paths
B: a, b return the same possible paths
C: a, b, c return the same possible paths
D: c, d return the same possible paths
E: b, c, d return the same possible paths
F: b, c return the same possible paths
Q6.2 (10 pts):
A: 0 <= h3(B) <= 10
B: 0 <= h3(B) <= 12
C: 1.5 <= h3(B) <= 9
D: 1.5 <= h3(B) <= 10
E: 1.5 <= h3(B) <= 12
F: 0 <= h3(B) <= 9
Q6.3 (10 pts): (Following the previous question)
A: 7 <= h3(B) <= 10
B: 8 <= h3(B) <= 10
C: 8 <= h3(B) <= 11
D: 7 <= h3(B) <= 11
E: 7 <= h3(B) <= 12
F: 9 <= h3(B) <= 10
G: 8 <= h3(B) <= 12
H: 9 <= h3(B) <= 12
I: 9 <= h3(B) <= 11
Q7.1 (10 pts): Consider a state space where the start state is number 1, and the successor
function for state n returns two states, numbers 2n and 2n + 1. A state space for states 1 to 15
is shown below:
Your preview ends here
Eager to read complete document? Join bartleby learn and gain access to the full version
- Access to all documents
- Unlimited textbook solutions
- 24/7 expert homework help
Suppose the goal state is 11. List the order in which nodes will be visited. Please use a comma
to separate nodes, e.g. 1,2,3.
Breadth-first search:
A: 1,2,3,4,5,6,7,8,9,10,11
B: 1,2,4,8,9,5,10,11
C: 8,4,9,2,10,5,11
D: 1,2,5,10,11
E: 1,2,5,11
Q7.2 (10 pts): Following the previous question, Depth-limited search with limit 2:
A: 1,2,4,5,3,6,7
B: 1,2,3,4,5,6,7
C: 1,2,3,4,5,6,7,8,9,10,11
D: 1
E: 1,2,4,8,9,5,10,11
F: 8,4,9,2,10,5,11