

![0_image_0.png](0_image_0.png)

When comparing the minimal number of visited nodes of all the heuristics for all the hard instances, we found that only five of them (which were all inconsistent) required more than 150 visited nodes. This is particularly remarkable as all these instances are from the phase-transition region of an NP-hard problem, i.e., instances which are usually considered to be the most difficult ones. Further note that about 15% (120) of the 788 (pathconsistent) instances were inconsistent, which is much higher than usual (cf. Figure 7). Interestingly, most of those inconsistent instances were solved faster than the consistent instances. At this point, it should be noted that combining heuristics orthogonally is very similar to randomized search techniques with restarts (Selman, Levesque, & Mitchell, 1992).

However, in contrast to randomized search, our method can also determine whether an instance is inconsistent. In Figure 11 we chart the number of hard instances solved with the smallest number of visited nodes with respect to their solubility. Due to the low number of hard instances of A(n,d,4.0), the figure on the left looks a bit ugly but one can at least approximate the behavior of the curves when comparing it with the second figure on the right whi is the same curve for H ( n, d, 4.0) (see below). The oscillating behavior of the inconsistent instances (more instances are solved with an odd than with an even number of visited nodes) might be due to the sizes of the instances—we generated instances with an even number of nodes only. The most difficult instance ( n = 56, d = 10) was solved as inconsistent with the B/static/global heuristic using about 91,000 visited nodes while all heuristics using one of the maximal tractable subsets as a split set failed to solve it even when each was allowed to visit 20,000,000 nodes in the search space.

We did the same examination for the set of 75,081 hard instances of H ( n, d, 4.0).  2,640 of these instances could not be solved by any of the 20 different heuristics using 10,000 visited nodes each. Their distribution is shown in Figure 12(a). Similar to the hard instances of A ( n, d, 4.0), the heuristics using H s as a split set were the most successful ones for solving the hard instances of H ( n, d, 4.0), as shown in Table 2.  They solved more of the hard instances than any other heuristics and produced the fastest response of more than 50% of the hard instances.  There is no significant difference between using C s, Q s, or B as a split set, neither in the number of solved instances nor in the percentage of first response. Like in the previous case, computing constrainedness using the static/global or the dynamic/local heuristics resulted in more successful paths through the search space by which