CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com

1. Junior Member
Join Date
Aug 2014
Posts
17

## Difficult Algorithm!

Hi everyone, i have a difficult problem to solve, and i need a risolutive algorithm, but i just can't find a solution to it...i'll explain the problem:

I have N villages and M hospitals.
The villages are disposed on a street, and every village is at a certain mile of the road:
ex:

0______5________12__14_15......

i need to place M hospitals so that the total distance that the villagers have to cover is minimun...

example: if i place an hospital in 12 and one in 5, the villagers in zero have to cover 5 miles, the ones in 5 zero, the ones in 12 zero, the ones in 14 two and the ones in 15 three...

i need an algorithm that, given the villages distances, can put the M hospitals to minimize the total distance

2. ## Re: Difficult Algorithm!

There is probably a smart algorithm to do this (which some smart guru will no doubt point out ), but one 'obvious' solution is just brute force through all the possible solutions.

Given that M < N (its trivial if M >=N !), there are a defined and calculable number of ways of placing M pegs in N holes (hole is a village and peg is a hospital) where there is no distinction between the pegs. For each way M is placed in N, total the distance covered and the order of M that gives the minimum distance is the optimal solution.

3. Junior Member
Join Date
Aug 2014
Posts
17

## Re: Difficult Algorithm!

Yes, I thought of that, the problem is that the computation cost is around N^M, which is really bad, i'm sure that there is something better...

4. Junior Member
Join Date
Aug 2014
Posts
17

## Re: Difficult Algorithm!

The point of the problem is to find the fastest algorithm possible, so i don't think teta(N^M) is the best one, not even close

5. ## Re: Difficult Algorithm!

Originally Posted by Ceffa93
The point of the problem is to find the fastest algorithm possible, so i don't think teta(N^M) is the best one, not even close
Yeah!

6. Member
Join Date
Feb 2013
Posts
58

## Re: Difficult Algorithm!

Originally Posted by Ceffa93
Hi everyone, i have a difficult problem to solve, and i need a risolutive algorithm, but i just can't find a solution to it...i'll explain the problem:

I have N villages and M hospitals.
The villages are disposed on a street, and every village is at a certain mile of the road:
ex:

0______5________12__14_15......

i need to place M hospitals so that the total distance that the villagers have to cover is minimun...

example: if i place an hospital in 12 and one in 5, the villagers in zero have to cover 5 miles, the ones in 5 zero, the ones in 12 zero, the ones in 14 two and the ones in 15 three...

i need an algorithm that, given the villages distances, can put the M hospitals to minimize the total distance

divide N villages into M groups & place each hospital for each group.

PS

each group consists of most closest villages to one another.

7. Senior Member
Join Date
Oct 2008
Posts
1,456

## Re: Difficult Algorithm!

by "total distance", do you mean the sum of all distances from each village to its nearest hospital, or the maximum such distance ?

8. Junior Member
Join Date
Aug 2014
Posts
17

## Re: Difficult Algorithm!

S@rk0y: I thought of that, but it is not correct...i'll make an example:

|_|_|_|_|__|

the villages are at distance 1 one another, except the last one. I need to put two hospitals. Following your idea, i need to put one for each group, in this case, the second group is the last village only because the maximum distance in this example is just before him. So (supposing i put the first hospital in village 3 and the second in the last village, minimum total distance is 12. But if i put the two hospitals in 2 and 4, ignoring your rule, total distance is 9

I think your idea works only if the distance that divide two blocks of villages is greater then the dimension of the block itself (or something like that)

superbonzo: i mean the sum of the distance from village to nearest hospital so that it's minimum

9. Senior Member
Join Date
Oct 2008
Posts
1,456

## Re: Difficult Algorithm!

well, the problem is equivalent to minimizing the area between the curve given by the (sorted) village positions and the "staircase" curve passing through the hospital positions and their midpoints; hence, if you seek an approximate solution valid for N,M big and the villages are smoothly distributed, then fitting the second derivative of the village distributions and placing hospitals at the zeros would probably work ...

OTOH, if you need an exact solution I doubt you can get better than an exponential big-O, I don't know ... ( BTW, the brute force algorithm scales as N*M*Binomial(N,M) ( easily reducible to N*Binomial(N,M) ) that may be still tractable for special N vs M asymptotics ... )

10. Junior Member
Join Date
Aug 2014
Posts
17

## Re: Difficult Algorithm!

I think i get the point, but i didn't understand everything, sorry but my math notion are not superlative^^

The best optimization i came out with is the bruteforce, which should be Combination(n,m), so:

[n*(n-1)*...*(n-m+1)] / m! which is less then n^m.

when you were talking about the binomial stuff, you were referring to something like that?

Sorry again, it's only my fault i don't understand^^

11. Senior Member
Join Date
Oct 2008
Posts
1,456

## Re: Difficult Algorithm!

Originally Posted by Ceffa93
when you were talking about the binomial stuff, you were referring to something like that?
yes, that stuff ; whether the brute force is sufficient or not is up to you; you can take a look at the wikipedia article about the binomial coefficient ( asymptotics section ) to have some estimates ...

12. Junior Member
Join Date
Aug 2014
Posts
17

## Re: Difficult Algorithm!

Ok thanks a lot!

13. Member
Join Date
Feb 2013
Posts
58

## Re: Difficult Algorithm!

Originally Posted by Ceffa93
S@rk0y: I thought of that, but it is not correct...i'll make an example:

|_|_|_|_|__|

the villages are at distance 1 one another, except the last one. I need to put two hospitals. Following your idea, i need to put one for each group, in this case, the second group is the last village only because the maximum distance in this example is just before him. So (supposing i put the first hospital in village 3 and the second in the last village, minimum total distance is 12. But if i put the two hospitals in 2 and 4, ignoring your rule, total distance is 9

I think your idea works only if the distance that divide two blocks of villages is greater then the dimension of the block itself (or something like that)

superbonzo: i mean the sum of the distance from village to nearest hospital so that it's minimum
well, let's dip deeper:

1. take list of villages sorted by distances from zero-checkpoint.
2. divide that list in M groups.
3. for each group, take the two villages w/ maximal distance between them (taken villages) & place hospital at the middle of that distance.
4. perform corrections for neighboring groups.
------------------------------
it's wise to deal w/ iterative method, then you can control ratio of Time vs. Quality of Optimization. as far as i understand, here is very root to minimize maximal distances.

14. Junior Member
Join Date
Aug 2014
Posts
17

## Re: Difficult Algorithm!

Thanks, i was thinking something like it but you formalized it better...i'll try it, though i'm not sure how much computation time the "corrections" will require, it could be a lot, tomorrow i'll try to write the algorithm and see

15. Member
Join Date
Feb 2013
Posts
58

## Re: Difficult Algorithm!

Originally Posted by Ceffa93
Thanks, i was thinking something like it but you formalized it better...i'll try it, though i'm not sure how much computation time the "corrections" will require, it could be a lot, tomorrow i'll try to write the algorithm and see
you must deal w/ Just edges of the group, i. e. farthest villages. actually, correction may run the following way:

1. take group w/ longest distance between edges.
2. move edges to neighboring groups to see any opportunity to shorten the max.
3. mark the processed group as 'solved'.
4. go to group w/ new max to process further.
5. if all groups been marked as 'solved', stop the algo.

#### Posting Permissions

• You may not post new threads
• You may not post replies
• You may not post attachments
• You may not edit your posts
•