|
Hello everyone,
I am in search of an algorithm to find the most appropriate division technique of an area.
For example; I have 3 100x500 cm of sheets and I want to get 15 50x40 cm, 2 100x100 etc. sheets. So I have to divide these 100x500 cm sheets into smaller parts. But when I -let's say- try to get 15 50x40 cm sheets from only one 100x500 cm sheet probably there will be a loss (500 mod 40 != 0).
So I have to use a combine of 50x40, 100x100 etc. sheets.
Also there isn't a must to only use quadrangles. Polygonial sheets may also used.
So is there an algorithm to get the desired number of different area shapes from a number of main shapes with less loss ?
Thanks for your helps and best regards.
.:: Something is Wrong ::.
|
|
|
|
|
IIRC what you're describing is an NP complete problem.
--
Rules of thumb should not be taken for the whole hand.
|
|
|
|
|
Sorry about my English I am not good with abbreviations. So what do you mean by IIRC and NP..
.:: Something is Wrong ::.
|
|
|
|
|
|
Maximilien wrote: NP stands for a Non Polygonial class of problems.
I think you mean "nondeterministic polynomial".
--
Marcus Kwok
|
|
|
|
|
|
sorry. IIRC is short for If I Recall Correctly, and is internet slang for I think this is right, but am not certain.
--
Rules of thumb should not be taken for the whole hand.
|
|
|
|
|
But at least there must be a subset of the NP, that is deterministic.. Am I wrong ?
.:: Something is Wrong ::.
|
|
|
|
|
There is, it's the set of problems called P. That's the sort of problem that can be done in at worst polynomial time on a normal computer.
Your question appears to indicate a bit of a vocabulary/jargon problem.
P is the set of problems that can be done in polynomial time on a dterministic turing machine. All normal computers are deterministic turing machines.
NP is the set of problems that can be done in polynomial time on a nondterministic turing machine. A nondeterministic machine guesses the correct solution (the first time, every time, in a nonexplainable way) and then proves that it is correct. A deterministic turing machine can simulate a non deterministic one, by trying each possible solution in sequence. This takes exponential time. A quantum computer is capable of directly running multiple data sets at once, but the fastest QC ever built is still no faster than a normal machine due to the low maximum qbit count it can work with.
It's believed, but not proven than P is a subset of NP, but that the two are not equal.
Depending on the problem, and conditions applied to it, there may or may not be a solution in P that can give a reasonable approximation with a known worst case error. Except for well known problems the approximations are unlikely to be published anywhere except in academic journals.
--
Rules of thumb should not be taken for the whole hand.
|
|
|
|
|
Really thanks for the explanation. So if we return to the point is there a way to "guess" or "approximate" the most proper division technique ? 
.:: Something is Wrong ::.
|
|
|
|
|
probably, but given the lack of response I don't think anyone posting here is aware of one. If you can't find anything via google you'll need to do a journal search for papers on the subject. I don't know if CS journals charge for online access or not. If so, it may be cheaper to visit the library of a major college/university than to buy access.
--
Rules of thumb should not be taken for the whole hand.
|
|
|
|
|
Ok, I will give a try, and if get a result I will share it  . But at least, which keywords should I use in search? Any ideas?
.:: Something is Wrong ::.
|
|
|
|
|
|
Yep. Following the link from there to the knapsack problem confirmed my vague recollection that it was NP-Complete.
--
Rules of thumb should not be taken for the whole hand.
|
|
|
|
|
y=x-(xz)
what is the formula for finding the value of x from the given formula above.
Thanks
|
|
|
|
|
x = y / (1 - z)
"Programming today is a race between software engineers striving to build bigger and better idiot-proof programs, and the Universe trying to produce bigger and better idiots. So far, the Universe is winning." - Rick Cook www.troschuetz.de
|
|
|
|
|
|
for z!=1 
"Throughout human history, we have been dependent on machines to survive. Fate, it seems, is not without a sense of irony. " - Morpheus
|
|
|
|
|
Can any one tell me which is the best book of Advance Algoritham analysis
|
|
|
|
|
We used Introduction to Algorithms[^] (called "CLR" or "CLRS" for short) in my algorithms class, and it was a pretty good book.
TAOCP[^] is also supposed to be very highly regarded, but I have not personally ventured into that territory yet
--
Marcus Kwok
|
|
|
|
|
|
Mythbusters had a recent episode on this problem. They used huge and thin. Didn't hurt to have a forklift to help horse it around after it got thick.
The evolution of the human genome is too important to be left to chance idiots like CSS.
|
|
|
|
|
The user provides the start, end and control points for a bezier curve on a bitmap. I need to look a certain amount above and below each point on the curve based on an int X location and rounded Y location. Is there a formula anyone knows of which will calculate the Y value of a bezier curve given the X value and the four points?
|
|
|
|
|
Hi,
I dont think it is easy to find y from x, given that x(t) and y(t) are both polynomials.
But maybe you could modify y(t) by adding your fixed vertical distance, and then walk
the modified bezier.
|
|
|
|
|
It is impossible to calculate y based on x because Bezier curves are implicit, meaning that they are not necessary functions. In this article:
http://www.codeproject.com/useritems/ArrowRenderer.asp I've provided source code that helps calculating <x,y> pairs of Bezier curve
Michał Bryłka
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
