CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Page 3 of 4 FirstFirst 1234 LastLast
Results 31 to 45 of 46
  1. #31
    Join Date
    Feb 2013
    Posts
    58

    Re: Difficult Algorithm!

    Quote Originally Posted by Ceffa93 View Post
    S@rK0Y, i had time to read your solution only now, the computation time is intresting, but how many times do you need to balance them? I've not tought deeply about it, but at a guess, every time i balance two groups, shouldn't I restart from the begin? i mean, after balancing B and C, maybe i need to verify if my previous balance between A and B is still the optimal one, and so on...In your opinion the overall computation cost, of the whole algorithm, with your method, how much would be?
    Ye need to test ABmid & BCmid to choose the best balance. it's enough to balance each group Just once, then go to next one. if about complexity, seems C*M*lg2(N) -- C - const, M is number of groups & N is number of overall items.

  2. #32
    Join Date
    Aug 2014
    Posts
    17

    Re: Difficult Algorithm!

    I'm not sure that you need to balance it only one time...i mean, if i balance B and C, then i pass to C and D and i find out that they need to be balanced. Now my C and D groups are different then before, so, maybe, B and C are not balanced anymore, and so A and B and so on...if i just balance them one time i don't think that the solution is optimal

  3. #33
    Join Date
    Feb 2013
    Posts
    58

    Re: Difficult Algorithm!

    Quote Originally Posted by Ceffa93 View Post
    I'm not sure that you need to balance it only one time...i mean, if i balance B and C, then i pass to C and D and i find out that they need to be balanced. Now my C and D groups are different then before, so, maybe, B and C are not balanced anymore, and so A and B and so on...if i just balance them one time i don't think that the solution is optimal
    very goal of balance to exclude the farthest items from a group. if two groups ain't neighbors, they cannot affect each other because their items are to far from one another. keep in mind, if you include new item in group, max_dist cannot shrink in there.

  4. #34
    Join Date
    Aug 2014
    Posts
    17

    Re: Difficult Algorithm!

    I'm not so sure of that, i mean, A and C doesn't directly interact between them, but if i balance B and C, then i have to adjust the position of B and C centers...then i need to rebalance A and B because now the center of B changed...that's the point i'm not getting, if you change the center of a group that influences the neighbours, and the neighbour's neighbourses

  5. #35
    Join Date
    Oct 2008
    Posts
    1,456

    Re: Difficult Algorithm!

    I think the confusion comes from the fact that you didn't rigorously specified the to be minimized quantity. Sarkoy is referring to the maximal distance between groups separated by hospitals, whereas you referred to a "total" distance. Can you take a look at post#25 ?

  6. #36
    Join Date
    Aug 2014
    Posts
    17

    Re: Difficult Algorithm!

    Yes i read it, what i'm looking for is this:

    we have x villages and m hospitals.
    we place the hospitals.
    every village is distant "L" from it's nearest hospital. (ex:if village is at km 4, and hospitals are in 2 and 7, the "L" is 2 and not three)

    The minimum distance i'm looking for, is the sum of these "L" so that the total is the lowest possible.

  7. #37
    Join Date
    Jul 2013
    Posts
    576

    Re: Difficult Algorithm!

    Quote Originally Posted by Ceffa93 View Post
    sorry razzle, the greedy approach you were suggesting is interesting, but the result is not optimum, after that how do you manage to balance everything and get the optiumum solution?
    No, the greedy approach is not exact but neither is the "balancing" algorithm you're fiddling on. At least so far no one has shown that it leads to an optimal solution and so far no one has shown that it finishes in polynominal time. It's all just high hopes.

    As I've said several times now, if the problem is NP complete then searching for a polynominal algorithm is futile.
    Last edited by razzle; August 31st, 2014 at 04:17 PM.

  8. #38
    Join Date
    Aug 2014
    Posts
    17

    Re: Difficult Algorithm!

    Yes but how could i know if it is NP complete?
    is there a way to verify that?

  9. #39
    Join Date
    Jul 2013
    Posts
    576

    Re: Difficult Algorithm!

    Quote Originally Posted by Ceffa93 View Post
    Yes but how could i know if it is NP complete?
    is there a way to verify that?
    Yes there is but I cannot help you because I'm not into this type of math. The principle is simpel enougth though. One starts with a known NP complete problem and then reduce it to ones own problem which is then also NP complete.

    Have a look here for example (the proofs are outlined in theorems 1 and 2),

    http://www.cs.toronto.edu/~cebly/Pap...tAl_aaai07.pdf

    This article discusses subset problems similar to yours and they are proven to be NP-hard. (in your case a subset would be one specific selection of cities with hospitals).

    A less formal and more practical approach is to reformulate the problem to a standard problem with a known solution. If this fails it's most likely an NP complete problem. But you never know for absolutely sure of course.

    Your problem eludes a dynamic programming formulation (at least I couldn't do it). If hospitals are placed one by one in stages then when a new hospital is placed it has repercursions for all past stages and so Bellman's optimality principle is violated.

    When no "additivity" can be identified in a problem, when there's no "direction" on which to base a serach for optimality, when something is changed it influences everything else in a totally unpredictable way, then, in my experience, it's very likely an NP-hard problem.
    Last edited by razzle; September 1st, 2014 at 02:20 AM.

  10. #40
    Join Date
    Oct 2008
    Posts
    1,456

    Re: Difficult Algorithm!

    Quote Originally Posted by Ceffa93 View Post
    Yes i read it
    ok, so we agree; now, it's up to Sarkoy to realize that his "divide and balance" strategy will not give an optimal solution ...

  11. #41
    Join Date
    Oct 2008
    Posts
    1,456

    Re: Difficult Algorithm!

    thinking about it, the "continuous" limit has a rather trivial solution; that is, a straightforward calculation shows that if the (strictly increasing) function giving the village positions is twice-differentiable then the total distance ( as defined before ) has a unique minimum corresponding to hospitals placed in such a way to halve villages located between the midpoints with the previous and next hospitals.

    So, if I'm correct, this means that either a simpler solution could exist for the discrete case too or that strong bounds could be found for n,m big enough ...

  12. #42
    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 superbonzo View Post
    thinking about it, the "continuous" limit has a rather trivial solution; that is, a straightforward calculation shows that if the (strictly increasing) function giving the village positions is twice-differentiable then the total distance ( as defined before ) has a unique minimum corresponding to hospitals placed in such a way to halve villages located between the midpoints with the previous and next hospitals.

    So, if I'm correct, this means that either a simpler solution could exist for the discrete case too or that strong bounds could be found for n,m big enough ...
    From reading the initial problem description in post #1, I didn't think there was a function giving the village positions as the distance from a village to its previous one is specified separately for each village?
    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)

  13. #43
    Join Date
    Oct 2008
    Posts
    1,456

    Re: Difficult Algorithm!

    Quote Originally Posted by 2kaud View Post
    From reading the initial problem description in post #1, I didn't think there was a function giving the village positions as the distance from a village to its previous one is specified separately for each village?
    sorry, I'm not sure I understood what you said; are you referring to what I described as "the (strictly increasing) function giving the village positions" ?

    if yes, consider, say, villages placed at miles 1,4,7,17 then this defines a strictly increasing real valued function from the set {0,1,2,3} to the set of reals, or, equivalently, a "staircase" function from the real interval [0,4] to the set of reals. The total distance as defined before is just the area between this function and another staircase curve passing through the hospital positions and their midpoints. Now, if the said function can be approximated ( eventually by taking an appropriate limit ) by a twice differentiable and strictly increasing function, then we can use differential calculus to compute the minima with respect to the hospital positions ...

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

    Re: Difficult Algorithm!

    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)

  15. #45
    Join Date
    Feb 2013
    Posts
    58

    Re: Difficult Algorithm!

    Quote Originally Posted by superbonzo View Post
    ok, so we agree; now, it's up to Sarkoy to realize that his "divide and balance" strategy will not give an optimal solution ...
    i think it's more practical to have minimum distance for farthest item in each group

    I'm not so sure of that, i mean, A and C doesn't directly interact between them, but if i balance B and C, then i have to adjust the position of B and C centers...then i need to rebalance A and B because now the center of B changed...that's the point i'm not getting, if you change the center of a group that influences the neighbours, and the neighbour's neighbourses
    Ceffa, each group has closest items to each other: if A has, for eg, minimal max_dist -- you have no the least reason to re-balance there.

Page 3 of 4 FirstFirst 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