代考人工智能考试 Artificial Intelligence代考 AI代考 CS代考

Artificial Intelligence: Sample Mid-Term Exam

代考人工智能考试 Problem 1 The following problem is known as EXACT SET COVER: You are given a universal set U of elements and a collection W of subsets of U.

Problem 1 代考人工智能考试

The following problem is known as EXACT SET COVER: You are given a universal set U of elements and a collection W of subsets of U. The object is to find a subcollection Y of W such that every element of U is in exactly one set in Y.

For instance, suppose that U is the set {a,b,c,d,e,f,g,h,i} and that W is the following collection:

W1 = {a,d,f,h}

W2 = {b,e,g}

W3 = {e,g}

W4= {d,e,i}

W5 = {b,d,f,h}

W6 = {a,c,i}

W7 = {c,d,e}

W8 = {b,c,f}

Then one solution would be Y={W3,W5,W6}

The following state space can be used to solve EXACT SET COVER.

• A state is a subcollection S of W such that no element of U appears in more than one set in S. For example {W1,W2} is a state.

• Let S be a state. The successors to S are formed as follows: Let X be the first element of U, alphabetically, that is not convered by any element of S, and let Wi be any set in W that contains X and does not overlap with S. Then adding Wi to S is a possible successor of S.

For instance, if S is the collection {W6}, then X is the element “b”. The successors to S are the collections {W6,W2}, and {W6,W5}. The collection {W6,W8} is not a successor to S — in fact, it is not a legitimate state at all — because both W6 and W8 contain the element “c”.

• The start state is the empty collection.

• A goal state is one that covers every element of U.

A. Show the part of the state space generated by a depth-first search for the above example. 代考人工智能考试

B. Suppose that in a particular problem, there are 100 elements in U; there are 50 sets in W; each set in W has exactly 20 elements; and each element in U is covered by exactly 10 sets in W. Thus, a solution to the problem must consist of exactly 5 sets in W (100 elements total divided by 20 elements per set). What is

the branching factor in the state space? What is the depth of the state space? Give an upper bound on the size of the state space.

C. Would it be worthwhile using iterative deepening rather than depth-first search for the problem in B? Explain your answer.

D. Suppose that in a particular problem, there are 100 elements in U; there are 50 sets in W; each set in W has between 10 and 20 elements; and each element in U is covered by between 5 and 10 sets in W. Thus, a solution to the problem contains somewhere between 5 (=100/20) and 10 (=100/10) sets in W. Might it be worthwile using iterative deepening for this problem rather than depth-first search? Explain your answer.

Problem 2 代考人工智能考试

Suppose that we want to solve EXACT SET COVER using hill climbing. Let us define a state to be any subcollection of W; for instance, in the above example {W3, W4, W7} would be one state. Propose a plausible neighbor relation on the state space and a plausible error function.

Problem 3

Convert the following sentences to CNF:

A. ~ [P ^ (Q=>R)]

B. ~[Q <=> R]

Problem 4

Trace the workings of the Davis-Putnam procedure on the set of clauses. When you reach a choice point, use the alphabetically first unbound atom and try TRUE before FALSE.

1. ~P V Q V R.

2. Q V ~R V ~W.

3. P V Q V ~R

4. ~Q.

5. ~P V ~W

6. W V X

7. ~R V W V ~X.

Problem 5 代考人工智能考试

Let U be a domain of people and books. Let L a first-order language over U with the following symbols:

B(b,p) — book b is a biography of person p

G(p1,p2,b) — person p1 gave a copy of book b to person p2.

O(p,b) — person p owns a copy of book b.

W(p,b) — person p wrote book b.

F(p1,p2) — persons p1,p2 are friends.

A,P,S — Anne, Pamela, Sam

Express the following in L

1. Sam gave a copy of a book by Anne to Pamela.

2. If person p1 gave book b to person p2 then p2 owns a copy of b.

3. Sam owns a copy of every book that Anne has written.

4. The only books that Anne has written are biographies of friends of Anne’s.

更多代写：personal statement计算机代写  托福家庭版保分  英国代写  Finance an Management 金融与管理Essay代写  Research Paper作业代写  计算机体系结构cs代写

合作平台：essay代写 论文代写 写手招聘 英国留学生代写