# 算法代写 | G51FAI (COMP 1032)-E1 Turn Over

这个作业是完成游戏中的A*算法设计

G51FAI (COMP 1032)-E1 Turn Over

Answer ALL questions

ADDITIONAL MATERIAL: None

SUBMISSION INSTRUCTIONS:

1. Submission

Complete your report using appropriate word processors in PDF. It must be submitted

online via Moodle. You must name your file as COMP1032-EX-XXXXXXXX.pdf (note:

XXXXXXXX is your full 8-digit student ID number).

G51FAI (COMP 1032)-E1 END

1. Search (40 marks)

Heuristic search, such as A*, can be shown to be effective (e.g. guaranteeing that the

optimal solution can be found) and efficient (e.g. it is faster because it searches a

smaller portion of the search space) for some applications, particularly those involving

finding the shortest path in real-world navigations.

Describe how a heuristic search can be designed for the problem of games. In your

answer, you are required to state out the assumptions of the problem and provide

technical arguments why your heuristic search would work effectively for the problem.

Finally, discuss how you can measure the efficiency of your search methodology.

Answer in no more than 500-words.

2. Probabilistic Reasoning (60 marks)

i. Let � and � be discrete random variables. � takes on value from {�, �, �}. � takes on

value from {1,2,3}. Answer the following questions.

[30 marks]

a) Suppose it is known that the underlying distribution for � is uniform. What is

ℙ(� = �)? Briefly explain your answer.

[4 marks]

b) Consider that you have two jointly distributed random variables � and �. Given

the following conditional probabilities ℙ(�|�):

c) � = � � = � � = �

� = 1 1/10 6/10 2/10

� = 2 1/10 3/10 6/10

� = 3 8/10 1/10 2/10

First, mathematically formulate how individual joint probability can be computed

for this problem setting. Then, compute all the joint probabilities and construct

the associated joint probability table for ℙ(�, �). Verify your computations for

ℙ(�, �) are correct.

[20 marks]

d) What are the marginal probabilities ℙ(� = �)?

[6 marks]

ii. Suppose you have a class whereby students are given their ID numbers. Suppose

that a list is made for the entire class. In this list, students are placed in a manner

whereby their corresponding ID numbers ascend. That is, this list would appear as a

list of integers in an ascending order. Demonstrate and argue why this list is a valid

random list, i.e., this list is a realization of a random variable. Full marks for a

complete, mathematical answer with further general explanations. Answer in no more

than 500-words.

[30 marks]