Python与人工智能 - 中国大学mooc

已完结

 451

第1周

课后作业

1、Q4 Conditional Probabilities Select all of the following statements that are true for all joint distributions over XX and YY.

2、(续上题)

3、(续上题)

4、(续上题)

5、(续上题)

6、Q1 Probabilistic Inference Your box of cereal may be a contest winner! It's rattling, which 100% of winning boxes do. Of course 1% of all boxes rattle and only one box in a million is a winner. What is the probability that your box is a winner? Note on answer formatting: Please specify your answer as a decimal probability (i.e. .05 rather than 5%). Do not include zeros before the decimal. To receive credit, your answer must match ours exactly.

7、Q2 Events You are playing a solitaire game in which you are dealt three cards without replacement from a simplified deck of 10 cards (marked 1 through 10). You win if one of your cards is a 10 or if all of your cards are odd. How many winning hands are there if different orders are different hands?

8、(续上题) 216+60=276216+60=276 What is your chance of winning? (round your answer to 3 decimal places)

9、Q3 Expectations Someone rolls a fair six-sided die and you win points equal to the number shown. What is the expected number of points after one roll?

10、(续上题) After 2 rolls?

11、(续上题) After 100 rolls?

第2周

课后作业

1、Q7 HashingQ7.1 Which critical operation is generally faster in a hash table than in a linked list?

A、inserting an element into the data structure

B、testing for the membership of an element in the data structure

C、(无)

D、(无)

2、Q7.2 On average, how fast is this operation in a hash table?

A、

B、

C、

D、

3、Q7.3 On average, how fast is this operation in a linked list?

A、

B、

C、

D、

4、Q6 Logarithms Select all of the the following statements that are true.

5、(续上题)

6、(续上题)

7、(续上题)

8、(续上题)

9、(续上题)

10、Q5 Linear Equations You know that

and

What is x?

11、(续上题) What is y?

第3周

课后作业

1、Q6 Hive Minds: Lonely BugIntroduction The next five questions share a common setup. You control one or more insects in a rectangular maze-like environment with dimensions M MM times N NN , as shown in the figure below.

At each time step, an insect can either (a) move into an adjacent square if that square is currently free, or (b) stay in its current location. Squares may be blocked by walls, but the map is known. Optimality is always in terms of time steps; all actions have cost 1 regardless of the number of insects moving or where they move. For each of the five questions, you should answer for a general instance of the problem, not simply for the example maps shown. Problems For this problem, you control a single insect as shown in the maze above, which must reach a designated target location X, also known as the hive. There are no other insects moving around.Q6.1 Which of the following is a minimal correct state space representation?

A、An integer (d) encoding the Manhattan distance to the hive.

B、A tuple ((x, y)) encoding the (x) and (y) coordinates of the insect.

C、A tuple ((x, y, d)) encoding the insect's (x) and (y) coordinates as well as the Manhattan distance to the hive.

D、This cannot be represented as a search problem.

2、Q6.2 What is the size of the state space?

A、

B、

C、

D、

3、Q7 Hive Minds: Swarm Movement You control KKK insects, each of which has a specific target ending location

XkXk. No two insects may occupy the same square. In each time step all insects move simultaneously to a currently free square (or stay in place); adjacent insects cannot swap in a single time step.

A、

B、

C、

D、

4、Q7.2 What is the size of the above state space?

A、

B、

C、

D、

5、Q8 Hive Minds: Migrating Birds You again control a single insect, but there are BBB birds flying along known paths. Specifically, at time ttt each bird b bbwill be at position

(xb(t),yb(t))(xb(t),yb(t)). The tuple of bird positions repeats with period TTT. Birds might move up to 3 squares per time step. An example is shown below, but keep in mind that you should answer for a general instance of the problem, not simply the map and path shown below. Your insect can share squares with birds and it can even hitch a ride on them! On any time step that your insect shares a square with a bird, the insect may either move as normal or move directly to the bird’s next location (either action has cost 1, even if the bird travels farther than one square).

Q8.1 Which of the following is a minimal state representation?

A、

B、

C、

D、

6、Q8.2 Which of the following is the size of the state space?

