-
August 30th, 2014, 02:55 PM
#31
Re: Difficult Algorithm!
Originally Posted by Ceffa93
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.
-
August 30th, 2014, 05:01 PM
#32
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
-
August 30th, 2014, 08:19 PM
#33
Re: Difficult Algorithm!
Originally Posted by Ceffa93
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.
-
August 31st, 2014, 04:18 AM
#34
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
-
August 31st, 2014, 10:12 AM
#35
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 ?
-
August 31st, 2014, 10:55 AM
#36
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.
-
August 31st, 2014, 11:02 AM
#37
Re: Difficult Algorithm!
Originally Posted by Ceffa93
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.
-
August 31st, 2014, 11:26 AM
#38
Re: Difficult Algorithm!
Yes but how could i know if it is NP complete?
is there a way to verify that?
-
August 31st, 2014, 11:32 AM
#39
Re: Difficult Algorithm!
Originally Posted by Ceffa93
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.
-
August 31st, 2014, 11:42 AM
#40
Re: Difficult Algorithm!
Originally Posted by Ceffa93
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 ...
-
September 1st, 2014, 05:44 AM
#41
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 ...
-
September 1st, 2014, 06:08 AM
#42
Re: Difficult Algorithm!
Originally Posted by superbonzo
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)
-
September 1st, 2014, 08:09 AM
#43
Re: Difficult Algorithm!
Originally Posted by 2kaud
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 ...
-
September 1st, 2014, 08:19 AM
#44
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)
-
September 1st, 2014, 01:31 PM
#45
Re: Difficult Algorithm!
Originally Posted by superbonzo
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.
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
|