課程名稱︰人工智慧
課程性質︰選修
課程教師：許永真
開課學院：電資學院
開課系所︰資工所、網媒所、知識管理學程
考試日期（年月日）︰
考試時限（分鐘）：
試題 :
AI Midterm Sample Solution
1 Search
(20 points) Consider the task of finding the minimal cost path from an initial
city to a destination city.
(a) (4 Points) What defines the Cost of a node in Uniform Cost Search (UCS)?
(b) (4 Points) UCS is a special case of the general class of Best-First Search
algorithms. True or False? Justify your answer briefly.
(c) (4 Points) How does UCS compare with Depth-First Search in terms of space
complexity and optimality?
(d) (4 Points) How does A* improves the performance of UCS?
(e) (4 Points) How does UCS handle graph search?
Ans:
(a) (4 points) g(n) is total cost of the path from initial node to the given
node n.
(b) (2 points) True.
(2 points) The evaluation funtion used in best-first search to decide
which node to expand here is g(n), the cost from start node to the given
node n. Whenever UCS selects a node n for expansion, the optimal path to
that node has been found.
1+│(C*)/ε│
(c) (2 points) UCS: O(b ￣ ￣ ), optimal
(2 points) DFS: O(bm), not optimal
where b is branching factor, m is the maximum depth of the search tree,
C* is the cost of the optimal solution, ε is a small positive constant.
(d) (2 points) add heuristic function h(n) so f(n) = h(n) + g(n)
(2 points) It not only considers path length from start node to the given
node, but also the estimated cost of the cheapest path from n to the goal.
It will expand less nodes and become faster.
(e) (4 points) (p.84 Figure 3.14)
We use explored set to avoid repeated nodes. (and a priority queue ordered
by path-cost, etc.)
2 Beyond Classical Search
(15 points) Consider the Traveling Salesperson Problem (TSP).
(a) (6 Points) Show how the problem can be formulated and solved using hill
climbing.
(b) (4 Points) Please estimate the size of the search space (e.g. O(n^2)).
(c) (5 Points) Describe how the search may be improved using genetic
algorithms.
Ans:
(a) (2 points) states: valid permutations of all n cities (and start&end nodes
are the same), where "valid" means that continuous nodes are neighbors in
the given graph
ex: We say A-B-D-C-A is a valid tour if A&B, B&D, D&C are neighbors.
(2 points) heuristic function is total cost of the valid tour.
(2 points) successor: To move one step is to switch two nodes, and the
cost should be smaller and smaller.
(b) Orderly select one node in the permutation, and choose another node to
switch.
(we assume each permutation after switch is also valid)
ex: [A]-B-C-D you can choose B or C or D to switch with A
A-[B]-C-D you can choose A or C or D to switch with B...
In this case, search space is n*(n-1) = O(n^2)
Note: This is just an sample answer, we will grade your answer based on
your problem formulation.
(c) (2 points) initial population: a set of k randomly generated states.
(2 points) fitness function: total cost of the tour.
reproduction: a crossover point is chosen randomly, and the offsprings are
created by crossing over.
(1 point) mutation: switch the order of two cities.
3 Game Search: Multi-Agent PacMan
(20 points) Suppose that you are designing agents for the PacMan game with
multiple ghosts. PacMan acts as a max agent, and the ghosts act as min agents.
(a) (4 Points) Describe briefly how you may extend the standard minimax
algorithm to deal with the general case of multiple adversaries.
(b) (3 Points) Define an appropriate utility function.
(c) (3 Points) Define an appropriate evaluation function.
(d) (5 Points) Will a PacMan agent using alpha-beta pruning select the same
actions as an agent running minimax? Explain briefly.
(e) (5 Points) How should you fix the algorithm if the ghosts are non-optimal?
Ans:
(a) The original minimax algorithm minimizes the ghosts utility value and
maximize the PacMans utility value, dealing with the minimization and
maximization alternatively. When considering multiple ghosts, the
minimization will be repeated many times, which is the number of ghost.
Each layer corresponds to one ghost.
(b) You have to follow the definition: An utility function, which is also
called objective function or payoff function, defines the final numeric
value for a game that ends in terminal state for a player.
(c) You have to follow the definition: An evaluation function returns an
estimation of the expected utility of the game from a given position,
just as the heuristic functions. You can consider the time and position
of given state.
(d) Yes, alpha-beta pruning just eliminates the states which can not be
better. So it will not change the result.
(e) Since the ghosts are non-optimal, there exists a probability function
which determines the possibility that the ghost will choose the optimal
solution.
4 Constraint Satisfaction
(15 points) Consider the following logic puzzle.
˙ The Englishman lives in the red house.
˙ The Spaniard owns the dog.
˙ Coffee is drunk in the green house.
˙ The Ukrainian drinks tea.
˙ The green house is immediately to the right of the ivory house.
˙ The Ford driver owns the snail.
˙ A Toyota driver lives in the yellow house.
˙ Milk is drunk in the middle house.
˙ The Norwegian lives in the first house to the left.
˙ The man who drives the Chevy lives in the house next to the man with the
fox.
˙ A Toyota is parked next to the house where the horse is kept.
˙ The Dodge owner drinks orange juice.
˙ The Japanese owns a Porsche.
˙ The Norwegian lives next to the blue house.
(a) (6 Points) Formulate the problem as a CSP.
(b) (4 Points) Who owns the fish?
(c) (5 Points) What is the worst-case complexity of running AC-3 on a
tree-structured CSP?
Ans:
(a) ˙ Solution 1
The problem can be represented as a CSP by introducing a variable
for each color, pet, drink, country, and car brand (a total of
25 variables). The value of each variable is a number from 1 to 5
indicating the house number.
˙ Solution 2
Another representation is to have five variables for each house, one
with the domain of colors, one with pets, and so on.
(b) ┌───┬─────┬─────┬────┬────┬────┐
│ │ 1 │ 2 │ 3 │ 4 │ 5 │
├───┼─────┼─────┼────┼────┼────┤
│people│Norwegian │Ukrainian │English │Spaniard│Japanese│
│drink │ wine │ tea │ milk │ juice │ coffee │
│color │ yellow │ blue │ red │ ivory │ green │
│ car │ Toyota │ Chevy │ Ford │ Dodge │Porsche │
│ pet │ fox │ horse │ snail │ dog │ fish │
└───┴─────┴─────┴────┴────┴────┘
The Japanese owns fish.
(c) On a tree-structured graph, no arc will be considered more than once, so
the AC-3 algorithm is O(ED), where E is the number of edges and D is the
size of the largest domain.
5 Propositional Logic
(14 points) Given three propositions: S denotes it is sunny, R denotes it is
rainy, and H denotes happy.
(a) (4 Points) Use all three propositions to construct a valid propositional
sentence.
(b) (4 Points) Use all three propositions to construct a satisfiable
propositional Horn clause.
(c) (6 Points) Prove or disprove the following sentence using resolution.
[(S => H) Ｖ (R => ﹁H)] => [(S Λ ﹁R) => H].
Ans:
(a) (a) All three propositions must be used.
(b) The sentence must be valid.
(b) (a) All three propositions must be used.
(b) The clauses must be in the Horn form.
(Horn clause is a disjunction of literals of which at most one is
positive.)
(c) [(S => H) Ｖ (R => ﹁H)] => [(S Λ ﹁R) => H]
Transform the Negation of this sentence into CNF
╞ ﹁(﹁[(S => H) Ｖ (R => ﹁H)] Ｖ [(S Λ ﹁R) => H]
╞ [(S => H) Ｖ (R => ﹁H)] Λ ﹁[(S Λ ﹁R) => H]
╞ [(﹁S Ｖ H) Ｖ (﹁R Ｖ ﹁H)] Λ ﹁[﹁(S Λ ﹁R) Ｖ H]
╞ [(﹁S Ｖ H) Ｖ (﹁R Ｖ ﹁H)] Λ [(S Λ ﹁R) Λ ﹁H]
╞ [(﹁S Ｖ H Ｖ ﹁R Ｖ ﹁H)] Λ S Λ ﹁R Λ ﹁H
In the resolution procedure, we try to yield an empty clause.
S1) (﹁S Ｖ H Ｖ ﹁R Ｖ ﹁H)
S2) S
S3) ﹁R
S4) ﹁H
(﹁S Ｖ H Ｖ ﹁R Ｖ ﹁H)_S1 (S)_S2
╲ ╱
╲ ╱
╲╱
H Ｖ ﹁R Ｖ ﹁H (﹁H)_S4
╲ ╱
╲╱
﹁R Ｖ ﹁H ﹁R
╲ ╱
╲╱
(﹁R Ｖ ﹁H) ≠ □
So, the sentence is NOT valid.
6 First-Order Logic
(16 points) Consider the following axioms:
˙ Everyone who aces any final exam studies or is brilliant or is lucky.
˙ Everyone who makes an A aces some final exam.
˙ No CS major is lucky.
˙ Anyone who drinks beer does not study.
˙ If every CS major makes an A, then every CS major who drinks beer is
brilliant.
(a) (10 Points) Please translate the English sentences into First-Order Logic.
(b) (3 Points) Please convert the first FOL sentence into CNF.
(c) (3 Points) Please convert the last FOL sentence into CNF.
Ans:
Define
Domain P: people, E: final exams Function A(x, y): x aces final exam y,
x ∈ P, y ∈ E
Function S(x): x studies, x ∈ P
Function B(x): x is brilliant, x ∈ P
Function L(x): x is lucky, x ∈ P
Function C(x): x majors CS, x ∈ P
Function D(x): x drinks beer, x ∈ P
(a) 1.) ∀x∃y (A(x, y) => S(x) Ｖ B(x) Ｖ L(x))
2.) ∀x∃y (A(x, y))
3.) !∃x C(x) Λ L(x)
4.) ∀x D(x) => ﹁S(x)
5.) ∀x∃y (C(x) Λ A(x, y) => (C(x) Λ D(x) => B(x))
(b) ∀x∀y (A(x, y) => S(x) Ｖ B(x) Ｖ L(x))
╞ ∀x∀y (﹁A(x, y) Ｖ S(x) Ｖ B(x) Ｖ L(x))
╞ ﹁A(x, y) Ｖ S(x) Ｖ B(x) Ｖ L(x)
(c) ∀x∃y (C(x) Λ A(x, y) => (C(x) Λ D(x) => B(x))
╞ ∀x∃y ﹁(C(x) Λ A(x, y)) Ｖ ((C(x) Λ D(x)) => B(x))
╞ ∀x∃y ﹁(C(x) Λ A(x, y)) Ｖ (﹁(C(x) Λ D(x)) Ｖ B(x))
╞ ∀x∃y ﹁C(x) Ｖ ﹁A(x, y) Ｖ ﹁C(x) Ｖ ﹁D(x) Ｖ B(x)
╞ ∀x ﹁C(x) Ｖ ﹁A(x, g(x)) Ｖ ﹁C(x) Ｖ ﹁D(x) Ｖ B(x)
╞ ﹁C(x) Ｖ ﹁A(x, g(x)) Ｖ ﹁C(x) Ｖ ﹁D(x) Ｖ B(x)
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 36.231.77.69
※ 文章網址: https://www.ptt.cc/bbs/NTU-Exam/M.1441983659.A.411.html