Artificial Intelligence Midterm Exam
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
Artificial Intelligence
Midterm Exam
March 9, 2022
Problem 1: 25 points
The BIN PACKING problem is defined as follows. You are given:
● A set of bins, each of which has a capacity (a positive number).
● A set of objects, each of which has a volume (a positive number).
The problem is to put each object in a bin in such a way that the total volume of objects in each bin is at most the capacity of the bin. You are not allowed to split an object between two bins.
For instance suppose you have three bins: X and Y with capacity 10 and Z with capacity 13. You
have six objects: P and Q with volume 6, and R, S, T, and U with volume 5. A solution is P-Z, Q-Z, R -X, S-X, T-Y, U-Y.
A. (10 points) Describe how you could use blind state space search to solve the BIN PACKING problem. Your answer should specify what is a state; what are the successors to a state; what is the start state; and what is a goal state.
B. (5 points) Would depth first search or iterative deepening search be more appropriate for the state space you’ve defined in (A)?
C. (10 points) Suppose we consider a state space where a “state” is any assignment of all the objects to bins. For instance, one state would be { P-X, Q-Y, R-X, S-Y, T-Y, U-Y }. Describe how you might use hill climbing over this space. You should specify (a) what are the neighbors of a state; (b) what is the cost function. (You can just describe the cost function in words; you do not have to give a formula in mathematical notation.)
Problem 2: 10 points
Convert the following two sentences to CNF. (You need only show the answer, not the intermediate stages.)
1) [A ÷ B] ÷ C.
2) C ÷ -[A V B].
Problem 3: 20 points
Use the Davis-Putnam algorithm to find a valuation satisfying all the clauses below. . Give a trace, in the style of the solution to the practice exam.
1) A ^ -B.
2) A ^ -C.
3) A ^ D ^ E.
4) -A ^ B ^ C.
5) -A ^ -C ^ - E.
6) -A ^ -D.
7) -B ^ C ^ D.
8) -C ^ E.
9) -C ^ -D ^ E.
Problem 4: 20 points
As discussed in class, the “Hamiltonian path” problem is the problem of finding a path through a graph from a specified starting point that goes once through every vertex.
The class notes linked here on the subject show how an instance of Hamiltonian path can be trans- lated into the propositional calculus.
Suppose, now, we consider the following modified version of Hamiltonian path. Given:
An undirected graph G.
A starting vertex, S .
A fixed number of steps, M .
A list of vertices that must be reached, L.
Find a path through G that starts in S, reaches all of the vertices in L and uses no more than M steps. The path is allowed to repeat vertices.
For instance in this graph, if S=A, M=5, and L = { D,F }, then one solution is A-B-C-F-C-D.
Explain how an instance of this kind of problem can be translated into the propositional calculus. If you want, you can phrase your answer in terms of how you would modify the solution in the notes for Hamiltonian path, or you can start from scratch.
BE SURE THAT YOUR ANSWER WOULD WORK FOR ANY INSTANCE OF THIS PROBLEM, NOT JUST THE PARTICULAR EXAMPLE SHOWN ABOVE.
THIS QUESTION IS ABOUT PROPOSITIONAL LOGIC, NOT THE PREDICATE CALCULUS. YOUR LOGICAL SENTENCES SHOULD NOT CONTAIN QUANTIFIERS.
Problem 5: 25 points
Let u be a domain consisting of people and countries. Let c be a language with the following symbols:
Predicates:
F(p1,p2): Persons p1 and p2 are friends.
B(c1,c2): Countries c1 and c2 border one another.
C(p,c): Person p is a citizen of country c.
V(p,c): Person p has visited country c.
Constants:
A – Anne. D – Debby. J – John. E – Egypt. I – India. U — US.
Express the following sentences in c:
A. There are no countries that border both the US and India.
B. John and all his friends are American citizens.
C. In every country that borders India, Anne has a friend that is a citizen. there. (Different friends in different countries: She has one friend who is a citizen of Pakistan, one who lives in China, and so on.)
D. All Anne’s friends who are citizens of Egypt are also friends of Debby.
E. Anne has one particular friend who has visited every country that borders Egypt.
2023-03-02