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.
Return the result of the algorithm in the context of the problem. i.e. Solvable, Unsolvable, Unknown. This tells
more than "Done" or "Not_Done" that is given in the more general sense. This might just be "true" or "false", it
might be the encoding of a series of moves, etc.
Runs the Algorithm. This is the most important method.
public java.lang.String getCurrentProblemData()
A string representation of the current state of the problem data. This should be in the same format as it
was passed in to setProblemData, but updated to give the current state based on the algorithm progress so
far. The idea is that this can be used to show the progress of the algorithm by some GUI (or in text
form, I suppose).
public boolean countsOperations()
True if and only if the algorithm intends to keep track of the number of operations it is performing.
Each algorithm is free to decide what it considers an "operation" to be.
Mostly for use in comparing results from previous versions of algorithms, and/or so we can know whether or not
data in the database is based on an older version of the algorithm. Start with "return 1.0". Go up by whatever
increments you like (e.g. 1.1, 1.2, etc. or 1, 2, 3, etc.)