Top Qs
Timeline
Chat
Perspective
Pebble motion problems
Set of related problems in graph theory From Wikipedia, the free encyclopedia
Remove ads
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.
Remove ads
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.
Remove ads
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.
Remove ads