本次Python代写是完成数据结构与算法相关的测试题

CSCI 3202 Remote edition Fall 2020

(1) [35 points] For problem 1, refer to the following graph, with heuristic values h(n) depicted inside

each node in parenthesis. Consider the task of finding the shortest path from S to G, where step

costs to travel between two nodes are given as edge weights.

1A) [5 points] In what order would BFS expand the nodes of the graph? List all nodes that

are expanded and the order in which they are expanded. Assume that numeric nodes are

expanded lowest-first when an option exists.

1B) [5 points] In what order would DFS expand the nodes of the graph? List all nodes that are

expanded in the order in which they are expanded. Assume that numeric nodes are expanded

lowest-first when an option exists.

1C) [5 points] In what order would UCS expand the nodes of the graph? List all nodes that

are expanded in the order in which they are expanded.

1D) [5 points] In what order would A∗ expand the nodes of the graph? List all nodes that are

expanded in the order in which they are expanded.

3

1E) [5 points] Is the heuristic h on the graph admissible? If so, explain why. If not, explain for

which single state n you could change the values of h(n) to make everything admissible and

consistent. What range of values for h are possible to make this correction?

1F) [4 points] Suppose after making any adjustments that you’ve arrived at a consistent and

admissible heuristic h1(n). You then decide to use the new heuristic h2(n) = 2h1(n). Is A∗

the solution found using h2 guaranteed to be optimal? Justify your answer.

1G) [3 points] Provide a reason as to why using an inadmissible or inconsistent heuristic may be

a bad idea.

1H) [3 points] Provide a reason as to why using an inadmissible or inconsistent heuristic may be

a good idea.

4

(2) [30 points] Parts A-D refer to this game. We’re playing our favorite new game, “walls among us.”

In this game, we play as a noble space explorer, maintaining our 2-dimensional ship represented

by the 4×4 grid below. On our turn, we may move in one of the 4 cardinal directions, and must

move into an unoccupied square. Our opponent is attempting to sabotage us, and has sabotaged

the ship’s warp drive! We have to fix it, but our opponent is in the game, and plays as a brick

wall trying to block our way. On the wall’s turn, they also must move in one of the 4 cardinal

directions, and must also move to an unoccupied square. The game ends – with us as the victor

– when we move to the goal in the bottom-right corner of the map. The wall may never move to

that tile.

2A) [4 points] Assuming the engine might be moved to any tile on the board, what is the size of

the overall state space? The exact result should use the fact that the wall can never overlap

with either you or the engine.

2B) [10 points] Draw a game tree with one move for each player from the starting position

shown. Nodes in the tree represent game states (location of all agents and walls). Edges in

the tree connect successor states to their parent states. Draw only the legal moves.

5

2C) [4 points] On the shallow game tree of depth 2 from part 2B, what would we infer is the

value of the game? Use the score of ”number of warp drives reached by the player” as your

evaluation function.

**程序代写代做C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB**

本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！

**E-mail:** [email protected] **微信:**itcsdx

如果您使用手机请先保存二维码，微信识别。如果用电脑，直接掏出手机果断扫描。