PaperHomework_AI_2012011722
Homework of AI
YingChen Shi DEP20 2012011722
1. Which of the following are true and which are false? Explain your answers.
a. Depth-first search always expands at least as many nodes as A ?search with an admissible heuristic.
False. Depth-first search may be lucky enough to prevent back-tracking and find the nodes for the first round of depth search. But A* must go though at least all the surrounding nodes of the starting place.
b. h(n) = 0 is an admissible heuristic for the 8-puzzle.
True. The requirement for h(n) is that it is smaller than the real cost from vertex n to the goal. “h(n)=0” will never miss that requirement.
c. A ? is of no use in robotics because percepts, states, and actions are continuous.
False. All the percepts,actions and states change in robotics are base on pattern search. We do the search work first and then convert the results to continuous actions, etc. d. Breadth-first search is complete even if zero step costs are allowed.
True. BFS can always be done if there is a goal, although it is not always the optimal one. And that is what complete means.
e. Assume that a rook can move on a chessboard any number of squares in a straight line, vertically or horizontally, but cannot jump over other pieces. Manhattan distance is an admissible heuristic for the problem of moving the rook from square A to square B in the smallest number of moves.
False. Manhattan distance is calculated at the default of that we can only move one squares at one time. So in this problem the Manhattan distance will be larger than the smallest number of moves.
2. A basic wooden railway set contains the pieces shown in the following figure. The task is to connect these pieces into a railway that has no overlapping tracks and no loose ends where a train could run off onto the floor.
a. Suppose that the pieces fit together exactly with no slack. Give a precise formulation of the task as a search problem.
The formulation is as follows:
Well, ① contains 7 of the straight pieces. ③ and ④ both contains 6 curves and 2 fork
① ②
③ ④ ⑤
pieces(a couple). ②contains 5 of the straight pieces. And ⑤contains 4 of the curves pieces.
b. Identify a suitable uninformed search algorithm for this task and explain your choice.
DFS algorithm. Because it has less capacity complexity and the same time complexity than other uninformed search algorithm as there are too many cases in this problem. Moreover, we can find that the depth of this searching problem is 32 and every node has 31 branches (at most), but the solution is at the bottom of the tree. So I choose DFS but not IDS.
c. Explain why removing any one of the “fork”pieces makes the problem unsolvable.
“fork” pieces can only be used in couples to form a conn ected graph, because it has three branches. So the number of it must be even.
d. Give an upper bound on the total size of the state space defined by your formulation.
State space = B m = 3132 .Where B is branching factor, m is the tree depth.
3. Prove each of the following statements, or give a counterexample:
a. Breadth-first search is a special case of uniform-cost search.
BFS is a kind of enumeration search algorithm as it iterates all child vertex for the next step first. So it is uninformed.
b. Depth-first search is a special case of best-first tree search.
No, it’s an uninformed search as it has no heuristic function to find the best choice.
c. Uniform-cost search is a special case of A?search.
No. A* search is a case of informed search, but Uniform-cost search is a case of uninformed search.
4. Trace the operation of A search applied to the problem of getting ?to Bucharest from Lugoj using the straight-line distance heuristic. That is, show the sequence of nodes that the algorithm will consider and the f , g, and h score for each node.
The result is as listed (“___” means that the node is chosen to go on the search and cannot be considered anymore):
Sequence NO. city g h f 1a Mehardia 70 241 311
1b Timisoara 111 329 440
2a Dobreta 145 242 387
3a Craiova 265 160 425
4a Rimnicu Vilcea 411 193 604
4b Pitesti 403 98 501
5a Bucharest 504 0 504
So the final way we find is Lugoj--- Mehardia--- Dobreta--- Craiova--- Pitesti--- Bucharest
5. The heuristic path algorithm (Pohl, 1977) is a best-first search in which the evaluation function is f (n) = (2 ?w)g(n) + wh(n). For what values of w is this complete? For what values is it optimal, assuming that h is admissible? What kind of search does this perform for w = 0, w = 1, and w = 2?
0 < w < 2 for its complete.
0 < w < 1 for its optimization.
When w=0, it’s uninformed best-first search; when w=1, it’s A* search; when w=2, it’s
greedy best-first search.
6. Consider the unbounded version of the regular 2D grid shown in the following figure. The start state is at the origin, (0,0), and the goal state is at (x , y ).
a. What is the branching factor b in this state space? 4
b. How many distinct states are there at depth k (for k > 0)? 4k
c. What is the maximum number of nodes expanded by breadth-first tree search? 4d , where d is the length of the shortest path to the goal.
d. What is the maximum number of nodes expanded by breadth-first graph search? d 2, where d is the length of the shortest path to the goal.
e. Is h = |u ? x | + |v ? y | an admissible heuristic for a state at (u , v )? Explain. True. This is the path length.
f. How many nodes are expanded by A ? graph search using h ? x * y
g. Does h remain admissible if some links are removed? Yes.
h. Does h remain admissible if some links are added between nonadjacent states? No. The actual path may become shorter than h.
7. 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. Calculate the size of the state space as a function of n .
)(...)1
(22
22n n n n A x n n -??-?== b. Calculate the branching factor as a function of n.
n k 5=
c. Suppose that vehicle i is at (xi, yi); write a nontrivial admissible heuristic hi for the number of moves it will require to get to its goal location (n ? i + 1, n), assuming no other vehicles are on the gri
d.
|||1|i i i y n x i n h -+-+-=
d. Which of the following heuristics are admissible for the problem of moving all n vehicles to their destinations? Explain.
}......,,max{21n h h h and }......,,min{21n h h h are both OK.
Because we need h(n) to be smaller than the real smallest cost, and these two meet the requirement.
8. Invent a heuristic function for the 8-puzzle that sometimes overestimates, and show how it can lead to a suboptimal solution on a particular problem. (You can use a computer to help if you want.) Prove that if h never overestimates by more than c, A ? using h returns a solution whose cost exceeds that of the optimal solution by no more than c.
If the state is a goal, h(n) returns 0, otherwise returns a random number between 1 and N. N is big enough to ensure that it will sometimes overestimate.
Now we start at ??????????85762431, the whole procedure is: ????
?
?????8576243113130=+=f ??????????85762431761=+=f ?????
?????85762314430=+=f ????
??????85762314412=+=f ????
?
?????8562731415132=+=f ??????????87652314853=+=f ??????????857623141293=+=f ??????????85761234
13103=+=f ????
?
?????85761234624=+=f ????
?
?????857612341064=+=f ?????
?????8576134216115=+=f
??
??
??????85761342826=+=f
??????????857641321257=+=f ??????????8765134219127=+=f ????
?
?????857613421587=+=f
??????????857641321468=+=f ?????
?????857641321028=+=f ????
?
?????857643211569=+=f ??????????8576432114410=+=f ??
????????8564732119910=+=f
??????????8765432113211=+=f ?????
?????8576432120911=+=f ????
?
?????8765432112=f As you can see, there are totally 12 steps. But the minimize is 4 steps.
To prove that theory, we suppose as the new heuristic function. If there are any nodes in this n*n squares that is sub-optimal for more than c, we have .And of course, it will not be visited until an optimal node is expanded.
9. Prove that if a heuristic is consistent, it must be admissible. Construct an admissible heuristic that is not consistent.
If h is the consistent heuristic function, ),(P N c is the cost of reaching node P from N. And P is the present node. So we have()('n h is the cost of the shortest path from n to the goal):
)()(),()(),()(''N h P h P N c P h P N c N h =+≤+≤
Therefore, )(N h is admissible.
Construct an admissible heuristic that is not consistent(h is an admissible function):
)}(),(),(min{)(0N h P N c P h P h -=
10. We can define a relaxation of the 8-puzzle in which a tile can move from square A to
c n h n h +=)()('c C n f +>'
)(
square B if B is blank. The exact solution of this problem defines Gaschnig ’s heuristic (Gaschnig, 1979). Explain why Gaschnig ’s heuristic is at least as accurate as h1 (misplaced tiles), and show cases where it is more accurate than both h1 and h2 (Manhattan distance). Explain how to calculate Gaschnig ’s heuristic efficiently.
When the blank is at its final position but the tiles is still misplaced, we should have two moves to make one tile in place. So the Gaschnig path is larger than the number of misplaced tiles and is more close to the real shortest path.
This is an example when Gaschnig ’s heuristic is more accurate than both h1 and h2: Target: Original:
??
????????85764321
??
??
?
?????65784321
Shortest path: 10
Gaschnig ’s heuristic: 3 Misplaced tiles: 2 Manhattan distance: 2
Pseudocode to calculate Gaschnig ’s heuristic:
Path=0;
while not in final state:
if blank in its final position: swap blank with a mismatch; Path++; else
Swap blank with tile in its position; Path++; return Path;