Is it a know problem this problem? (an extension of Nearest-Neighbor Problem) : Graphics

I met a problem which can be considered as an extension of
Nearest-Neighbor Problem.

Suppose we have n (e.g. n = 10) robots and m (e.g., m = n = 10)
locations to explore in a 3-dimensional space. We want to assign each
robot to explore a possible location, while minimizing the summation of
the distances between each robot-location pair.

If n = 1 or m = 1, it is clear this is a nearest-neighbor problem. What
if both n and m are greater than 1 (n and m are not necessarily equal)?
Is it a known problem which has been addressed by some heuristic
algorithm?

Thanks.

This sounds more like an optimization problem. You might ask this question in
sci.math.num-****ysis and sci.op-reesearch.

In article <1161647600.014183.289010@f16g2000cwb.googlegroups .com>, "Joe
Zhang" <jingqiao@gmail.com> wrote:
>I met a problem which can be considered as an extension of
>Nearest-Neighbor Problem.
>
>Suppose we have n (e.g. n = 10) robots and m (e.g., m = n = 10)
>locations to explore in a 3-dimensional space. We want to assign each
>robot to explore a possible location, while minimizing the summation of
>the distances between each robot-location pair.
>
>If n = 1 or m = 1, it is clear this is a nearest-neighbor problem. What
>if both n and m are greater than 1 (n and m are not necessarily equal)?
>Is it a known problem which has been addressed by some heuristic
>algorithm?
>
>Thanks.
>

"Joe Zhang" <jingqiao@gmail.com> wrote in message
news:1161647600.014183.289010@f16g2000cwb.googlegr oups.com...
>I met a problem which can be considered as an extension of
> Nearest-Neighbor Problem.
>
> Suppose we have n (e.g. n = 10) robots and m (e.g., m = n = 10)
> locations to explore in a 3-dimensional space. We want to assign each
> robot to explore a possible location, while minimizing the summation of
> the distances between each robot-location pair.
>
> If n = 1 or m = 1, it is clear this is a nearest-neighbor problem. What
> if both n and m are greater than 1 (n and m are not necessarily equal)?
> Is it a known problem which has been addressed by some heuristic
> algorithm?

I assume you intend to have at most one robot exploring a
location and at most one location explored by a robot. Since
the problem is symmetric in robots/location, you may assume
that n <= m. One way to view this is to have a matrix M of
squared distances between robots and locations. Each row
corresponds to a robot (use index R); each column corresponds
to a location (use index L). Your goal is to choose pairs (R,L)
so that the sum of the matrix entries M(R,L) is minimized. Once
you have chosen a pair (R,L), any other pair (R',L') must satisfy
the conditions R' is different from R and L' is different from L.

This has the flavor of dynamic programming. If you have
assigned k < n robots to k of the m locations, the assignment
of the remaining n-k robots to the remaining m-k locations is
an optimization problem of the same type. Perhaps a search
of books/literature on dynamic programming will find you an
algorithm. It appears that to find the optimal solution, you
must evaluate all squared distances, so the algorithm is at
least order O(n*m).

--
Dave Eberly
http://www.geometrictools.com

Joe Zhang <jingqiao@gmail.com> wrote:
> I met a problem which can be considered as an extension of
> Nearest-Neighbor Problem.

Not really. It's closer to a variation of a graph theory problem
known as "matching".

> Suppose we have n (e.g. n = 10) robots and m (e.g., m = n = 10)
> locations to explore in a 3-dimensional space. We want to assign each
> robot to explore a possible location, while minimizing the summation of
> the distances between each robot-location pair.

As written, this is a little too vague. You only really described
what you want for n equal to m. What's supposed to happen if n is
larger or smaller than m? Does each robot get to search more than one
location, or will some locations remain unvisited? Does one location
get multiple visits, or will some robots remain unoccupied?

--
Hans-Bernhard Broeker (broeker@physik.rwth-aachen.de)
Even if all the snow were burnt, ashes would remain.

Joe Zhang wrote:
> I met a problem which can be considered as an extension of
> Nearest-Neighbor Problem.
>
> Suppose we have n (e.g. n = 10) robots and m (e.g., m = n = 10)
> locations to explore in a 3-dimensional space. We want to assign each
> robot to explore a possible location, while minimizing the summation of
> the distances between each robot-location pair.
>
> If n = 1 or m = 1, it is clear this is a nearest-neighbor problem. What
> if both n and m are greater than 1 (n and m are not necessarily equal)?
> Is it a known problem which has been addressed by some heuristic
> algorithm?

It is a known problem, but is is not "an extension of Nearest-Neighbor Problem". Not only you failed to described your problem fully (suprisingly as most persons in this newsgroup do), but also seem not to understand it really.

Even if you have 1 robot, it is is not a "nearest-neighbor problem". In this subcase (1 robot, m nodes) it is a classic "traveling salesman problem" with full graph, nodes or vertices are your locations, and there are ((m^2)-m)/2 of edges. Even for the one robot the problem is hard (the computational cost of finding otimal solution grows exponentially to the number of vertices) and you rather won't be able find optimal solution for larger numbers.

The nearest neighbour approach here is merely a very simple approximation algorithm, which is known as "greedy algorithm" or "Johnson's algorithm". I think in worse case it should give you solution something about log(o) times worse than optimal, where o is the cost of optimal solution.

Now if you have n robot and use your nearest neighbour approach and you want to minimize the sum of distances then algorithm is the same, except you choose the best node-robot (smallest distance) pair. But if you insist on sending all robots at once, you don't really want to minmize the sum of distances only, but also the time in which robots end all tasks (ie visit all locations), right?. So you have polyoptimalization problem which does not have optimal solution as such. You will have to define some ralation between time and distance, so you have some order relation defined between pairs of possible solutions (time,distance).

I would start with simple greedy algorithm:

while(there_are_location_with_work_to_do)
{
if(is_at_least_one_robot_available)
{
choose best robot-location pair; //(closest distance)
send robot to the location;
}
else
wait_for_robot_to_report_it's_available;
}

If that's not enough and the number of location is small (really) you can try to solve multiple traveling salesman problem.

--
Grzegorz Wróbel
http://www.4neurons.com/
677265676F727940346E6575726F6E732E636F6D