算法代写 | 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]