Spring ‘22 AI Homework 1: solutions
Assigned: Jan 24
Due: Jan 31, before class
Submit: doc or pdf via Brightspace (cannot be handwritten)
Copyright By PowCoder代写 加微信 powcoder
Search Algorithms
Path from Start to Goal for an undirected graph:
Edge weights are on the diagram, use the below h-function for part 3.
Questions:
● You can assume a visited-set that avoids revisiting nodes.
● For BFS and ID, choose the lower alphabetical first (so A before B, etc.)
1. [3 pts.] Show the order of nodes visited using Breadth First Search (BFS), and the
final path selected. Is this optimal? Why or why not?
2. [3 pts.] Show the order of nodes visited using Iterative Deepening (initial depth of
2, increasing depth by 1), and the final path selected. Is this optimal? Why or why
3. [4 pts.] Using the above h-function, show the order of nodes visited using A*, and
the final path selected. Is this optimal? Why or why not?
1. BFS, you don’t need a visited list, no penalty if you didn’t use one, I use a per-path one so S->K->L and S->L->K are both expanded, but S->L->S is not
Level=1 Start -> K -> L
Start -> K -> L
-> N -> L -> K -> M -> O
Start -> L -> K -> N
-> K -> L -> M -> O -> L -> M -> O
-> K -> N -> Goal # could exit here, or expand all of Level3 -> P
-> Q -> L -> O -> M
Solution of Start-> K -> N -> Goal found
Note: could exit as soon as solution found, or complete the expansion of the current level then exit with the “best” solution. Either is valid.
The solution would be optimal under unit-weight, or minimal edges, but is not optimal given the actual edge weights – there is a shorter weight path SLKNG.
This is because BFS does not offer any optimal guarantee regarding non-unit weights.
2. ID, using a per-path visited list only Depth=2
Start -> K -> L (backtrack) # depth=limited -> N (backtrack) # depth=limited
-> L -> K (backtrack) # depth=limited -> L -> M (backtrack) # depth=limited -> L -> O (backtrack) # depth=limited
No solution found, increase to Depth=3
Start -> K -> L -> M (backtrack) # depth=limited -> O (backtrack) # depth=limited
-> N -> Goal (solution)
Solution: Start->K->N->Goal
The solution would be optimal under unit-weight, or minimal edges, but is not optimal
given the actual edge weights – there is a shorter weight path SLKNG.
This is because ID does not offer any optimal guarantee regarding non-unit weights.
3. A* using (g+h) to select smallest for expansion
From Start:
{SK (14+9), SL (8+24)} => expand SK
{SKL(17+24), SKN(23+2), SL(8+24)} => expand SKN
{SKL(17+24), SKNG(28+0), SKNP(27+5), SKNQ(34+12), SL(8+24)} => expand SKNG
Solution: SKNG length=28
This is not an optimal solution. Unfortunately our h function was inadmissible, in that it
overestimated the cost from L, such that we never expanded SL.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com