Pebble motion problem
From Wiki @ Karl Jones dot com
In mathematics, a pebble motion problem, or pebble motion on graphs, is one of 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.
Description
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.
See also
External links
- Pebble motion problems @ Wikipedia