A、

B、

C、

D、

7、Q8.3 Which of the following heuristics are admissible (if any)?

A、Cost of optimal path to target in the simpler problem that has no birds.

B、Manhattan distance from the insect's current position to the target.

C、Manhattan distance from the insect's current position to the nearest bird.

D、Manhattan distance from the insect's current position to the target divided by three.

8、Q6.3 Which of the following heuristics are admissible (if any)?

A、Manhattan distance from the insect’s location to the hive.

B、Euclidean distance from the insect’s location to the hive.

C、Number of steps taken by the insect.

D、(无)

9、Q7.3 Which of the following heuristics are admissible (if any)?

A、Sum of Manhattan distances from each insect's location to its target location.

B、Sum of costs of optimal paths for each insect to its goal if it were acting alone in the environment, unobstructed by the other insects.

C、Max of Manhattan distances from each insect's location to its target location.

D、Max of costs of optimal paths for each insect to its goal if it were acting alone in the environment, unobstructed by the other insects.

10、Q1 Search Trees How many nodes are in the complete search tree for the given state space graph? The start state is S. You may find it helpful to draw out the search tree on a piece of paper.

11、Q2 Depth-First Graph Search Consider a depth-first graph search on the graph below, where S is the start and G is the goal state. Assume that ties are broken alphabetically (so a partial plan S->X->A would be expanded before S->X->B and S->A->Z would be expanded before S->B->A). You may find it helpful to execute the search on scratch paper. Please enter the final path returned by depth-first graph search in the box below. Your answer should be a string with S as your first character and G as your last character. Don't include arrows or spaces in your submission. For example, if you believe the path is S->X->G, please enter SXG in the box.

12、Q3 Breadth-First Graph Search Consider a breadth-first graph search on the graph below, where S is the start and G is the goal state. Assume that ties are broken alphabetically (so a partial plan S->X->A would be expanded before S->X->B and S->A->Z would be expanded before S->B->A). You may find it helpful to execute the search on scratch paper. Please enter the final path returned by breadth-first graph search in the box below. Your answer should be a string with S as your first character and G as your last character. Don't include arrows or spaces in your submission. For example, if you believe the path is S->X->G, please enter SXG in the box.

第4周

课后作业

