Exercise 5
Interpret the solution of the no good set in Exercise 5 as the solution of a relaxation. For each step k, write the resulting no good in the form of an inequality v ≥ Bk(x). In the simplest scheme, Bk(x) is either 0 or ∞ when Pk is infeasible, depending on x. If a feasible solution is found for Pk, Bk(x) is either zero or a finite value (i.e., the number of true variables in the feasible solution).
Exercise 4
Find an optimal solution of Exercise 4 using partial-order dynamic backtracking, where the objective is to minimize the number of medications taken. Solve the current no good set by setting a variable to false whenever possible. When a feasible solution is found, generate a no good that rules it out, and continue the search. Thus, if the solution x = (T, F, T, T, F) is found, generate the no good ¬x1 ∨ x2 ∨ ¬x3 ∨ ¬x4 ∨ x5. Continue until the search is exhaustive, and the optimal solution is the best feasible solution found.
Exercises 3
Find a feasible solution of the problem in Exercises 1, 2, and 3 by partial-order dynamic backtracking. Experiment with various choices of the last literal in a no good, and with various heuristics for solving the problem restriction.
Interpret the branching search of Exercise 2 as constraint-directed search by writing a table similar to Table 2.9.
Exercise 2
Find a feasible solution of the CNF expression in Exercise 1 using a DPL algorithm with clause learning. Branch on variables in the order x1,...,x5, and take the false branch first.
Exercise 1
A group of medications are commonly used to treat a form of cancer, but they can be taken only in certain combinations. A patient who takes Medications 1 and 2 must take Medication 5 as well. Medication 1 can be taken if and only 5 is not taken. At least one of Medications 3, 4, and 5 must be taken. If 5 is taken, then 3 or 4 must be taken. If 4 is taken, then 3 or 5 must be taken. Medication 3 must be taken if both 4 and 5 are taken. Medication 3 cannot be taken without 4, and 5 cannot be taken without 1. Let xj be true when medication j is taken, and write these conditions in propositional form. Convert them to CNF without adding variables.