COMP30024 Artificial Intelligence
Week 4 Problem Sheet Solutions
• Tutors: These are not unique, complete (and definitely not optimally pedagogical) solutions. there are other ways of deriving these results and the way you prefer is to some extent an aesthetic judgement.
• Students: If you want to attain any benefit from the problems you should make a genuine attempt at them before you see the solutions.
Copyright By PowCoder代写 加微信 powcoder
Comments/corrections are as always greatly appreciated by the teaching team.
1. Heuristics [T] Recall in greedy best-first search (GBFS) we expand the node estimated to be
the closest to the goal state, i.e. the evaluation function f(σ) = h(σ).
(a) Suppose that we run a greedy best-first (graph) search algorithm with the heuristic function for node σ set to the negative of the path cost, h(σ) = −g(σ). What sort of search will the greedy search emulate? Hint: simulate this for a few iterations on the graph in Figure 2.
This emulates depth-first search, noting that for frontier F : argmin f (σ) = argmax g(σ)
(b) The heuristic path algorithm is a best-first search where the evaluation function contains a relative weighting factor w: f(σ) = (2 − w)g(σ) + wh(σ).
(i) Whatkindofsearchdoesthisperformforw=0,w=1,andw=2? Uniform-cost search, A∗, and GBFS, respectively.
(ii) For what values is it optimal, assuming that the heuristic h is admissible? Hint:
recall the condition for optimality of A∗.
Note that f(σ) = (2−w)g(σ)+ w h(σ), a scaled version of A∗ with heuristic 2−w
w h(σ). We require this to be admissible, hence require w ≤ 1 =⇒ w ≤ 1. 2−w 2−w
Non-negativity of the heuristic requires then 0 ≤ w ≤ 1. 1
Figure 1: Simplified road map of part of Romania. Adapted from Russell and Norvig (2010).
2. Generation vs. Expansion [T] Recall that state generation refers to the creation of the
data structure σ representing the state, whereas state expansion refers to the generation of
all children of the present node.
(a) Should informedsearch algorith ms apply thegoaltest upon state generation or state expansion, in order for the resulting search to be optimal? Does it make a difference
fromuninformedsearchalgorithms?
(b) Run UCS on the graph in Figure 1, performing the goal test on state expansion. Compare this against performing the goal test on state generation and compare the search paths found.
Goal test on generation returns the upper suboptimal path, goal test on expansion returns the lower optimal path.
3. Romanian Road Ramble [T] This year’s COMP30024 class excursion is to sunny Roma- nia. Chris has enlisted your help to find the optimal path between stops along the trip. Trace the operation of an A∗ search from Lugoj to Pitesti from the map of Romania in Figure 2. At each stage record the frontier and explored set. Represent each node as: σ = (State,ParentσP,g(σ),h(σ)), and use the following straight-line distance tabulated heuristic function:
Applying the goal test on generation does not guarantee optimality in general for in- formedsearchmethods(andUCS)-theremaybelower-costpathslivinginthefrontier whichwehavenotexplored.However,ifweapplythegoaltestonexpansion,allnodesin the frontierwillhaveequalorlargerpathcost.Foruninformedsea rchalgorithms (except UCS)thisdoesnotaffectoptimalitybutwillaffecttimecomplexity. Forexample,BFS time complexity becomes O(bd+1) for goal test upon expansion.
What is the final path found by A∗?
Using the straight-line Euclidean distance, we trace the following path:
1. •Frontier(F):{σ1}
– σ1 (root): (Lugoj, ∅, 0, ?)
• F post-expansion: {σ2,σ3}
– σ2: (Mehadia, σ1, 70, 280)
– σ3: (Timisoara, σ1, 111, 320)
• Explored set: K = {σ1}
• F post-expansion: {σ3,σ4}
– σ3: (Timisoara, σ1, 111, 320)
– σ4: (Drobeta, σ2, 145, 240)
• K ← K ∪ σ2
F: {σ2,σ3}
• F post-expansion: {σ3,σ5}
– σ3: (Timisoara, σ1, 111, 320)
– σ5: (Craiova, σ4, 265, 138)
• K ← K ∪ σ4
F: {σ3,σ4}
• F post-expansion: {σ3, σ6, σ7} ← note goal generation, but we continue on.
– σ3: (Timisoara, σ1, 111, 320) – σ6: (RV, σ5, 411, 97)
– σ7: (Pitesti, σ5, 403, 0)
• K ← K ∪ σ5
F: {σ3,σ5}
• Upon goal expansion (σ7), terminate. Note: Delay termination upon goal generation
F : {σ3, σ6, σ7}
– more optimal path to the goal may exist.
Path: Lugoj → Mehadia → Drobeta → Craiova → Pitseti, a short trip totalling ≈ 390 km.
4. Gridlock [T] n vehicles occupy squares (1, 1) through (n, 1) (i.e., the bottom row) of an n × n grid. The vehicles must be moved to the top row but in reverse order; so the vehicle i that starts in (i, 1) must end up in (n − i + 1, n). On each time step, every one of the n vehicles can move one square up, down, left, or right, or stay put; but if a vehicle stays put, one other adjacent vehicle (but not more than one) can hop over it. Two vehicles cannot occupy the same square.
(a) Find an expression for the size of the state space in terms of n. Multiple answers, e.g. n2!/(n2 −n)!.
(b) Find an expression for the branching factor in terms of n. 5n
(c) Give a (non-trivial) admissible heuristic hi for the number of moves it takes for a single
vehicle i starting in (xi, yi) to its goal state, (n − i + 1, n). Manhattan distance.
(d) Is i hi an admissible heuristic for this problem? How about max{h1, . . . , hn} or
min{h1,…,hn}?
The first will not be admissible in general as vehicles can move simultaneously. Note for the ’hop’ operation one vehicle must remain and another jump 2 steps, meaning the total distance travelled by all cars per move is bounded above by n. The total distance D moved by all vehicles from the start to goal state is bounded below by D ≥ nmin{h1,…,hn}. Hence the minimum number of steps required to attain D is min{h1,…,hn}.
References
Stuart Russell and . Artificial Intelligence: A Modern Approach, 3rd Ed. Prentice-Hall, 2010.
Figure 2: Simplified road map of bigger part of Romania. Adapted from Russell and Norvig (2010).
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com