|
 |
||||||
Solving hard PCP instances
Mask method During the solving procedure,the concatenated top strings may be longer than the concatenated bottom ones. The longer part is called a configuration. In this case, the configuration is in the top. When the bottom ones are longer, the configuration is in the bottom. The mask method deals with the existance of critical configurations, which can be matched fully (leading to empty string) or be turned over (change from top to bottom or contrary). If in a PCP instance, no critical configurations in the top exist, or even they exist, none of them is valid, then this instance has top mask. There are some procedures to determine the validity of critical configurations. The bottom mask can be defined similarly. The mask method is very useful to prune branches for some instances. If one instance has top mask, any configurations in the top can be pruned because it will never lead to a solution. Bidirectional probing If every string in an instance is reversed, the result is the inversal of this instance. A PCP instance has the same solvability as its reversal, in the sense that it has a solution if and only if its reversal has, and it has the same number of optimal solutions and the same optimal length as its reversal. Though solving any of them is enough, the search difficulties in them are quite different in some cases. This reminds us of using a probing scheme to decide which direction is more promising. The solver probes both direction to a fixed depth, and then compares the numbers of visited nodes; in next step it continues searching the one with less number if no solutions found. As the branch factors in most instances are quite stable, this method worked very well in the experiment. Heuristic pruning As used in search algorithms such as A* and IDA*, the heuristic value of the solution length in a PCP instance can also be calculated based on the current state (i.e., configuration) and stand as a lower bound of the optimal solution length. The estimated value will be used to prune to hopeless nodes. One simple heuristic of a configuration on one side can be calculated by its length divided by the maximum length difference of all pairs whose string on that side is shorter than the other side. This method reduced the number of visited nodes by roughly 80% in the experiment. Cache scheme The cache scheme works like the transposition table typically used in the game problem designs. Some of the old configurations will be stored in one big cache table, and if the newly generated configuration is luckly found in this table, we probably prune it to save the time. Besides, Hash table is employed to facilitate the look-up in the cache. Depth-first iterative deepening Iterative deepening is a good approach to deal with this problem since the solver knows nothing about the upper bound for its solution at the beginning. If we set a large depth threshold, the solver may fall into the deep search; while in fact, the solution can be found by shallow search. Iterative method with carefully tuned increment can handle this weakness. Tail recursion removal This method is more like a programming technique. As the solver does not know the length of the configuration, it is impractical to set a fixed size of memory space for it. If it uses the dynamical memory allocation, it will consume lots of CPU resources. What's more, the solve routine basically is a recursive function, so the stack operations involved also pose a big overhead. The tail recursion removal will eliminate all possible tail recursions and reuse the allocated memory, thus increases the search speed prominently. Notes: The last 3 methods came directly from Richard Lorentz's paper in CG'2000.
This webpage was created on April 29, 2001
Last modified on September 10, 2001 by Ling Zhao |
Introduction
Solving hard PCP instances
Instances having no solutions
Hard instances list
Documents
Next step
Contact |
|||||