164 CHAPTER 4 Automatically Created Heuristics x 8 1 8 7 6 2 3 4 5 x 2 z x 1 x x 3 4 6 5 x y y z 5 FIGURE 4.2 Two abstractions of the E IGHT -P UZZLE ; top abstraction maps all involved tiles to one don't care symbol x; in the bottom abstraction, two tile labels x and y have been introduced. domain are mapped to each constant in the abstract domain. In the example, the granularity of 2 is (3, 2, 2, 1, 1) because three constants are mapped to x, two are mapped to each of y and z, and constants 5 and 0 (the blank) remain unique. In the sliding-tile puzzles, a granularity (g 1 , . . . , g k ) implies that the size of the abstract state space is n 2 !/(c · g 1 ! · · · g k !), with the choice of c {1, 2} depending on whether or not half of all states are reachable due to parity (see Sec. 1.7). In general, however, we cannot directly derive the size from the granularity of the abstraction: might not be surjective; for some abstract states u there might not exist a concrete state u such that (u) = u . In this case, the abstract space can even comprise more states than the original one, thereby rendering the method counterproductive. In general, unfortunately, it is not efficiently decidable if an abstract space is surjective. 4.2 VALTORTA'S THEOREM Without a heuristic, we can only search blindly in the original space; the use of a heuristic focuses this search, and saves us some computational effort. However, this is only beneficial if the cost of the auxiliary search required to compute h doesn't exceed these savings. Valtorta found an important theoretical limit of usefulness. Theorem 4.2. (Valtorta's Theorem) Let u be any state necessarily expanded, when the problem (s, t) is solved in S with BFS; : S S be any abstraction mapping; and the heuristic estimate h(u) be computed by blindly searching from (u) to (t). If the problem is solved by the A* algorithm using h, then either u itself will be expanded, or (u) will be expanded.