Computational Intelligence - Problems for Chapter 4 -- Solution to part (b)

Go backward to Solution to part (a)
Go up to 7 Solving a CSP via backtracking, arc consistency, hillclimbing
Go forward to Solution to part (c)

Solution to part (b)

The optimal orderings are

[ B, C, E, D, A]
[ B, D, E, C, A]
[ C, B, E, D, A]
[ C, E, B, D, A]
[ D, B, E, C, A]
[ D, E, B, C, A]
[ E, C, B, D, A]
[ E, D, B, C, A]

There each have 49 failing branches. Some close orderings are:

[ B, C, D, E, A]
[ B, D, C, E, A]
[ C, B, D, E, A]
[ C, E, D, B, A]
[ D, B, C, E, A]
[ D, E, C, B, A]
[ E, C, D, B, A]
[ E, D, C, B, A]

There each have 61 failing branches.

[ B, C, E, A, D]
[ C, B, E, A, D]
[ C, E, B, A, D]
[ E, C, B, A, D]

These each have 64 failing branches. So how would one go about arguing for a good ordering? We can look at a strategy that tries to cut out as big a proportion of the branches as possible at each stage. It doesn't matter what we choose first. The second choice should make the biggest pruning which can be done if we choose a node that uses the > constraint. This has cut the possibilities to a few of the pairs. The third constraint then has to prune as much as possible again. The ones that prune the most are those that have constraints with both of the first two variables. The first three variables should either be {B,C,D} or {C,D,E}. Note that if a branch gets pruned on the third step, it doesn't matter what the ordering of the variables is.