首页 低价平台

服务介绍

代写程序 代写论文 编程辅导
程序案例 论文案例 联系方式 诚邀英才 代写选择指南
程序辅导案例 > Program >

程序代写案例-CS 467 /

欢迎使用51辅导，51作业君孵化低价透明的学长辅导平台，服务保持优质，平均费用压低50%以上！ 51fudao.top
1

Professor: Dr. Mohammed Ayoub Alaoui Mhamdi

Bishop’s University
CS 467 / CS 566 – Advanced Topics in Artificial Intelligence br>Example of final exam: Solution
The exam is worth 100 points total and has six problems. Be sure to read the whole exam
before attempting any of it. The exam is open notes. Use the provided white space to
respond to each question. Please, write legibly. The description video of this final exam is
available on Moodle.
Full name Contribution




Problem I: Recall Questions
Answer the following questions with true or false. Justify each answer with a short
explanation and / or diagram. A response without justification will automatically be
assigned the score zero.
1. Let two heuristic functions ℎ1 and ℎ2 be such that ℎ1() ≤ ℎ2() for any node .
The use of ℎ1 by
∗ makes it possible to visit a number of nodes lower or equal
compared to ℎ2. (2 points)
Solution
False. Based on the dominance and trivial heuristics of A* search, the bottom of lattice is
the zero heuristic and the top of lattice is the exact heuristic. Moreover, Max of
2

admissible heuristics is admissible. Therefore, compare between the two functions, the use
of ℎ2will be chosen to visit nodes. Moreover, A∗ search expands the node with the lowest
f(n)=g(n)+h(n) value. If g1(x) costs too much, f1(x) will greater than f2(x), then h2 will
dominate.
2. In order to find a solution more quickly with the ∗ algorithm, it is possible to give
greater weight to the heuristic value. In other words, use a value > 1 when =
+ × ℎ. (2 points)
Solution
True. However, this does not guarantee optimality since A* will become greedier.
3. When no solution exists, an efficient heuristic allows the A * algorithm to visit
fewer nodes before concluding that a solution does not exist. (2 points)
Solution
FALSE. If no solution exists, the A * algorithm will still have to traverse all the accessible
nodes in order to reach the conclusion that there is no solution, regardless of the heuristic
used.
4. In a constraint satisfaction problem (CSP), constraints of order greater than two can
be converted into binary constraints. (2 points)
Solution
True. The n-ary constraints can be converted to binary constraints by adding new variables.
5. The alpha-beta pruning algorithm always returns the same result as the Minimax
algorithm. (2 points)
Solution
True. Pruning is done to avoid visiting nodes unnecessarily.
3

6. In the worst case, the alpha-beta pruning algorithm does no pruning and has the
same algorithmic complexity as the Minimax algorithm. (2 points)
Solution
True. If we don't do any pruning, we visit the whole tree.
7. In the best case, the alpha-beta pruning algorithm runs twice as fast as the Minimax
algorithm. (2 points)
Solution
False. With the perfect ordering, the time complexity of alpha-beta pruning algorithm is
(

2 ), compared to () in Minimax algorithm. The depth solvable is doubled but the
running time is not double based on the value of m.
8. When the values iteration algorithm is used to solve an MDP problem, a bad
initialization of the values of the states may not guarantee convergence towards an
optimal solution. (2 points)
False. We assume the values iteration algorithm runs k times. When k becomes greater,
the values converge. Therefore, even the initialization is not perfect, the algorithm can still
find an optimal solution.
9. Problems without uncertainty cannot be resolved by MDP. (2 points)
FALSE. They can be resolved by formulating an MDP, the only difference being the
probability corresponding to the actions. This probability will be 1, and therefore the MDP
will correspond to a standard research tree.
Problem II: A* Search
The graph of Figure 1 illustrates a state space = {0, … , 6} and a transition function. An
oriented arc of a state to indicates that is a successor state of . Arcs are labeled
with their cost.
4


Figure 1
The function () returns true if and only if = 6. The heuristic function ℎ() is
defined using Table 1.
Table 1
State 0 1 2 3 4 5 6
ℎ() 3 3 2 7 1 4 0
1. Give a trace of the execution of the ∗ algorithm using the space of states and the
goal function and the heuristic function ℎ defined in Table 1. For each state in the
open and closed lists, give its values and . (10 points)
Iteration Open List (state, , ), … Closed List (state, , ), …
0 (s0, 3, 0)
1 (s2, 4, 2) (s1, 6, 3) (s3, 11, 4) (s0, 3, 0)
2 (s4, 4, 3) (s1, 6, 3) (s3, 11, 4) (s0, 3, 0) (s2, 4, 2)
3 (s6, 4, 4) (s1, 6, 3) (s3, 11, 4) (s0, 3, 0) (s2, 4, 2) (s3, 4, 3)
4 (s1, 6, 3) (s3, 11, 4) (s0, 3, 0) (s2, 4, 2) (s3, 4, 3) (s6, 4, 4)
5

