
August 22nd, 2014, 08:10 AM
#1
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
For me, it's hard as hell, if any of you is smarter then me, please help^^

August 22nd, 2014, 08:40 AM
#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.
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only  not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums  and not via private messages!
C++17 Compiler: Microsoft VS2017 (15.5.0)

August 22nd, 2014, 09:26 AM
#3
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...

August 22nd, 2014, 09:28 AM
#4
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

August 22nd, 2014, 09:56 AM
#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!
All advice is offered in good faith only. All my code is tested (unless stated explicitly otherwise) with the latest version of Microsoft Visual Studio (using the supported features of the latest standard) and is offered as examples only  not as production quality. I cannot offer advice regarding any other c/c++ compiler/IDE or incompatibilities with VS. You are ultimately responsible for the effects of your programs and the integrity of the machines they run on. Anything I post, code snippets, advice, etc is licensed as Public Domain https://creativecommons.org/publicdomain/zero/1.0/ and can be used without reference or acknowledgement. Also note that I only provide advice and guidance via the forums  and not via private messages!
C++17 Compiler: Microsoft VS2017 (15.5.0)

August 22nd, 2014, 08:52 PM
#6
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
For me, it's hard as hell, if any of you is smarter then me, please help^^
divide N villages into M groups & place each hospital for each group.
PS
each group consists of most closest villages to one another.

August 23rd, 2014, 03:55 AM
#7
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 ?

August 23rd, 2014, 05:57 AM
#8
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

August 23rd, 2014, 10:29 AM
#9
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 bigO, 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 ... )

August 23rd, 2014, 10:37 AM
#10
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*(n1)*...*(nm+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^^

August 23rd, 2014, 10:52 AM
#11
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 ...

August 23rd, 2014, 11:06 AM
#12

August 23rd, 2014, 03:26 PM
#13
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 zerocheckpoint.
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.

August 23rd, 2014, 04:44 PM
#14
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

August 23rd, 2014, 08:28 PM
#15
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

Forum Rules

Click Here to Expand Forum to Full Width
This a Codeguru.com survey!
OnDemand Webinars (sponsored)