1、Q4 A* Graph Search Consider A* graph search on the graph below. Arcs are labeled with action costs and states are labeled with heuristic values. Assume that ties are broken alphabetically (so a partial plan S->X->A would be expanded before S->X->B and S->A->Z would be expanded before S->B->A.

Q4.1 In what order are states expanded by A* graph search? You may find it helpful to execute the search on scratch paper.

A、Start, A, B, C, D, Goal

B、Start, A, C, Goal

C、Start, B, A, D, C, Goal

D、Start, A, D, Goal

2、Q4.2 What path does A* graph search return?

A、Start-A-C-Goal

B、Start-B-Goal

C、Start-A-D-Goal

D、Start-A-B-Goal

3、Q5 Uniform-Cost Graph Search Consider the graph below. Arcs are labeled with their weights. Assume that ties are broken alphabetically (so a partial plan S->X->A would be expanded before S->X->B and S->A->Z would be expanded before S->B->A.

Q5.1 In what order are states expanded by Uniform Cost Search? You may find it helpful to execute the search on scratch paper.

A、Start, A, B, C, D, Goal

B、Start, A, C, Goal

C、Start, B, A, D, C, Goal

D、Start, A, D, Goal

4、Q5.2 What path does uniform cost search return?

A、Start-A-C-Goal

B、Start-B-Goal

C、Start-A-D-Goal

D、Start-A-B-Goal

5、Q9 Hive Minds: Jumping Bug Your single insect is alone in the maze again. This time, it has super legs that can take it as far as you want in a straight line in each time step. The disadvantage of these legs is that they make turning slower, so now it takes the insect a time step to change the direction it is facing. Moving vv squares v requires that all intermediate squares passed through, as well as the vvvth square, currently be empty. The cost of a multi-square move is still 1 time unit, as is a turning move. As an example, the arrows in the maze below indicate where the insect will be and which direction it is facing after each time step in the optimal (fewest time steps) plan (cost 5):

Q9.1 Which of the following is a minimal state representation?

A、A tuple (x,y) giving the position of the insect.

B、A tuple (x,y) giving the position of the insect, plus the direction the insect is facing.

C、A tuple (x,y) giving the position of the insect, plus an integer representing the number of direction changes necessary on the optimal path from the insect to the goal.

D、A tuple (x,y) giving the position of the insect, plus an integer t representing the number of time steps that have passed.

6、Q9.2 What is the size of the state space?

A、

B、

C、

D、

7、Q10 Hive Minds: Lost at Night It is night and you control a single insect. You know the maze, but you do not know what square the insect will start in. You must pose a search problem whose solution is an all-purpose sequence of actions such that, after executing those actions, the insect is guaranteed to be on the exit square, regardless of initial position. The insect executes the actions mindlessly and does not know whether its moves succeed: if it uses an action which would move it in a blocked direction, it will stay where it is. For example, in the maze below, moving right twice guarantees that the insect will be at the exit regardless of its starting position.

Q10.1 Which of the following state representations could be used to solve this problem?

A、A tuple (x,y) representing the position of the insect.

B、A tuple (x,y) representing the position of the insect, plus a list of all squares visited by the insect.

C、An integer t representing how many time steps have passed, plus an integer b representing how many times the insect's motion has been blocked by a wall.

D、A list of boolean variables, one for each position in the maze, indicating whether the insect could be in that position.

8、Q10.2 What is the size of the state space?

A、

B、

C、

D、

9、Q10.3 Which of the following are admissible heuristics?

A、Total number of possible locations the insect might be in.

B、The maximum of Manhattan distances to the exit square from each possible location the insect could be in.

C、The minimum of Manhattan distances to the exit square from each possible location the insect could be in.

D、(无)

10、Q11 Hive Minds: Time Limit In this problem, the ladybug has a limited number of timesteps remaining. For each timestep, there is no moving penalty, but the remaining time will decrease by one. The ladybug will gain or lose points when it lands on positive or negative values, respectively. The ladybug must move to a new square for each timestamp, and the ladybug cannot move to a square that it has already visited. Your goal in this problem is to find the optimal score (higher is better) for a given timestep limit.

Q11.1 What is the optimal score for a timestep of 2?:

11、(续上题)Q11.2 What is the optimal score for a timestep of 5?:

12、(续上题)Q11.3 What is the optimal score for a timestep of 8?:

13、Q11.4 What is the optimal score for a timestep of 11?:

第5周

课后作业

1、Q12 Early Goal Checking Graph Search Recall from lecture the general algorithm for GRAPH-SEARCH reproduced below.

With the above implementation a node that reaches a goal state may sit on the fringe while the algorithm continues to search for a path that reaches a goal state. Let's consider altering the algorithm by testing whether a node reaches a goal state when inserting into the fringe. Concretely, we add the line of code highlighted below:

Now, we've produced a graph search algorithm that can find a solution faster. However, In doing so we might have affected some properties of the algorithm. To explore the possible differences, consider the example graph below.

Q12.1 If using EARLY-GOAL-CHECKING-GRAPH-SEARCH with a Uniform Cost node expansion strategy, which path, if any, will the algorithm return?

A、S-G

B、S-A-G

C、EARLY-GOAL-CHECKING-GRAPH-SEARCH will not find a solution path.

D、(无)

2、Q12.2 If using EARLY-GOAL-CHECKING-GRAPH-SEARCH with an A* node expansion strategy, which path, if any, will the algorithm return?

A、S-G

B、S-A-G

C、EARLY-GOAL-CHECKING-GRAPH-SEARCH will not find a solution path.

D、(无)

3、Q13 Lookahead Graph Search Recall from lecture the general algorithm for Graph Search reproduced below.

Using GRAPH-SEARCH, when a node is expanded it is added to the closed set. This means that even if a node is added to the fringe multiple times it will not be expanded more than once. Consider an alternative version of GRAPH-SEARCH, LOOKAHEAD-GRAPH-SEARCH, which saves memory by using a "fringe-closed-set" keeping track of which states have been on the fringe and only adding a child node to the fringe if the state of that child node has not been added to it at some point. Concretely, we replace the highlighted block above with the highlighted block below.

Now, we've produced a more memory efficient graph search algorithm. However, in doing so, we might have affected some properties of the algorithm. To explore the possible differences, consider the example graph below.

Q13.1 If using LOOKAHEAD-GRAPH-SEARCH with an A* node expansion strategy, which path will this algorithm return? (We strongly encourage you to step through the execution of the algorithm on a scratch sheet of paper and keep track of the fringe and the search tree as nodes get added to the fringe.)

A、S→A→D→G

B、S→B→G

C、S→A→C→G

D、S→B→D→G

4、Q12.3 Assume you run EARLY-GOAL-CHECKING-GRAPH-SEARCH with the Uniform Cost node expansion strategy, select all statements that are true.

A、The EXPAND function can be called at most once for each state.

B、The algorithm is complete.

C、The algorithm will return an optimal solution.

D、(无)

5、Q12.4 Assume you run EARLY-GOAL-CHECKING-GRAPH-SEARCH with the A* node expansion strategy and a consistent heuristic, select all statements that are true.

A、The EXPAND function can be called at most once for each state.

B、The algorithm is complete.

C、The algorithm will return an optimal solution.

D、(无)

6、Q13.2 Assume you run LOOKAHEAD-GRAPH-SEARCH with the A* node expansion strategy and a consistent heuristic, select all statements that are true.

A、The EXPAND function can be called at most once for each state.

B、The algorithm is complete.

C、The algorithm will return an optimal solution.

D、(无)

7、Q14 Memory Efficient Graph Search 7 Points Recall from lecture the general algorithm for GRAPH-SEARCH reproduced below.

Using GRAPH-SEARCH, when a node is expanded it is added to the closed set. This means that even if a node is added to the fringe multiple times it will not be expanded more than once. Consider an alternate version of GRAPH-SEARCH, MEMORY-EFFICIENT-GRAPH-SEARCH, which saves memory by (a) not adding node n nn to the fringe if STATE[nnn] is in the closed set, and (b) checking if there is already a node in the fringe with last state equal to STATE[nnn]. If so, rather than simply inserting, it checks whether the old node or the new node has the cheaper path and then accordingly leaves the fringe unchanged or replaces the old node by the new node. By doing this the fringe needs less memory, however insertion becomes more computationally expensive. More concretely, MEMORY-EFFICIENT-GRAPH-SEARCH is shown below with the changes highlighted.

Now, we've produced a more memory efficient graph search algorithm. However, in doing so, we might have affected some properties of the algorithm. Assume you run MEMORY-EFFICIENT-GRAPH-SEARCH with the A* node expansion strategy and a consistent heuristic, select all statements that are true.

A、The EXPAND function can be called at most once for each state.

B、The algorithm is complete.

C、The algorithm will return an optimal solution.

D、(无)

第6周

课后作业

1、(续上题) Select the boxes for leaf values that don't get visited due to pruning

A、5

B、6

C、2

D、1

2、Q1 Minimax Consider the zero-sum game tree shown below. Triangles that point up, such as at the top node (root), represent choices for the maximizing player; triangles that point down represent choices for the minimizing player. Outcome values for the maximizing player are listed for each leaf node, represented by the values in squares at the bottom of the tree. Assuming both players act optimally, carry out the minimax search algorithm. Enter the values for the letter nodes in the boxes below the tree.

Input Answers Here A:

3、(续上题) B:

4、(续上题) C:

5、(续上题) D:

6、Q4 Alpha-Beta Pruning Consider the game tree shown below. Triangles that point up, such as at the top node (root), represent choices for the maximizing player; triangles that point down represent choices for the minimizing player. Assuming both players act optimally, use alpha-beta pruning to find the value of the root node. The search goes from left to right; when choosing which child to visit first, choose the left-most unvisited child. In the first set of boxes below, enter the values of the labeled nodes. Then, select the leaf nodes that don't get visited due to pruning. Hint: Note that the value of a node where pruning occurs is not necessarily the maximum or minimum (depending on which node) of its children. When you prune on conditions V>βV>βV>β or V

Enter the values of the labeled nodes A:

7、(续上题) B:

8、(续上题) C:

9、(续上题) D:

第7周

课后作业

1、Q2 Expectiminimax Consider the game tree shown below. As in the previous problem, triangles that point up, such as the top node (root), represent choices for the maximizing player; triangles that point down represent choices for the minimizing player. The circular nodes represent chance nodes in which each of the possible actions may be taken with equal probability. The square nodes at the bottom represent leaf nodes. Assuming both players act optimally, carry out the expectiminimax search algorithm. Enter the values for the letter nodes in the boxes below the tree.

Input Answers Here A:

2、(续上题) B:

3、(续上题) C:

4、(续上题) D:

5、(续上题) E:

6、(续上题) F:

7、(续上题) G:

期末考试

期末考试

1、Consider A* graph search on the graph below. Arcs are labeled with action costs and states are labeled with heuristic values. Assume that ties are broken alphabetically (so a partial plan S->X->A would be expanded before S->X->B and S->A->Z would be expanded before S->B->A.

In what order are states expanded by A* graph search? You may find it helpful to execute the search on scratch paper.

A、Start, A, B, C, D, Goal

B、Start, A, C, Goal

C、Start, B, A, D, C, Goal

D、Start, A, D, Goal

2、(续上题) What path does A* graph search return?

A、Start-A-C-Goal

B、Start-A-D-Goal

C、Start-A-B-Goal

D、Start-A-B-D-Goal

3、Assume you are given a CSP and you enforce arc consistency. Which of the following are true?

A、If the CSP has no solution, it is guaranteed that enforcement of arc consistency resulted in at least one domain being empty.

B、If the CSP has a solution, then after enforcing arc consistency, you can directly read off the solution from resulting domains.

C、In general, to determine whether the CSP has a solution, enforcing arc consistency alone is not sufficient; backtracking may be required.

D、None of the above.

4、Which of the following statements are true for an MDP?

A、If the only difference between two MDPs is the value of the discount factor then they must have the same optimal policy.

B、For an infinite horizon MDP with a finite number of states and actions and with a discount factor γ that satisfies 0

C、When running value iteration, if the policy (the greedy policy with respect to the values) has converged, the values must have converged as well.

D、None of the above

5、In general, for Q-Learning to converge to the optimal Q-values...

A、It is necessary that every state-action pair is visited infinitely often.

B、It is necessary that the learning rate α (weight given to new samples) is decreased to 0 over time.

C、It is necessary that the discount γ is less than 0.5.

D、It is necessary that actions get chosen according to

.

6、Consider the value of perfect information (VPI) of observing some node in an arbitrary decision network. Which of the following are true statements?

A、VPI is guaranteed to be positive (>0).

B、VPI is guaranteed to be nonnegative (≥0).

C、VPI is guaranteed to be nonzero.

D、The MEU after observing a node could potentially be less than the MEU before observing that node.

7、Consider the following particle filter implementations.

For each of the following statements about the two implementations, select whether they are true or false. The default implementation will typically provide a better estimate of the distribution than the alternate implementation.

8、(续上题) If the observation model is deterministic then the default implementation will typically provide a better estimate of the distribution than the alternate implementation.

9、(续上题) If the transition model is deterministic then the default implementation will typically provide a better estimate of the distribution than the alternate implementation.

10、Someone rolls a fair six-sided die and you win points equal to the number shown. What is the expected number of points after one roll?

11、(续上题) After 2 rolls?

12、(续上题) After 100 rolls?

13、Consider the game tree shown below. As in the previous problem, triangles that point up, such as the top node (root), represent choices for the maximizing player; triangles that point down represent choices for the minimizing player. The circular nodes represent chance nodes in which each of the possible actions may be taken with equal probability. The square nodes at the bottom represent leaf nodes. Assuming both players act optimally, carry out the expectiminimax search algorithm. Enter the values for the letter nodes in the boxes below the tree.

Input Answers Here G:

14、Below is a table listing the probabilities of three binary random variables. Fill in the correct values for each marginal or conditional probability below.

15、(续上题)