→Solution found
2. Is the heuristic function ℎ admissible? Justify your answer. (10 points)
No. The h heuristic overestimates the remaining cost for states s3 and s5. For example, f *
(s3) = 6 (the optimal cost from s3 to s6) while h (s3) = 7. To be eligible, h (s)≤f * (s) for
all states. Note: the heuristic remains inadmissible even if the path found in a) does not
borrow any state s with an overestimated value h (s). In other words, it may happen that
A* returns an optimal solution, but this is never guaranteed, and this is generally not the
case.
Problem III: CSP
You are asked to design a program to assign seats at a wedding reception. We have
guests and circular tables, each with a capacity of (maximum number of people per
table). It is assumed that the number of tables is sufficient for the number of guests ( ≥
). Answer the following questions as clearly as possible in the space provided.
1. Suppose we have constraints on the people who must sit at the same tables or at the
adjacent tables (for example parents with their children) and pairs of people who
cannot sit at the same tables or at the adjacent tables (e.g. ex-spouses). Explain how
you would formalize this problem as a constraint satisfaction problem. (10 points)
Solution
• Define a variable for each guest: N variables in total.
• The domain of each variable is the set of places: MN variables. (We could use a single
identifier for each seat or two (table, place-on-the-table)).
• We define a membership function for the same tables for two given places.
• We define a membership function in two adjacent tables for two given places (or adjacent
tables if we chose the second representation) according to the arrangement of the tables.
6

• For each group of people having to sit at the same tables or at the adjacent tables, we
define corresponding constraints.
• Same thing for people who do not have to sit at the same or adjacent tables
2. Suggest a technique (algorithm) to solve this problem as formulated in your
previous answer. (5 points)
Solution
Backtracking search with MRV and AC3.
3. As stated in point 1), the constraints are "hard" (they must be absolutely satisfied)
and the problem may not have a solution. Propose a different statement for the
problem of allocation of places in a marriage, with more flexible constraints, such
that the problem can always have a solution. (7 points)
Solution
Rather than imposing constraints on the placement of people on the tables, we express
preferences on the placement of people on the tables. To do this, we express the constraints
as before; i.e., a constraint is a pair of people who should not sit on the same table or at an
adjacent table; or on the contrary to sit on the same table or at an adjacent table. In addition,
we give a cost function, taking a constraint as an argument and returning a real number
expressing the cost linked to the violation of the constraint; thus, the function expresses the
degree of desirability of the constraint. From now on we are sure we always have a solution.
On the other hand, a returned solution could violate certain constraints.
4. Explain how you would formalize the new problem, as stated in your answer in 3),
as a problem of satisfying constraints. (3 points)
Solution
7

Same formalization as before, except that we add in addition the cost function which being
given a constraint returns a real number expressing the cost related to the violation of the
constraint.
5. Suggest a technique (algorithm) to solve the new problem as formulated in your
previous answer. (8 points)
Solution
Use A *.
• A node is a (partial) assignment as in Backtracking-Search
• As in Backtracking-Search, in a node, we assign one variable at a time.
• Given a (partial) assignment, let's define the cost of the assignment as the sum of
the costs of the constraints violated by the assignment.
• The cost of a transition between two successive assignments is the difference in
costs between these transitions.
• The heuristic function gives the cost estimate between the current node (partial
assignment) and an optimal full assignment: We could calculate it by estimating
the cost of violating constraints by the remaining variables (i.e., variables not yet
present in the current partial assignment).
There may be better h functions but defining them is a real challenge.
Problem IV: Alpha-Beta Pruning
Let a zero-sum game where two players, Min and Max, compete. The turn is returned to
Max. The current configuration of the game is given by node 1. The Successors() function
gives the child nodes of a node. The Utility() function returns the utility value of a leaf
node.
Nodes Successors() Utility() h() Nœud Successors() Utility() h()
n0 {n1, n2, n3} 1 n8 {} 31 31
n1 {n4, n5, n6} 0 n9 {} 7 7
8

n2 {n7, n8, n9} 6 n10 {} 16 16
n3 {n10, n11} 13 n11 {} 4 4
n4 {n12, n13} 16 n12 {} 18 18
n5 {n14, n15} 14 n13 {} 20 20
n6 {} 1 1 n14 {} 19 19
n7 {} 20 20 n15 {} 15 15
1. Draw the tree visited by the Alpha-Beta pruning algorithm. The child nodes of a
node must be visited in the same order as those of the Successors() function in the
table above. To the right of each node, enter the returned value. (7 points)
Solution

