1
$\begingroup$

Let's allow that there is a matrix of approachibilities of the NN size (N >= 500), a matrix of costs of NM and K of points with coordinates (x1, y1), (x2, y2)..., (xk, yk)

In a matrix of costs movement cost from a point of I (by xi, yi) in J point (xj, yj) is described. Thus cost is a tupple of two elements: tij - time for moving from i point to j and dij - distance between i and j points. If time is equal, it is necessary to take a point to which the distance is the smallest.

There are K of points (P1, P2, P3, P4). It is necessary to find such a point X which cost would be minimum.

The K is much smaller than N, M

enter image description here

  • 0
    If it's NP-complete, [Simulated Annealing or Tabu Search](http://docs.jboss.org/drools/release/5.4.0.Final/drools-planner-docs/html_single/inde$x$.html#d0e3890) are a good idea. If it's not NP-complete, then are better approaches: in that case, you are likely to be able to find an `A*` approach which scales decently (which means its scales like Big0(N) or Big0(N²) but not Big0(N^N)).2012-07-30

2 Answers 2

1

My first idea would be some kind of parallel Dijkstra: A node in the priority queue would be a tuple denoting a point and the identity of one of the k target points. So you'd visit each point up to k times. The priority queue would expand nodes ordered by cost (or time, whatever you choode there), without regard for the associated target node. When you visit a node which has already been visited from all the other k − 1 targets, then it has a chance to be the point x you are looking for.

If the final cost for x simply is the maximum of the k scores to the individual targets, then this will be the point you're looking for, as any point encountered later in the priority queue will have at least that maximum cost. If you want the sum to be minimal, you might have to go until costs popped from the priority queue reach k the sum of your current best candidate for node x.

If there is some relation between the geometric location of your points and the costs between these points, then perhaps you can use A* to explore your graph in a directed fashion, concentrating towards the location where some heuristic predicts the solution to be. So if there is any such relation between cost and distance, you might want to give more details on that.

0

I think this can be solved in $O(\max(N,M))$ time and $O(\max(N,M))$ space. We have to find the median of $x$ coordinates and median of all $y$ coordinates in the $k$ points and the answer will be $(x_{median},y_{median})$;

Let the input of the coordinates be an array of coordinates.

coord_t c[k] struct coord_t {    int x;    int y; }; 

My idea is to create an array of size = N>M?N:M;

int array[size] = {0}; //initialize all the elements in the array to zero  for(i=0;i= count/2) { break; }  int x_median = i;  //similarly with y coordinate.  int array[size] = {0} ; //initialize all the elements in the array to zero  for(i=0;i= count/2) { break; }  int y_median = i;  coord_t temp; temp.x = x_median; temp.y= y_median; return temp;