CENG462 Artificial Intelligence Homework 2 Solved

Description

1      Problems

351. Imagine that you are responsible for the arrangement of the classroom for the exam schedule of the department on a given day. You have 6 courses, namely CENG111, CENG213, CENG223, CENG315, CENG331 and CENG351. The availability of the classrooms are given as below:
     • BMB1 is available at 09:30 and 13:30.
     • BMB2 is available at 09:30 and 13:30.
     • BMB3 is available at 13:30 and 16:30.

You should arrange the schedule so that no two exams of the same grade (whose course codes start with the same digit) are held in the same time. You may assume that all of our students perfectly prepared for the exams, so no one will complain about having consequent exams in the same day.

1. (20 points) Formulate this problem as a Constraint Satisfaction Problem by defining variables, domains and constraints. You should write the constraints for each possible assignment for the pairs of courses (You may define a set of assignable pairs then use it for the pairs, there is no need for repetition.).
2. (10 points) Give an example for termination of search during the application of backtracking by forward checking.
3. (10 points) Give an example for termination of search during the application of backtracking by arc consistency.

For item b and c, you can draw a table or formally define the behavior.

1

1. (30 points) Apply the alpha-beta cutoff for the game tree given below where the orange triangles and green circles represent the max’s and min’s turn respectively. Blue squares are final states with their values.

List v, α, β values of all explored nodes and indicate where α/β-prunning occurs in the tree (if exists).

• Prove that K ⇒ L for the following knowledge base

I ∧ J ⇒ K

• ∧ H ⇒ I
• ∧ D ⇒ J

E ∧ H ⇒ G

E ∧ F ⇒ H

G ∧ A ⇒ E

• ∧ B ⇒ E
• ∧ C ⇒ F

A B C

D

by using;

1. (15 points) Forward chaining,
2. (15 points) Backward chaining.

Show your work step by step. In case of a tie-break during the selection of next premise, choose the first premise in the alphabetical order.

2      Submission

• Submission will be done via OdtuClass system.
• You should upload a single pdf file named in the format <your-student-id> pdf (i.e. e1234567 hw2.pdf).
• Handwritten submissions will not be accepted.

2