Applications

The 15-puzzle[11][9][6], a typical application from single-agent search, consists of fifteen squared tiles located in a squared tray of size . One square, the blank square, is kept empty so that an orthogonally adjacent tile can slide into its position - thus leaving a blank square at its origin. The problem is to re-arrange some given initial configuration with the fewest number of moves into a goal configuration without lifting one tile over another. While it would seem easy to obtain any solution, finding an optimal (=shortest) solution path is -complete [14]. The 15-puzzle spawns a search space of states. Using IDA*, it takes some hundred million node expansions to solve a random problem instance with the popular Manhattan distance (the sum of the minimum displacement of each tile from its goal position) as a heuristic estimate function.

Floorplan area optimization [18][17] is a stage in VLSI design. Here the relative placements and areas of the building blocks of a chip are known, but their exact dimensions can still be varied over a wide range. A floorplan is represented by two dual polar graphs and , and a list of potential implementations for each block. As shown in Figure 2, the vertices in and represent the vertical and horizontal line segments of the floorplan. There exists an edge in the graph , if there is a block in the floorplan, whose left and right edges lie on the corresponding vertical line segments. For a specific configuration (i.e. a floorplan with exact block sizes), the edges are weighted with the dimensions of the blocks in this configuration. The solution of the floorplan optimization is a configuration with minimum layout area, given by the product of the longest paths in the graphs and .

  
Figure 2: A floorplan and the graphs and

In our parallel DFBB implementation, the leaves of the search tree describe complete configurations, while the inner nodes at depth represent partial floorplans consisting of blocks . The algorithm backtracks when the area of a new partial floorplan exceeds the area of the currently best solution.