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