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
    I don't understand what the `M`, `N` values represent. Also, how do you define the "cost" if you have to take into account both time and distance?2012-07-29
  • 0
    It seems to me that you have to define a comparison which takes both cost and time into account. Will this be a weighted sum? It also seems that you'll have to somehow combine *K* costs to compute the cost of *X* with respect to all *K* points. Will this me a sum, or a maximum, or something else?2012-07-29
  • 0
    @interjay I mixed up M with N. Costs matrix is N to N, where N is the number of points. The cost is time. And if time t1 is equal to t2 then I should prefer the point, which is nearest.2012-07-29
  • 0
    @MvG I suppose that the result should be found by minimizing the sum of times between X and each point2012-07-29
  • 0
    So there are N possible points, a given set of K points out of the N, and the solution has to also be one of the N points? If so, then the obvious brute-force solution will be O(NK) which is probably the best you can do. If not, then I don't understand the distinction between N and K.2012-07-29
  • 0
    you can consider using simulated annealing...its difference between any greedy algorithm is that sometimes you may stuck in local minimum however simulated annealing gives chances to get out of that local minimum for a better(global minimum) state...but there are other methods as well...2012-07-29
  • 0
    Hmm, interesting, I'll look...2012-07-29
  • 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/index.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;