- All Implemented Interfaces:
- AlgorithmInterface<PebbleInstance>
Deprecated.
@Deprecated
public class TwoPebblingBottomUp
extends TwoPebblingGeneric
NOTE: This algorithm seems to be slower than the Check2PebblingAllQValues algorithm by a significant amount. Despite
being the slower algorithm, this algorithm checks exponentially fewer configurations of pebbles and gets the same
results. Upon first glance, this seems strange. We currently believe that this is because most of the configurations
checked by the Check2PebblingAllQValues are solvable and are found to be solvable by one of the nondeterministic
solvability algorithms whereas this algorithm checks mostly unsolvable configurations and unsolvable configurations
will always resort to using MergePebbles to check the configurations. MergePebbles takes much longer than all the
nondeterministic algorithms, and thus it seems to be more beneficial to check more configurations but use
MergePebbles fewer times. Aaron Green, October 14, 2016 This algorithm checks to see if a graph violates the
two-pebbling property. It does so using the same backtracking (BottomUp) method as the PebblingNumberBottomUp
algorithm. The majority of this code should be the same as the PebblingNumberBottomUp algorithm because this
algorithm was initially just the PebblingNumberBottomUp algorithm copied and pasted into a new package. I will
attempt to outline the differences between this algorithm and the PebblingNumberBottomUp algorithm here: This
algorithm uses the Two-Pebbling approach that has been taken in the past of extending each vertex of the graph to an
additional vertex adjacent only to that vertex. This allows for Solvability algorithms to be run on the graph without
modification and still check for the ability to get two pebbles to any vertex rather than just one. After the graph
is "extended", pebbles are placed on the original vertices of the graph in the same way as the PebblingNumberBottomUp
algorithm places pebbles on the vertices. When a configuration is reached that is solvable, the algorithm removes the
pebble that caused the configuration to be solvable and then checks if the configuration (without the pebble) meets
the criterion of the two-pebbling property (i.e. if the configuration has 2 * pebblingNumber - q + 1 pebbles). If it
does meet that criterion, then it is a configuration that violates the two-pebbling property, so we output it and
continue.
- Author:
- Aaron Green Fall 2016