Pebble motion problems
Set of related problems in graph theory From Wikipedia, the free encyclopedia
The pebble motion problems, or pebble motion on graphs, are a set of related problems in graph theory dealing with the movement of multiple objects ("pebbles") from vertex to vertex in a graph with a constraint on the number of pebbles that can occupy a vertex at any time. Pebble motion problems occur in domains such as multi-robot motion planning (in which the pebbles are robots) and network routing (in which the pebbles are packets of data). The best-known example of a pebble motion problem is the famous 15 puzzle where a disordered group of fifteen tiles must be rearranged within a 4x4 grid by sliding one tile at a time.
Theoretical formulation
Summarize
Perspective
The general form of the pebble motion problem is Pebble Motion on Graphs[1] formulated as follows:
Let be a graph with vertices. Let be a set of pebbles with . An arrangement of pebbles is a mapping such that for . A move consists of transferring pebble from vertex to adjacent unoccupied vertex . The Pebble Motion on Graphs problem is to decide, given two arrangements and , whether there is a sequence of moves that transforms into .
Variations
Common variations on the problem limit the structure of the graph to be:
- a tree[2]
- a square grid,[3]
- a bi-connected graph.[4]
Another set of variations consider the case in which some[5] or all[3] of the pebbles are unlabeled and interchangeable.
Other versions of the problem seek not only to prove reachability but to find a (potentially optimal) sequence of moves (i.e. a plan) which performs the transformation.
Complexity
Finding the shortest solution sequence in the pebble motion on graphs problem (with labeled pebbles) is known to be NP-hard[6] and APX-hard.[3] The unlabeled problem can be solved in polynomial time when using the cost metric mentioned above (minimizing the total number of moves to adjacent vertices), but is NP-hard for other natural cost metrics.[3]
References
Wikiwand - on
Seamless Wikipedia browsing. On steroids.