A, B, C, D 
.
Suppose also that there is only one solution to this
segment: a1 for A, b3 for B, c1 for C,
and d1 for D. We wish to find this solution by
depth-first search.
Solutions to regular CSP problems are typically generated by using backtracking (or fancier search algorithms) to assemble a set of labels, one for each node, which are consistently admissible. Extracting solutions from MUSE CSPs can be done in a similar way, but it is desirable to make a few modifications to the search algorithms to take advantage of the extra information which is contained in the MUSE AC-1 data structures.
Consider the example shown in Figure 28.
This figure presents a simple MUSE CSP. Suppose we are only interested in solutions to
the segment which is highlighted: A, B, C, D .
Suppose also that there is only one solution to this
segment: a1 for A, b3 for B, c1 for C,
and d1 for D. We wish to find this solution by
depth-first search.
We begin by assigning a1 to A. However, the domain of B, in addition to the desired label b3, also contains the labels b1 and b2, which are valid only for other segments. If we initially (and naively) choose b1 for B and continue doing depth-first search, we would waste a lot of time backtracking. Fortunately, after enforcing MUSE arc consistency, the MUSE data structures contain useful information concerning the segments for which the labels are valid. In this case, the backtracking algorithm can check Local-Next-Support(B, b1) to determine which of the outgoing nodes b1 is compatible with. Since (B, C) is not an element of Local-Next-Support(B, b1), a smart search algorithm would not choose b1 as a label for B.
However, just looking at the local support sets might not be enough. After the search algorithm has rejected b1 as a label for B, it would go on to consider b2. Local-Next-Support(B, b2) indicates that b2 is a valid label for some of the segments which contain C, but it fails to tell us that b2 is not valid for the segment we are examining. Despite this, the search algorithm can still eliminate b2 by looking at Next-Support[(B, C), b2], which indicates that b2 is only compatible with segments containing the node F. Clearly, this type of information will more effectively guide the search for a solution along a certain path. Improved search strategies for MUSE CSPs will be the focus of future research efforts.
Figure 28: Using MUSE arc consistency data structures to guide a
backtracking search.