代做COMP 380编程语言、代写Java，Python程序设计

日期：2020-10-31 10:37

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 <B, A < B> 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.