人工智能练习题.doc

Part I SEARCH1 SearchYoure a taxi driver. Your taxi can hold 4 passengers. Passengers pay a flat fee for a ride to the airport, so goal is to pick up 4 passengers and take them to the airport in the smallest number of miles. Your world can be modeled as a graph of locations with distances between them. Some, but not all, of the locations have passengers that you can pick up.a. Describe the state space of this search problem.b. What would be a good cost function for this search problem?c. Now, consider a case where passengers have to pay according to how far away they are from the airport when theyre picked up (note: they dont pay according to how long a ride they take in your taxi, but according to the length of the shortest path from their pickup-point to the airport). Describe the state space of this search problem.d. What would be a good cost function for this version of the problem? You still have a desire to save gas.e. Is uniform cost search guaranteed to find the optimal solution in either or both versions of the problem? Why or why not?a. Your current location and number of passengers in the car.b. Distance traveled so far.c. Current location, the number of passengers in the car, and the fares of the passengers you have in the car.d. Some constant c1 times the distance traveled so far minus some other constant c2 times the fares of the passengers weve picked up so far.e. UCS will work in the first case, because there are no negative costs, but its not guaranteed to find the shortest path in the second version of the problem.2 SearchConsider the following graph, in which A is the start node and F is the goal node. Assume that nodes are visited at most once.1. In what order does uniform-cost search visit the nodes?2. Let the heuristic function h(n) be the minimum number of arcs between node n and the goal node. Is this an admissible heuristic? Why or Why not?3. In what order does A* search visit the nodes? What are their estimated values when they are visited?1. A B E C F2. Yes, it is admissible because it is a conservative estimate of the distance.3. A(2) B(4) E(4) F(5)3 Search Below is a graph to be searched (starting at S and ending at G). Link/edge costs are shown as well as heuristic estimates at the states. You may not need all the information for every search.1.Draw the complete search tree for this graph. Label each node in the tree with the cost of the path to that node and the heuristic cost at that node. When you need to refer to a node, use the name of the corresponding state and the length of the path to that node.2. For each of the searches below, just give a list of node names (state name, length of path) drawn from the tree above. Break ties using alphabetical order. 1. Perform a depth-first search using a visited list. Assume children of a state are ordered in alphabetical order. Show the sequence of nodes that are expanded by the search. S0, A3, C5, G5 note that B6 is not expanded because B is on visited list (placed there when S0 was expanded).2. Perform a best-first (greedy search) without a visited or expanded list. Show the sequence of nodes that are expanded by the search. S0 (h=5), A3(h=2), G5(h=0)3. Perform a Uniform Cost Search without a visited or expanded list. Show the sequence of nodes that are expanded by the search. S0, B1, C2, A3, A4, C5, G5 note that nodes are ordered first by cost then alphabetically when tied for cost.4. Perform an A* search (no pathmax) without an expanded list. Show the sequence of nodes that are expanded by the search. S0(0+5), B1(1+3), C2(2+2), A3(3+2), G5(5+0)5. Is the heuristic in this example 1. admissible? Yes 2. consistent? No Justify your answer, briefly.All the h values are less than or equal to actual path cost to the goal and so the heuristic is admissible. The heuristic drops from 5 at S to 3 at B while the path cost between S and B is only 1, and so the heuristic is not consistent.4 Search(1234987651011121314List the order in which nodes are visited in the tree below for each of the following three search strategies (choosing leftmost branches first in all cases):a).Breadth-first search(3 Points) b).Depth-first search(3 Points)5 IDA*Write out the main idea of Iterative Deepening A*.6 Missionaries and cannibalsThe missionaries(传教士) and cannibals(食人者) problem is usually stated as follows. Three missionaries and three cannibals are on left side of a river, along with a boat that can hold one or two people. Find a way to get everyone to the right side, without ever leaving a group of missionaries in one place outnumbered by the cannibals in that place.We can search in the state spaces of this problem to solve it. So we have to define the state and the operators firstly. The states and operators are defined as below:State: A state consists of an ordered sequence of three numbers representing the number of missionaries, cannibals, and boats on the left side of the river. Thus, the start state is (3,3,1) and the goal state is (0,0,0).Operators: We define pij as boating i missionaries and j cannibals from left side of the river to the right side and qij as boating i missionaries and j cannibals from right side of the river to the left side.Draw the state-space graph of this problem. You do not need to draw any states; just complete the graph that I have given. You may mark the operator pij only beside every edge.(Because operator qij is the same as pij)331220321311111011000p02p01p11p027 2L-WaterThere are two bottles named A and B to store water. The volume of A is 4L and B is 3L, either with no scales on it. Our aim is to get 2L water exactly in bottle A through some operations. At each step, we can perform one of the three operations: (1) filling up one bottle (2) empty one bottle; (3) dump water from one bottle to another. How can you get 2L exactly in bottle A? Searching in state space of this puzzle will lead to a solution and the best-first search can improve search efficiency. So we have to define the state and the estimation function. The states and estimation function are defined as below:State: A state, (x, y), consists of an ordered sequence of two variables representing the volume of water in bottle A and bottle B. Thus, the start state is (0, 0) and the goal state is (2,0).We define the estimation function as f(n) = g(n) + h(n). g(n) = number of operations already performed.h(n) = 2 If 0x4 and 0y3 = 4 if 0x4 or 0y3 =10 if x=0 and y=0 or x=4 and y=3 =8 if x=0 and y=3 or x=4 and y=0Please draw the search tree, and for each node n give the value of f(n).8 Bottle worldImagine a world which consists of four beer bottles A, B, C, and D. They can be arranged in any order from left to right, except that bottle A can never be further to the right than bottle D. For example, ABCD, CBAD, and CADB are possible states of our world, whereas DCBA, CDAB, or BCDA can never occur. The world can be manipulated by the schema swap(x, y), which swaps the bottles in positions x and y. For example, swap(1, 2) turns state BCAD into CBAD. However, swap(1,2), swap(2,3), and swap(2,4) are the only three available operators. a) Draw the state-space graph of this world. You do not need to draw any bottles; just use four-letter sequences to describe states.b) Assume that your world is in the state ADBC, and the goal state is CBAD. Now we define a estimation function f(n) = g(n) + h(n), f(n) = number of operations already performed + (number of bottles in incorrect position)/2. Please write down the resulting search tree, indicate the order in which nodes were created, and for each node n give the value of f(n). 9 General graph-searching algorithm Please present a general graph-searching algorithm that permits any kind of ordering the user might prefer-heuristic or uninformed. Then answer the following questions:1)What happens if we simply append new nodes at the beginning of OPEN?2)What happens if we simply append new nodes to the end of OPEN?PART II Game Search1 PracticeThe Isola World Championships for Java Programs Isola is a board game that is extremely simple yet in my humble opinion quite interesting. Basically, like in every good game or movie, there are two opponents. These opponents live on a 7x7 array of squares, and they move alternately. One move consists of moving to a neighboring square (vertically, horizontally, or diagonally) that is not occupied by the opponent and removing one of the squares, of course one with no-one standing on it. And finally, whoever is the first to be unable to move loses the game. Your task, of course, is to write an algorithm in Java that plays Isola at grandmaster level. You are required to implement a minimax algorithm and alpha-beta pruning. The greatest challenge for programming the algorithm should be the huge number of possible moves (up to 320, if I am not mistaken), because each move is a combination of jumping to a neighboring square and removing any of the unoccupied squares. Maybe it would be a good idea to implement some mechanism that reduces the number of moves that are being considered. For example, in many cases it does not matter whether you remove a square that is far away from both players, or you remove one of its neighboring squares. You should by all means try to restrict the branching of the search tree, otherwise your algorithm will not be able to look far ahead. However, with regard to this assignment and its deadline, you just have to implement the player, including a reasonable static evaluation function, minimax, and alpha-beta. If you do that correctly, you will get all the points for Question 1. Please also supply some text explaining how your evaluation function works, as well as any extra mechanisms that you implemented. After you submitted your homework, you can still work on your algorithm and improve it until the tournament (there will be another deadline). 2 Alpha-Beta PruningThe tree below indicates the complete Minimax tree for a particular problem (first move by MAX, then MIN, and then MAX again). The number at each leaf p indicates the value of the static evaluation function e(p) if it were computed at that leaf. a) To check which branch will be pruned and mark a cross(X) on these nodes.b) Which next move (the left or right one) should MAX make?MAXMINMINMAX-16-244-3022-30-235-21-30689-39-27-54-912-3173-568125-113MINMAXMIN maxminmaxmin 4 5 3 1 2 4 3 6 7 5 2 5 2 5 8 2 3 1 5 4 4 6 7 1 maxminmaxmin3451236786782345436782343 Game SearchConsider the game tree shown below. Assume the top node is a max node. The labels on the arcs are the moves. The numbers in the bottom layer are the values of the different outcomes of the game to the max player.1. What is the value of the game to the max player? 2 2. What first move should the max player make? L 3. Assuming the max player makes that move, what is the best next move for the min player, assuming that this is the entire game tree? R 4 Alpha-Beta PruningIn the following game tree, are there any alpha-beta cutoffs? Consider the nodes from left to right, which nodes are cutoff? Circle the nodes that are not examined and label them with L. None . Consider the nodes from right to left, which nodes are cutoff? Circle the nodes that are not examined and label them with R. The leftmost 8 node . PART III Logic1.Convert the following English sentences to first-order logic: 1. Everyone has one mother. You may use the predicate Mother(x,y) and Equal(x,y).xy Mother(y,x) (z Mother(z,x) (y = z)2. An aunt is a parents sister. You may use the predicate Aunt(x,y), Sister(x,y) and Parent(x,y). xyz. Parent(x,y) Sister(z,x) Aunt(z,y)2.Convert this sentence to clause form: xy. P(x,y) Q(x) (z R(z) (w Q(w) Remove : xy. (P(x,y) Q(x) (z R(z) (w Q(w) Move : xy. P(x,y) Q(x) (z R(z) (w Q(w) Skolemize: xy. P(x,y) Q(x) R(sk1(x,y) Q(sk2(x,y) Drop : P(x,y) Q(x) R(sk1(x,y) Q(sk2(x,y) CNF: P(x,y) Q(x) R(sk1(x,y) P(x,y) Q(x) Q(sk2(x,y)3.Given the following clauses: 1. Hasjob(p, job(p) 2. Hasjob(p, k) Equal(job(p), k) 3. Hasjob(George, Fireman) 4. Equal(Fireman, Teacher) 5. Equal(x,y) Equal(y, z) Equal(x, z) 6. Equal(x,y) Equal(y,x) Prove by resolution refutation that: Hasjob(George, Teacher) Hint: think about the strategy for the proof before you start doing resolutions. How would you prove the result by hand? Step Parent Parent Unifier 7 Neg Goal Hasjob(George, Teacher) - 8 2 7 Equal(job(George), Teacher) p=George k=Teacher 9 2 3 Equal(job(George), Fireman) p=George k=Fireman 10 9 6 Equal(Fireman, job(George) x=job(George) y=Fireman 11 5 10 Equal(job(George),z) Equal(Fireman, z) x=Fireman y=job(George) 12 8 11 Equal(Fireman,Teacher) z=Teacher 13 4 12 Contradiction 4. Write the following sentences in first-order logic, using S(x) for slow, S(x,y) to mean that x is slower than y, H(x) for horse, B(x) for brown, and W(x,r) for horse x winning race r.1. All brown horses are slow.2. All slow horses are brown.3. All slow things are brown horses.4. Some slow horses are brown.5. The slowest horse is brown.6. There is a winner in every race.1. x.B(x) H(x) S(x)2. x.S(x) H(x) B(x)3. x.S(x) B(x) H(x)4. x.S(x) H(x) B(x)5. x.H(x) B(x) y.(x y H(x) Slower(x, y)6. r.R(r) x.W(x, r)5 Clausal FormGiven the following sentence in first-order logic, convert it to clausal form:r.o(r) x.w(x)o(r) w(f(r)6 Clausal Normal FormConvert the following sentence to CNF (AB) (C D)7 UnificationFor each pair of literals below, specify a most general unifier, or indicatethat they are not unifiable.a. r(f(x), y) and r(z, g(w)b. r(f(x), x) and r(y, g(y)c. r(a,C, a) and r(f(x), x, y)a. z/f(x), y/g(w)b. not unifiablec. a/f(x), x/C, y/f(x)8 Clausal formConvert each sentence below to clausal form.a. y. x.r(x, y) s(x, y)b. y.( x.r(x, y) p(y)c. y. x.(r(x, y) p(x)a. r(f(y), y) s(f(y), y)b. r(x, y) p(y)c. r(f(y), y) p(f(y) 9 FOL SemanticsConsider a world with objects A, B, and C. Well look at a logical langugewith constant symbols X, Y , and Z, function symbols f and g, and predicatesymbols p, q, and r. Consider the following interpretation: I(X) = A, I(Y ) = A, I(Z) = B I(f) = , , I(p) = A,B I(q) = C I(r) = , , For each of the following sentences, say whether it is true or false in the giveninterpretation I:a. q(f(Z)b. r(X, Y )c. w.f (w) = Yd. w.r(f(w),w)e. u, v.r(u, v) (w.r(u,w) v = w)f. u, v.r(u, v) (w.r(w, v) u = w)a. Tb. Fc. Fd. Te. Ff. T10 Interpretationa. I(p) = A I(q) = C I(r) = b. I(p) = B,C I(r) = ,c. I(p) = A I(r) = , ,11.Propositional calculus and resolution refutation Is the following argument valid or not? Use resolution or resolution refutation to find out. Proceed in four steps: a)Extract the propositions from the argument and name them with single letters.(4 Points) b)Describe the hypotheses and the conclusion in propositional calculus. (3 Points)c)Convert these expressions into conjunctive normal form (CNF) suitable for resolution refutation (3 Points)d)List the steps of the resolution refutation and state the result, that is, whether the argument is valid or not. (5 Points)Anne goes to the library on Saturday or on Sunday. John also goes to the library on Saturday or Sunday. Therefore, both Anne and John will be at the library on Saturday, or both of them will be at the library on Sunday.Frank and Sarah take the AI course at XAUT. Sarah and George take the Discrete Math course at XAUT. Whoever takes the AI course at XAUT ends up in a lunatic asylum(疯人院). Whoever takes the Discrete Math course at XAUT loses all their hair. Therefore, Sarah will lose all her hair and end up in a lunatic asylum.Jennifer is either watching a soccer game or a basketball game, or both. Whenever she watches a soccer game, she wears a Beckham t-shirt. Whenever she watches a basketball game, she wears a YaoMing scarf. Therefore, Jennifer is wearing a Beckham t-shirt and a YaoMing scarf.If we could travel backwards in time, we could visit ourselves in the past. If we could visit ourselves in the past, someone would have done so. If someone had visited him/herself in the past, the visited person would publicize that event. No such event has ever been publicized. Therefore, we cannot travel backwards in time. Whenever Carl drinks a bottle of whiskey, he gets terrible headaches. Whenever Carl drinks a bottle of rum, he believes he sees pink elephants. Whenever Carl drinks a bottle of water, he feels bored. He drinks one or more bottles, each of them containing whiskey, rum, or water. Carl does not believe he sees pink elephants, and he is not bored. Therefore, he