Description
I. Questions
(a) Short Answer Questions: [30 marks]
i. Name a stochastic search algorithm and describe it briefly.
[4 marks]
ii. In A* algorithm, the score for each node is computed as
f(n)=g(n)+h(n). What is the meaning of g(n) and h(n) in the equation?
[4 marks]
iii. Besides α-β pruning, suggest two methods to deal with the limited
source problem when applying Minimax algorithm.
[4 marks]
iv. Evaluate Breadth-First Search and Depth-First Search and explain
briefly.
[8 marks]
v. For heuristics in A* algorithm, prove that consistency implies
admissibility but not the other way around.
[10 marks]
CSCI3230,, Written Assignment 2 2
(b) The distances between colleges in CU are shown in the map and the table
respectively below. Use both the following TWO algorithms to search for a
shortest path from S.H. Ho College (in black) to Shaw College (in red). Show all
your steps and state the paths and costs clearly. [40 marks]
i. Uniform-cost search with path cost [20 marks]
ii. Recursive Best First Search [20 marks]
Heuristic Estimated Distances to Shaw College
S.H. Ho College 24 United College 10
Morningside College 20 Lee Woo Sing College 6
Chung Chi College 17 Wu Yee Sun College 3
New Asia College 16 C.W. Chu College 12
CSCI3230, Written Assignment 2 3
(c) Describe the concept of pruning and the basic principles of α-β pruning in minimax
algorithm; Show the pruning steps with the following three-ply game tree.
(Please copy the game tree and indicate the steps of your search with brackets)
[30 marks]
≤ 9 (5)
≥ 5 (2)
= 9 (4)
≥ 13 (7)
5
(1)
9
(3)
13
(6)
10 25 14 16 32 20 36 10 15 5 6 48 23
MAX
MIN
MAX
II. Assignment Submission
You MUST complete this assignment by using any one of the computer text editors
(e.g. MS Word, WordPad, iWork Pages… etc.) and then save the document to PDF
format with A4 printable page size. Scan version of the hand written work is NOT
accepted. Please limit the file size of the PDF file less than 1MB.
You MUST submit the PDF file to the submission system on our course homepage
(within CUHK network), otherwise, we will NOT mark your assignment.
III. Important Points
You MUST STRICTLY follow these points:
a. You MUST strictly follow the submission guidelines.
b. Remember to type your FULL NAME, STUDENT ID on the assignment.
c. Late submission will NOT be entertained according to our submission system
settings.
d. Plagiarism will be seriously punished.
IV. Late Submission
According to the course homepage, late submission will lead to marks deduction.
No. of Days Late Marks Deduction
1 10%
2 30%
3 60%
4 or above 100%
