john@cpss11.cps.msu.edu (Hyun Duk John) (03/25/91)
Dear Sirs :
Have you ever seen the problem stated below ?
If so, please give me the information.
Your help would be much appreciated.
Mar. 24, 1991 >>> Hyun-Duk John <<<
**************** START of the Problem **************************
<< Problem : Traveling Stars >>
A network routing problem can be simplified and/or modified to
more generalized problems. Here, one of the generalized
version of the network routing problem named ``Traveling Stars''
is described. The famous problem ``8-puzzle'' can be viewed as an
instance of the traveling stars problem. The problem can also
be viewed as a permutation problem. Only decision problems are
described here, but algorithms are of interest too.
== Problem
-. Given an undirected graph G = (V,E) and m stars, where m <= |V|.
-. A star occupies a vertex and can be moved to an adjacent
vertex one by one. (Only one star can be moved at a time)
-. No two stars can share a vertex at any moment.
-. Initially, each star i is located in its starting vertex
s(i), and is destined to its terminal vertex t(i).
-. Questions :
1. Can all the stars be moved from their starting vertices to
terminal vertices ?
2. Is there a way of moving stars from their starting vertices
to terminal vertices in less than or equal to k steps ?
(A movement of a single star from a vertex to its adjacent
vertex is called a step.)
<< A Formal Expression of the Problem >>
== For more formal approach, we define some terminologies.
-. A `state' is a sequence of vertices (v-1,v-2,...,v-m) such that
for all i <> j, v-i <> v-j.
-. A `transition' is an ordered pair of states (W,X) where
W = (w-1,w-2,...,w-m) and
X = (x-1,x-2,...,x-m), in which there exists one and only one
i, such that for all j <> i, w-j = x-j and (w-i,x-i) is in E.
-. A `move' of size k is a sequence of states
(W-0,W-1,W-2,...,W-k) where every pair
(W-i,W-(i+1)) is a transition.
We denote the move as [W-0,W-k].
== Instance :
-. Undirected graph G = (V,E).
-. Two states S and T of size m.
-. An integer k.
== Question :
-. Is there a move [S,T] ?
-. Is there a move [S,T] of size <= k ?
*********************** END ********************************