人工智能练习题

Part I SEARCH1 SearchYou’re 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 they’re picked up (note: they don’t 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 we’ve picked up so far.e. UCS will work in the first case, because there are no negative costs, but it’s 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 SearchBelow 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 astate 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. Showthe 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 thesequence 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 example1. admissible? Yes2. consistent? NoJustify your answer, briefly.All the h values are less than or equal to actual path cost to the goal and sothe 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(List 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*10 11 12 13 14Write 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 anystates; 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)7 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 alread y performed.h’(n) = 2 If 0<x<4 and 0<y<3= 4 if 0<x<4 or 0<y<3=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 neveroccur. 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 est imation 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 algorithmPlease 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 ProgramsIsola 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?9 -2 7 -5 4 -9 12 -3 17 3 -5 6 8 1 2 5 -11 3m a x Array m i nm a xm i n4 5 3 1 2 4 3 6 7 5 2 5 2 5 8 2 3 1 5 4 4 6 7 1m a xm i nm a xm i n 3451236786782345436782343 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? 22. What first move should the max player make? L3. 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? R4 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).∀x∃y Mother(y,x) ∧(∀z Mother(z,x) ⇒(y = z))2. An aunt is a parent's 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) ∨ E qual(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?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(A∧B) ∨¬ (C ⇒D)7 UnificationFor each pair of literals below, specify a most general unifier, or indicate that 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. We’ll 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) = {<A,B>, <B,C>, <C,C>}• I(p) = {A,B}• I(q) = {C}• I(r) = {<B,A>, <C,B>, <C,C>}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) = {<A,B>}b. • I(p) = {B,C}• I(r) = {<A,B>,<B,B>,<C,C>}c. • I(p) = {A}• I(r) = {<A,A>, <B,A>,<C,A>}11.Propositional calculus and resolution refutationIs 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. (3Points)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 must have drunk a bottle of whiskey..12 What are the resolution result and MGU of the two sentences below?P(x)∨ Q(x,y)P(A)∨ R(B,x)Resolution Result:MGU:PART III Machine Evolution1. On our computer we can simulate evolutionary processes in two main aspects, please write out the two main aspects.2. On our computer we can simulate evolutionary processes in two main aspects, that is, generation of descendants and selective survival in these descendants. We can use the main idea of evolutionary to produce a curricula schedule. Present your design to implement such a curricula schedule.3. We have introduced a wall-following robot in the grid-space. We can use the idea of machine evolution to get a perfect wall-following robot rule. There are two trees represent two rules that the robot followed In the graph below. Please give me the descendant of the two tree use “crossover” and the probably result if mutation occurred.PART IV Computer VisionRobot Vision (15 Points)a) Median filteringUse a 3⨯3 filter and move it across the image, for each position, compute the median of the brightness values of the nine pixels and use the median as the new value for the center pixel.Averaging filteringUse a 3⨯3 filter and move it across the image, for each position, compute the average of the brightness values of the nine pixels and use the median as the new value for the center pixel.b) Edge detectionCompute the first derivate and second derivate in X-direction of the sample input . The filter is given below.Filter:First derivate:Second derivate:c).labelingBelow you see the 2D projection of an artificial 3D scene. Label each line according to its type (+,—, ↑ ).FilteringAssume that you have the following 7×7 pixel grayscale image A:a) Apply the following Sobel filter to A: -1 0 1 -2 0 2 -1 0 1Write down the resulting 5×5 image B of brightness values. If you prefer, you can write a small program to do all computations for Question 3.b) Now apply a 3×3 median filter to the original 7×7 image A. Also apply this filter to the pixels on the border of the image so that the resulting image C is not 5×5, but 7×7.Obviously, whenever you move the center of your filter onto the border, it will cover less than nine pixels. Then just take the median of thissmaller set of pixels as the resulting brightness value. Write down the brightness values of C.c) Now apply the same Sobel filter once again, but this time to the median-filtered image C. Write down the brightness values for the resulting 5×5 image D.d) Describe the difference between images B and D, that is, the effect of applying a median filter before the Sobel operation. Why is it a good idea to perform smoothing (either with a Gaussian or median filter) before edge detection?PART V InferenceB ayes’ NetsI am a professor trying to predict the performance of my class on an exam.After much thought, it is apparent that the students who do well are those that studied and do not have a headache when they take the exam. My vast medical knowledge leads me to believe that headaches can only be caused by being tired or by having the flu. Studying, the flu, and being tired are pairwise independent.a) We will model everything with Boolean variables. F indicates the presence of the flu, T indicates being tired, H - having a headache, S - studying, and E - passing the exam. Which of the following three networks bestmodels the relationships described?b) Why were the other two networks unsatisfactory models? Explain the deficiencies of each in terms of the conditional independence and dependence relationships they model. Which one of the remaining models represents an equivalent joint probability table as the best model, given that the description of the relationships was accurate?c) I found that tiredness and having the flu each have a small impact on the likelihood of studying (small because MIT students are so tough). Draw a network that expresses this connection. Compute its complexity and the complexity of the network you choose in part a). Give two reasons why the original network is superior, despite the small improvement this new network gives in predictive power.d) Leslie got the flu. Using model 3, compute the probability that she will fail the exam, in terms of values that are available in the conditional probabilitytables stored at each node.e) Michael passed the exam. Using model 3, compute the probability that he studied, in terms of values that are available in the conditional probability tables stored at each node.a) Model 3 best models the relationship.b) The first model makes flu, tiredness, and studying only conditionally independent (the first two conditioned on H and the third conditioned on E). The second model has the right relations, but many unnecessary dependencies. If the situation is accurately described in the problem, it will produce the same joint distribution as the third model because the dependencies will have no effect (for example, P(S|F, T) will be the same as P(S)).c) If we assume that we need to hold only one value, P(X = true) to represent the apriori probability of a single variable, then we need 2n entries for a conditional probability table for a node with n parents. So, the original network has a complexity of 1 + 1 + 1 + 4 + 4 = 11 and the new network has a complexity of 1+1+4+4+4 = 14. So, the size of the information necessary to store the network has increased by about 27%, but we have gained only a little more accuracy.d)e)阅读材料Note that trees are a subclass of directed graphs (even when not shown with arrows on the links). Trees don't have cycles and every node has a single parent (or is the root). Cycles are bad for searching, since, obviously, you don't want to go round and round getting nowhere.When asked to search a graph, we can construct an equivalent problem of searching a tree by doing two things:1. turning undirected links into two directed links;2. and, more importantly, making sure we never consider a path with a loop or, even better, by never visiting the same node twice.。