課程名稱︰人工智慧 課程性質︰選修 課程教師：許永真 開課學院：電資學院 開課系所︰資工所、網媒所、知識管理學程 考試日期（年月日）︰2012.11.06 考試時限（分鐘）：120分鐘 試題 : Introduction to AI: Midterm ═══════════════════════════════════════ Please observe the standard testing rules with honor in this open-book exam. There are six parts for a total of 100 points, and you have exactly 120 minutes. You may not have time to finish all problems. We suggest that you browse through the problems first and start with the easiest problems for you. Don'tforget the bonus points! Write your answers in English (or Chinese), on the answer sheets. Mark each answer with the corresponding problem number clearly. Write your name and student ID on both the exam paper and answer sheets. ═══════════════════════════════════════ 1. (20 Points) Search Consider the search strategies introduced in Chapter 3. (a) (5 Points) Which uninformed search strategy compares most favorably with the others, and why? (b) (5 Points) We may extend uniform cost search to iterate over increasing limits on path cost. Is this new algorithm optimal? Justify your answer briefly. (c) (4 Points) Suppose that we modify the evaluation function for best-first search to f(n) = (2 - w)·g(n) + w·h(n). For what values of w is this complete? (d) (6 Points) What kind of search does this perform for w = 0, w = 1, and w = 2? Ans: (a) Any search strategy with reasonable explanation (5 Points). (b) Uniform cost search itself is a optimal algorithm (2 Points). The extention doesn't change its behavior (the order how nodes are expanded) (2 Points), so the new algorithm is still optimal (1 Points). (c) It is complete when 0 ≦ w ＜ 2 (4 Points). For w ≧ 2 or w ＜ 0, it is not complete. (d) Assume the h(n) is admissible. For w = 0, it is a uniform cost search (2 Points); for w = 1, it is a A* search (2 Points); for w = 2, it is a greedy best-first search (2 Points). 2. (15 Points) Local Search Consider the problem of solving the Sudoku puzzle. ╔═╤═╤═╤═╗ ║ │２│ │３║ ╟─┼─┼─┼─╢ ║ │ │４│２║ ╟─┼─┼─┼─╢ ║３│４│ │ ║ ╟─┼─┼─┼─╢ ║２│ │３│ ║ ╚═╧═╧═╧═╝ Figure 1: A simple math puzzle. (a) (6 Points) Please formulate the problem as a local search problem. (b) (4 Points) Please estimate the size of the search space (e.g. O(n^3)). (c) (5 Points) Describe how the search may be improved using simulated annealing. Ans: (a) Problem : A 2×2 Sudoku puzzle with some fixed grids with given values and some blank grids (unfixed) ‧ 1 point for each of the following, 2 points for reasonable formulation ◇ State: a valid value in each blank grid, where a valid value ∈ {1, 2, 3, 4} and the blank itself. ◇ Initial State: each blank (unfixed) grid is still blank. ◇ Action: Change an unfixed grid with a valid number. ◇ Goal: The sum of grids in each row and each column are all equal to 10. ◇ Cost: constant 1 for each action. (This one is optional) (b) The size of search space: ‧ 2 points for your explanation, ‧ 1 point for your parameter definition, ‧ 1 point for the estimation answer Define the amount of blank grids as n, we have O(5^n), where 5 means the size of the set of valid values. (c) Simulated annealing ‧ 3 points for reasonable improvement ‧ 3 points for the relation between the answer and simulated annealing ‧ At most 5 points in this question. Define the Heuristic Function to estimate each state: Compute the sum of grids in each row and column, assumed each summation is an element in the set S. Heuristic Function: h = Σ |10 . si| s_i∈S where h is the smaller the better. The Temperature can be mapped to Time (Action times) Next state S_N, Current state S_C At higher temperature, the next state with higher h(S_N) - h(S_C) may be chosen; at lower temperature, the next state is almost chosen as the state with lowest h(S_N) - h(S_C). With the simulation annealing, the local optimal can be avoided through the random action (with the probability according to temperature). 3. (15 Points) Game Search Consider the search tree for a two-player game as shown. (a) (5 Points) Suppose both players play optimally, what is the final outcome of the game? (b) (5 Points) Circle all the nodes in the search tree above that will be pruned by alpha-beta pruning, assuming the game tree is searched from right to left. (c) (5 Points) Please re-arrange up to 5 leaf nodes so that more nodes may be pruned. http://i.imgur.com/oCIW6wC.png Figure 2: A two-player game tree with utility values at the leaf nodes. Ans: (a) (5 Points) http://i.imgur.com/B9RdQqX.png (b) (5 Points) http://i.imgur.com/9XgYzwe.png (c) (5 Points) Please re-arrange up to 5 leaf nodes so that more nodes may be pruned. http://i.imgur.com/imsL3nJ.png 4. (15 Points) Constraint Satisfaction Consider the problem of solving the Sudoku puzzle again. (a) (6 Points) Please re-formulate the problem as a CSP. (b) (4 Points) Please estimate the size of the search space. (c) (5 Points) Apply the AC-3 algorithm to solve the puzzle. Ans: You can answer the following problems for either Figuare 1 or n by n Sudoku (a) (6 Points) You need to answer the following three elements. ‧ (2 Points) Variables = {A_11, A_12, ..., A_44} ‧ (2 Points) Domains = {1, 2, 3, 4} ‧ (2 Points) Constraints = {A_i1 ≠ A_i2 ≠ A_i3 ≠ A_i4, A_1i ≠ A_2i ≠ A_3i ≠ A_4i, A_11 ≠ A_12 ≠ A_21 ≠ A_22, A_13 ≠ A_14 ≠ A_23 ≠ A_24, A_31 ≠ A_32 ≠ A_41 ≠ A_42, A_33 ≠ A_34 ≠ A_43 ≠ A_44, 1 ≦ i ≦ 4, i ∈ N} (b) (4 Points) You get at most 2 points if you don't explain how you get the complexity. ‧ n is the number of rows. Since each block has n choice and there are n*n blocks, the complexity is O(n^(n*n)). (c) (5 Points) You have to list the steps by applying AC-3 on either Figure 1 or general cases. You get at most 2 points if you just write down the solution. 5. (15 Points) Propositional Logic Consider the following sentence. [(P => D) Ｖ (B => D)] Λ C => [(P Λ B) => D]. (a) (4 Points) Determine, using enumeration, whether this sentence is valid, satisfiable (but not valid), or unsatisfiable. (b) (5 Points) Convert the entire sentence into CNF, showing each step. (c) (6 Points) Prove your answer to (a) using resolution Ans: The precedence (order of operations): 「﹁」＞「Ｖ」, 「Λ」＞「=>」 Therefore, the original formula can be presented as f: f = {[(P => D) Ｖ (B => D)] Λ C} => [(P Λ B) => D] (a) Truth-table enumeration : ‧ 4 points for showing the correct truth table ‧ You have to use enumeration methods, otherwise you can only get at most 2 points Ｂ│Ｃ│Ｄ│Ｐ│P=>D│B=>D│[(P=>D)Ｖ(B=>D)]ΛC │[(PΛB)=>D] │ｆ ─┼─┼─┼─┼──┼──┼──────────┼──────┼─ Ｔ│Ｔ│Ｔ│Ｔ│ Ｔ │ Ｔ │ Ｔ │ Ｔ │Ｔ Ｔ│Ｔ│Ｔ│Ｆ│ Ｔ │ Ｔ │ Ｔ │ Ｔ │Ｔ Ｔ│Ｔ│Ｆ│Ｔ│ Ｆ │ Ｆ │ Ｆ │ Ｆ │Ｔ Ｔ│Ｔ│Ｆ│Ｆ│ Ｔ │ Ｆ │ Ｔ │ Ｔ │Ｔ Ｔ│Ｆ│Ｔ│Ｔ│ Ｔ │ Ｔ │ Ｆ │ Ｆ │Ｔ Ｔ│Ｆ│Ｔ│Ｆ│ Ｔ │ Ｔ │ Ｆ │ Ｔ │Ｔ Ｔ│Ｆ│Ｆ│Ｔ│ Ｆ │ Ｆ │ Ｆ │ Ｆ │Ｔ Ｔ│Ｆ│Ｆ│Ｆ│ Ｔ │ Ｔ │ Ｆ │ Ｔ │Ｔ Ｆ│Ｔ│Ｔ│Ｔ│ Ｔ │ Ｔ │ Ｔ │ Ｔ │Ｔ Ｆ│Ｔ│Ｔ│Ｆ│ Ｔ │ Ｔ │ Ｔ │ Ｔ │Ｔ Ｆ│Ｔ│Ｆ│Ｔ│ Ｆ │ Ｔ │ Ｔ │ Ｔ │Ｔ Ｆ│Ｔ│Ｆ│Ｆ│ Ｔ │ Ｔ │ Ｔ │ Ｔ │Ｔ Ｆ│Ｆ│Ｔ│Ｔ│ Ｔ │ Ｔ │ Ｆ │ Ｔ │Ｔ Ｆ│Ｆ│Ｔ│Ｆ│ Ｔ │ Ｔ │ Ｆ │ Ｔ │Ｔ Ｆ│Ｆ│Ｆ│Ｔ│ Ｆ │ Ｔ │ Ｆ │ Ｔ │Ｔ Ｆ│Ｆ│Ｆ│Ｆ│ Ｔ │ Ｔ │ Ｆ │ Ｔ │Ｔ Therefore it is valid according to the column of f (b) Converting steps: ‧ 1 points for each of following steps (except step 1) ‧ 2 points for the correct result ‧ If no step is shown, you can only get at most 2 points 1.) Eliminate <=>: (ignore) 2.) Eliminate ==>: ‧ P => D ~> ﹁P Ｖ D ‧ B => D ~> ﹁B Ｖ D ‧ (P Λ B) => D ~> ﹁(P Λ B) Ｖ D ‧ f ~> ﹁[(﹁P Ｖ D Ｖ ﹁B Ｖ D) Λ C] Ｖ [﹁(P ^ B) Ｖ D] ~> ﹁[(﹁P Ｖ D Ｖ ﹁B) Λ C] Ｖ [﹁(P Λ B) Ｖ D] 3.) Move ﹁ inward: ‧ ﹁(P Λ B) Ｖ D ~> ﹁P Ｖ ﹁B Ｖ D ‧ ﹁[(﹁P Ｖ D Ｖ ﹁B) Λ C] ~> ﹁(﹁P Ｖ D Ｖ ﹁B) Ｖ ﹁C ~> (P Λ ﹁D Λ B) Ｖ ﹁C ‧ f ~> (P Λ ﹁D Λ B) Ｖ ﹁C Ｖ ﹁P Ｖ ﹁B Ｖ D 4.) Apply the distributivity law: ‧ (P Λ ﹁D Λ B) Ｖ ﹁C Ｖ ﹁P Ｖ ﹁B Ｖ D ~> (P Ｖ ﹁C Ｖ ﹁P Ｖ ﹁B Ｖ D) Λ (D Ｖ ﹁C Ｖ ﹁P Ｖ ﹁B Ｖ D) Λ (B Ｖ ﹁C Ｖ ﹁P Ｖ ﹁B Ｖ D) (c) ‧ If no resolution steps is shown, you can only get at most 3 points ‧ 3 points for the resolution tree (or resolution steps) ‧ 1 points for the re-processing steps ‧ 2 points for the correct result i. Negation of the consequent: ﹁((P Λ B) => D) and the antecedent [(P => D) Ｖ (B => D)] Λ C form our knowledge base ii. Convert each of them: ‧ ﹁(﹁(P Λ B) Ｖ D) ≡ ﹁﹁(P Λ B) Λ ﹁D ≡ P Λ B Λ ﹁D ‧ [(P => D) Ｖ (B => D)] Λ C ≡ [(﹁P Ｖ D) Ｖ (﹁B Ｖ D)] Λ C iii. Use knowledge base: (﹁P Ｖ D) Ｖ (﹁B Ｖ D), C to show P Λ B Λ ﹁D will be resolved by the Resolution Tree. ﹁P Ｖ D Ｖ ﹁B P ╲ ╱ ╲╱ ﹁B Ｖ D B ╲ ╱ ╲╱ D ﹁D ╲ ╱ ╲╱ □ 6. (20 Points) Short-Answer Questions (a) (4 Points) Describe two significant events in the history of AI. (b) (4 Points) A physical symbol system has the necessary and sufficient means for general intelligent action. Please argue for or against it. (c) (4 Points) Construct an admissible heuristic that is not consistent. (d) (4 Points) What are the critical capabilities for Watson to win Jeopardy!? (e) (4 Points) Give a PEAS description of a task environment in which a simple reflex agent will fail. Ans: (a) (4 Points) 2 points for each event. ‧ Dartmouth Conference 1958: The birth of AI. ‧ IBM Deep Blue defeated world champion Garry Kasparov. (b) (4 Points) You need to claim your reason for the statement. (c) (4 Points) 2 points if your heuristic function is admissible. 2 points if your heuristic function is not consisten. (d) (4 Points) You need to answer least two capabilities. 2 points for each capability. ‧ Computing power ‧ Nature language processing to understand the question (e) (4 Points) You need to give a PEAS description that the agent will fail. 1 point for each element. If you don't give a PEAS description, you get at most 2 points. ‧ An agent for driving a car from one place to another. It will fail because there are many unexcepted things that can't be handle by a simple reflex agent. ‧ Perfomance Measure: time ‧ Enviroment: roads ‧ Actuator: wheel, break ‧ Sensor: camera at front 7. (5 Points) Bonus Please make one suggestion for possible improvements to the course. --

※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.228.12.163 ※ 文章網址: https://webptt.com/m.aspx?n=bbs/NTU-Exam/M.1441740631.A.B0C.html