How backtracking search can be used to solve this problem

Assignment Help Computer Engineering

Reference no: EM131308414

Assignment

1. Consider a scheduling problem, where there are five activities to be scheduled in four time slots. Suppose we represent the activities by the variables A, B, C, D, and E, where the domain of each variable is {1, 2, 3, 4}. The constraints for the scheduling problem are: A > D, D > E, B ≥ A, B ≠ C, C ≠ A, C ≠ D, C ≠ D + 1, and C > E.

(a) Show how arc consistency (AC-3) can be used as a preprocessing first step. To do this you must:

(i) Draw the constraint graph (HINT: all of the constraints are binary and bidirectional);

(ii) Show an initial queue with the constraints in the order given above (the A - D constraint at the front of the queue) and then show how the queue changes throughout the algorithm; and

(iii) Show a table that illustrates how the algorithm progresses-the table consists of rows containing the constraint being considered, the elements in the domains of the two variables connected by the constraint after the arc is made consistent, and the arcs that are added to the queue by this step. Marks will be given for each of these elements of your answer.

(b) With the constraint graph preprocessed by AC-3 in part (a), show how backtracking search can be used to solve this problem. To do this, you must draw the search tree generated to find all answers. Indicate (in a summary) the valid schedule(s) that are found. Use the following variable ordering: A, D, E, C, and B.

2. You are given a Knowledge Base consisting of the following definite clauses:

B ∧ C ⇒ A

D ⇒ B

E ⇒ B

H ⇒ D

G ∧ B ⇒ F

C ∧ K ⇒ G

A ∧ B ⇒ J

Give a top-down derivation for A.

3. Convert the following FOL sentences into clauses. Show all intermediate conversion steps. Include steps that are required to incorporate the clauses into an empty Knowledge Base.

(a) ∃x∀yL(x, y)

(b) ∀x∃yL(y, x)

4. Give a most general unifier for the following pairs of expressions (if one doesn't exist, state the reason why):

(a) P(x, B, y, D) and P(A, w, C, z)

(b) Q(x, B, y, D) and Q(A, w, C, x)

(d) G(f(x), r(x), T) and G(x, r(q), q)

(e) B(v(x, a), z) and B(p, p)

5. You are given the following Knowledge Base (already converted to clause form):

¬B(x) ν C(x), ¬C(K) ν D(L), -C(M) ν E(N), D(w) ν ¬E(y).

Using resolution, prove ∃x¬B(x). Provide a diagram as shown in the book/slides. Be certain to show any unifiers that are required in the resolution proof.

Reference no: EM131308414

Questions Cloud

Statements is correct in relation to independent projects : Which one of the following statements is correct in relation to independent projects?

How situation would be handled and what steps to begin with : Discuss how the situation would be handled and what steps to begin with. Examine how data would be retrieved and/or destroyed. Address what steps would be taken to determine the culprit.

Basic social obligation of a business organization : What are the basic social obligation of a business organization? Does this conflict wth the profit objectives of the business? What is social audit?

Examine the significant ways in which business operations : Describe one (1) scenario in which the selected transaction management or concurrency control method is needed. Examine the significant ways in which business operations would have to change if concurrency management methods were not available.

How backtracking search can be used to solve this problem : With the constraint graph preprocessed by AC-3 in part (a), show how backtracking search can be used to solve this problem. To do this, you must draw the search tree generated to find all answers. Indicate (in a summary) the valid schedule(s) that..

Discussion-integration of technology : Technology has changed the way we conduct business on a daily basis. A number of organizations have opted for integrating systems and sharing information with their counterparts.

What are the source and destination port numbers : What are the source and destination port numbers when an SNMP message carries one of the following PDUs?

How does this differ from a network diagram : Why does keeping good records help in managing your network?What type of information is shown on a wiring diagram? How does this differ from a network diagram?

Strategy consulting companys products or services : Where does the strategy-consulting firm concentrate its efforts within the processes of strategy assessment, formulation, decision making, implementation, and evaluation?

User Account

All Pages