No pruning.
2. The order in which the nodes are visited can have a considerable impact on the
number of nodes visited and pruned, and thus affect the performance of the
9

algorithm. The function ℎ() returns an estimate of the utility value for each node.
How would you use the function ℎ() to prune as many nodes as possible? (3 points)
Solution
The idea is to visit the nodes that will cause pruning first. So, we sort the successors of the
Max nodes in descending order of ℎ() and the successors of the Min nodes in ascending
order.
3. Redraw the visited tree by using the strategy developed in 2). (7 points)
Problem V: MDP
Let the Markov decision process in Figure 2, which transitions are labeled by the names of
the actions and the probabilities of transitions; the states are labeled by the corresponding
rewards (expressing a utility function).
10


Figure 2
1. By using a Markovian decision process approach, indicate how to calculate the
value of the plan {0 → 1, 1 → 3, 2 → 4} in state 2 (assuming that the
execution of the plan begins in this state). Use a discount factor = 0.2.
Hint: Use simply the formula = + ∑ (, , ) , where is the reward
in the state . (5 points)
Solution
V0 = 1 + 0.2 (0.5 V0 + 0.5 V2 )
V1 = -1 + 0.2 (0.7 V0 + 0.3 V1)
V2 = -2 + 0.2 (1 V1 )
We obtain the value of 2 by resolving the system.
2. Give the value of the plan obtained in 1) in state 2, according to your formulation.
Hint: simply solve the equations’ system you obtained in 1). I suggest you to use
this solver. (5 points)
Solution
0 =
915
1054

11

1 =
−985
1054

2 =
−2035
1054

Thus, the value of the plan S2 is
−2035
1054

3. In the following table, indicate the values of the states at the end of each of the first
three iterations of the value-iteration algorithm, if a discount factor of 0.2 is used
and starting initially (iteration 0) with state values all equal to 0. Indicate only the
values, do not detail the calculations. (5 points)
Values
Iteration 1
Values
Iteration 2
Values
Iteration 3
S0 1 0.900 0.898
S1 -1 -0.920 -0.929
S2 -2 -1.920 -1.933
4. Give the action plan (policy) resulting from iteration 3. (5 points)
Solution
State Action
S0 a1
S1 a3
S2 a3
Problem VI: Algorithm A * applied to the Sokoban game
You are charged to program a resolver for the Sokoban game. In the game grid, the player
can move in four directions (up, down, left and right). The aim of the game is to push boxes
into target cells. Note that the player cannot pull the boxes. A game board is given by a
grid of cells, the player's initial position (x, y), m boxes placed at positions (bx1, by1)…
(bxm, bym) and target cells (cx1, cy1) … (Cxm, cym). It should be noted that the target
cells and boxes cannot be distinguished. Figure 3 illustrates a screenshot of a Sokoban
game. In this board, the player is represented by a snowman. Two boxes are initially placed
above the player and must be transported to the target cells which are designated by the
12

two circles. To push a box of one cell, the player must be on a neighboring cell and move
to the box. For example, to move the first box one space to the left, the player must perform
the following actions: right, up, up, and left. Only one box can be pushed at a time.

Figure 3
1. How would you use the A * algorithm to find an optimal solution to this problem?
Describe the representation of the states as well as the successor and goal functions.
(7 points)
Solution
State:
Position of the snowman (x, y) + positions of the boxes (bx1, by1)… (bxm, bym).
Successor function:
The successor function takes a state as input and returns up to 4 new successor states, each
one being the result of an up, down, left and right action. In these states, the player's
position (x, y) is moved if the box in the direction of the action is free. If a box is in the
place where the player wishes to go, the box is moved in the same direction if the box is
free. Otherwise the action is not possible and does not generate a successor.
13

Goal:
The function takes a state as a parameter and returns true if and only if all the boxes are
found in a target box (cx1, cy1)… (cxm, cym).
2. Give the most efficient admissible heuristic possible for Sokoban's game.
Hint: think of a distance we used for the Pacman, not Euclidian distance of course.
(7 points)
Solution
An admissible heuristic function should not overestimate the remaining cost. Each box
must follow a path to a goal. Thus, the sum of the distances between each box and the
closest goal is a lower bound for the number of shots to be made. To this we can add the
number of moves required to move the player to a box.
Thus:

where d(a, b) is the distance between boxes a and b. A distance from Manhattan can be
used, or better we can pre-calculate the optimal paths between all the pairs of possible
boxes with A *.

欢迎咨询51作业君
51作业君

Email:51zuoyejun

@gmail.com

添加客服微信: abby12468