Draw the constraint graph

Assignment Help Computer Engineering

Reference no: EM131268795

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: EM131268795

Questions Cloud

Taxonomy of multiple-access protocols : Q1. Draw the taxonomy of Multiple-access Protocols. Q2. What is the advantage of token passing protocol over CSMA/CD protocol?

What does say about the shape of the graph of the ppi : A government report states that the rate of change of inflation for producer prices is decreasing. What does this say about the shape of the graph of the PPI?

Array of fibonacci numbers : Write a Java program that generates an array of Fibonacci numbers. Add comments to the program.

Behavior is a function of its consequences : The best motivator in the workplace is usually money versus The best motivator in the workplace is usually not money. What do you think determines how a company decides to structure itself? What is the difference between diversity and affirmative act..

Draw the constraint graph : CS 3346a - CS 3121a Assignment. Draw the constraint graph (HINT: all of the constraints are binary and bidirectional); 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 h..

Write a paper describing its security features : Select a NOSQL database (MongoDB, Cassandra, DynamoDB, BigTable, etc...) and write a paper describing its security features - which model is implemented, granularity of the access control

Quantification of decision rules in healthcare environment : The NHS QOF effort is obviously full of very specific point systems for evaluation. What are the strengths and weaknesses of such quantification of decision rules in a healthcare environment?

Compare seven layers of osi model to four layers of tcp-ip : In a short half page essay briefly compare the seven layers of the OSI Model to the four layers of TCP/IP. Include a simple graphic/table of the two models and show at least two protocols in each of the four layers of the TCP/IP networking model.

Evaluate the options available to bucci : Pan, the owner of an apartment building, entered into a written contract with Bucci, a paving contractor whereby Bucci was to install asphalt paving on the parking lot of the building. When Bucci finished the job, Pan gave Bucci a check for $6,500 an..

User Account

All Pages