程序代写代做代考 C COMP 380: Midterm Examination Fall 2020

COMP 380: Midterm Examination Fall 2020
I commit to abiding by UFV’s policies on cheating and plagiarism.
(indicate your agreement by writing your name and student number below) Student name:
Student number:
● All answers must be written in your own words.
● Pasting a quote from the textbook does not count as an answer.
● Submitting someone else’s work as your own is plagiarism and can result in failure in the
exam or failure in the course.
● You are not permitted to discuss the exam with other students during the exam period.
Section A (multiple choice and true/false) [25 points] is on Blackboard.
Section
Possible Points
Points
B
20
C
5
D
5
Total
30
Write your answers in this doc file and submit via Blackboard. Remember to save your file often.
Remember to complete the multiple-choice section on Blackboard.

Section B. Short Answer (2-3 sentences each)
1. [2 points] ​Give two examples of the limitations of the STRIPS representation for planning, i.e. things it
cannot represent or cannot easily represent. a.
b.
2. [2 points]
a. In what sense is branch-and-bound search similar to A* search?
b. In what sense is branch-and-bound search similar to depth-first search?
3. [2 points]​ How does A* search extend best-first search?
4. [2 points]​ If we have a search problem that does not involve costs, can we still use a heuristic function with
A* in order to find the optimal solution? Explain your answer.
5. [3 points]​ Define a plateau. Why are plateaus a problem for local search applied to constraint satisfaction problems?
6. [2 points] ​What are the two key weaknesses of Stochastic Local Search?
A. B.

7. [2 points] ​If we unroll a CSP planning problem to horizon ​k ​and do not find a solution, is there any point in unrolling it to a larger time horizon and trying again? Explain why or why not.
8. [3 points] ​If we have two admissible heuristics ​h1​ and ​h2​, would it be better to use ​min(h1, h2)​ or ​max(h1, h2) as a heuristic with A* search? Briefly explain your answer.
9. [2 points]​ How many states can be represented by four variables, each of which can take five values?

Section C. Arc Consistency
Consider the following constraint network.
10. [3 points]​ If the variables A, B and C each have the domain {1,2,3,4} before arc consistency is run, indicate what their domains will be after arc consistency has finished:
A={​​} B={ } C={​​}
11. [2 points] ​If we have just considered the edge and reduce the domain of B as a result, do we need to add any arcs back to the To-Do Arcs list? If not, why not? If so, which edges?
Section D. Optimality of A*
Assume that we are running A* search on a problem and we find path ​p​ to a goal. In the lecture and text, we proved mathematically that, if we are using an admissible heuristic, there is no other path that is shorter than ​p​. In other words, if path ​p’​ is still on the frontier, and ​p”​ is a path to the goal that extends ​p’,​ path ​p​ will always be less than (or equal to) ​p”.​ This is called proving the optimality of A*.
12. [5 points]​ Explain why we cannot prove the optimality of A* if the heuristic is not admissible. Be as specific and detailed as possible, referring to the proof in your answer.
Remember to complete the multiple-choice section on Blackboard.