CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 1 of 4 1234 LastLast
Results 1 to 15 of 46
  1. #1
    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

    For me, it's hard as hell, if any of you is smarter then me, please help^^

  2. #2
    2kaud's Avatar
    2kaud is online now Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    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++23 Compiler: Microsoft VS2022 (17.6.5)

  3. #3
    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. #4
    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. #5
    2kaud's Avatar
    2kaud is online now Super Moderator Power Poster
    Join Date
    Dec 2012
    Location
    England
    Posts
    7,822

    Re: Difficult Algorithm!

    Quote Originally Posted by Ceffa93 View Post
    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++23 Compiler: Microsoft VS2022 (17.6.5)

  6. #6
    Join Date
    Feb 2013
    Posts
    58

    Re: Difficult Algorithm!

    Quote Originally Posted by Ceffa93 View Post
    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.

  7. #7
    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. #8
    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. #9
    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. #10
    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. #11
    Join Date
    Oct 2008
    Posts
    1,456

    Re: Difficult Algorithm!

    Quote Originally Posted by Ceffa93 View Post
    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. #12
    Join Date
    Aug 2014
    Posts
    17

    Re: Difficult Algorithm!

    Ok thanks a lot!

  13. #13
    Join Date
    Feb 2013
    Posts
    58

    Re: Difficult Algorithm!

    Quote Originally Posted by Ceffa93 View Post
    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. #14
    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. #15
    Join Date
    Feb 2013
    Posts
    58

    Re: Difficult Algorithm!

    Quote Originally Posted by Ceffa93 View Post
    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.

Page 1 of 4 1234 LastLast

Posting Permissions

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





Click Here to Expand Forum to Full Width

Featured