Dear all,

The cutting sticks problem---given a stick of length L and a set of
points where it has to be cut. If the cost of making a cut is equal to
the length of the stick, what is the best algorithm to find the
optimal sequence of cuts(giving minimum cost)

sophia <sophia.agnes@gmail.com> writes:

This is not the cutting sticks problem I've heard of before.

Your problem has an intuitive answer: minimize the geometric mean of
stick lengths as they are cut. Now you can either just write some code
based on that, or you can write some inefficient but sexy tail
recursive algorithm that converges on the intuitive answer.

Or you can change the problem to make it sufficiently complex that
there are different schemes based on the initial conditions. That's
how a CS professor would approach the subject.

-Nat

On May 7, 9:24*am, sophia <sophia.ag...@gmail.com> wrote:
I would advise always cutting the stick at whichever point is closest
to the middle. After all, if we were able to divide the sticks exactly
in half with each cut - we would always have the shortest possible set
of sticks for the number of cuts we had made.

And - in order to reduce the cost of each cut - we must reduce the
length of our sticks as rapidly as we can with our cuts. Therefore, it
makes sense for us to cut each stick at the point closest to its
middle - in order for our cuts to come closest to the ideal stick-
shortening cutting protocol.

Greg

Greg wrote:
) I would advise always cutting the stick at whichever point is closest
) to the middle. After all, if we were able to divide the sticks exactly
) in half with each cut - we would always have the shortest possible set
) of sticks for the number of cuts we had made.
)
) And - in order to reduce the cost of each cut - we must reduce the
) length of our sticks as rapidly as we can with our cuts. Therefore, it
) makes sense for us to cut each stick at the point closest to its
) middle - in order for our cuts to come closest to the ideal stick-
) shortening cutting protocol.

Counterexample:

Assuming a stick of unit length.
Suppose the three cuts have to be placed at 0.45, 0.50 and 0.55.

As per your algorithm, the first cut is at the center (0.50).
If we cut first at 0.50 and then at 0.45 and 0.55, the total cost
would be 1 + 0.50 + 0.50 = 2

However, if we first cut 0.45, then 0.55 and finally 0.50, the total
cost would be 1 + 0.55 + 0.10 = 1.65


SaSW, Willem
--
Disclaimer: I am in no way responsible for any of the statements
made in the above text. For all I know I might be
drugged or something..
No I'm not paranoid. You all think I'm paranoid, don't you !
#EOT

On May 7, 11:45*am, Willem <wil...@stack.nl> wrote:
Then there probably is no practical algorithm to find the optimal
solution (or at least none has ever been discovered). Instead, a
program would have to try every possible combination of cuts to find
out which is the cheapest (of course such an exhaustive search would
quickly become prohibitively slow as the number of cuts grew).

Essentially, this problem appears to be the "knapsack" problem (given
a knapsack containing sticks of different lengths - find the
combination of sticks that add up to a particular length) in disguise.

Greg

On May 8, 2:11*am, Greg Herlihy <gre...@mac.com> wrote:
what if the problem is like this one:-
http://acm.uva.es/problemset/v100/10003.html

sophia wrote:
Some people (such as ME) read usenet in such a manner that linkage
is not available while reading. This is called 'offline reading'.
So, if your reference is a reasonable size (say under 50 lines) you
should quote it in your message.

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.


** Posted from http://www.teranews.com **

"CBFalconer" wrote:

What an appallingly bad idea! You have outdone yourself, CBF.

osmium wrote:
Let me remind you, www and Usenet are entirely different
protocols. What is your recommended use for a URL when offline?

--
[mail]: Chuck F (cbfalconer at maineline dot net)
[page]: <http://cbfalconer.home.att.net>
Try the download section.

** Posted from http://www.teranews.com **

On May 7, 11:24*pm, sophia <sophia.ag...@gmail.com> wrote:
Contrary to a suggestion in this thread,
the straightforward solution to this puzzle
is not of exponential complexity, but rather N^3/3.
Yes, I know O(N^3) = O(N^3/3) but I show the constant
divisor to emphasize that the iterative structure is
related to the volume of a pyramid.

I'm enclosing my source code (and cross-posting to
comp.lang.c) for critique. The program is *not*
thoroughly tested; I estimate it still has 1.84 bugs.
(Certain peculiar code layout details are to ensure
short lines for Usenet.)

/* begin bestcutter.c */
#include <stdlib.h>
#include <stdio.h>

#define MAXPIECE 100

/* Sol[a][b] describes substick [a ... a+b+1] */
struct {
double cost, leng;
int cutpt;
} Sol[MAXPIECE-1][MAXPIECE];

int bestcut(int xbeg, int xend)
{
int x, bstc;
double xcost, cheapest = 99999999;

for (x = xbeg + 1; x < xend; x++) {
xcost =
Sol[xbeg][x - xbeg - 1].cost
+ Sol[x][xend - x - 1].cost;
if (xcost < cheapest)
cheapest = xcost, bstc = x;
}
return bstc;
}

double mkcuts(int xbeg, int ncut)
{
int cutpt;
double tcost;

if (ncut < 1)
return 0;
cutpt = Sol[xbeg][ncut].cutpt;
tcost = Sol[xbeg][ncut].leng;
printf("Making cut at mark %d cost = %f\n",
cutpt, tcost);
return tcost
+ mkcuts(xbeg, cutpt - xbeg - 1)
+ mkcuts(cutpt, xbeg + ncut - cutpt);
}

int main(int argc, char **argv)
{
int ncut, ix1, bstc;

if (MAXPIECE + 1 < argc || argc < 2) {
printf("Usage: cutstick #L1 #L2 ... #LN\n");
printf(" where #Lk is the distance from k-1'th");
printf(" mark to k'th mark.\n (0'th and N'th");
printf(" marks are stick ends.) N <= %d.\n",
MAXPIECE);
return EXIT_FAILURE;
}
for (ix1 = 0; ix1 < argc - 1; ix1++)
Sol[ix1][0].leng = atof(argv[ix1 + 1]);
for (ncut = 1; ncut < argc - 1; ncut++)
for (ix1 = 0; ix1 < argc - ncut + 1; ix1++)
if (ncut == 1) {
Sol[ix1][ncut].cutpt = ix1 + 1;
Sol[ix1][ncut].cost =
Sol[ix1][ncut].leng =
Sol[ix1][0].leng
+ Sol[ix1 + 1][0].leng;
} else {
Sol[ix1][ncut].leng =
Sol[ix1][0].leng
+ Sol[ix1 + 1][ncut - 1].leng;
Sol[ix1][ncut].cutpt =
bstc = bestcut(ix1, ix1 + ncut + 1);
Sol[ix1][ncut].cost =
Sol[ix1][ncut].leng
+ Sol[ix1][bstc - ix1 - 1].cost
+ Sol[bstc][ncut - bstc + ix1].cost;
}
printf("Total cost = %f\n", mkcuts(0, argc - 2));
return EXIT_SUCCESS;
}
/* end bestcutter.c */
/* Sample execution:
* % bestcutter 2 3 1 5
* Making cut at mark 3 cost = 11.000000
* Making cut at mark 1 cost = 6.000000
* Making cut at mark 2 cost = 4.000000
* Total cost = 21.000000
*/

James Dow Allen

On Fri, 9 May 2008 03:48:20 -0700 (PDT), James Dow Allen
<jdallen2000@yahoo.com> wrote:


calculating the cost of the same sticks as part of your subproblems.
If there is a stick with marks at a, b, c, ... x, y, z then if you
make the first cut as a and the second cut at z you are left with a
stick of length z-a with cuts at b, c, ... x, y. If you make the
first cut at z and the second cut at a then you will have exactly the
same subproblem to solve. Saving the result and retrieving it would
be much faster than re-solving a problem you had already solved. This
needs more memory than the simple algorithm of course.

It would probably not be worthwhile storing intermediate results for
0, 1 or 2 cuts since there is no choice possible for 0 or 1 cuts and
there is an obvious algorithm for 2 cuts (cut off the longer
end-piece). I am not sure if there is an easy algorithm for three
cuts, not having thought about it at any length.

rossum

On May 11, 3:49*pm, rossum <rossu...@coldmail.com> wrote:
No. Reread the source to see that the code calculates and saves the
intermediate results exactly as you describe. It is the caller of
bestcut()
rather than bestcut() itself that saves these results -- is that
where your confusion lies?

My algorithm is O(N^3). Are your comments intended to suggest
existence of a less complex algorithm?

James

On Sun, 11 May 2008 02:51:38 -0700 (PDT), James Dow Allen
<jdallen2000@yahoo.com> wrote:


solution is expressed in procedural rather than OO terms.

thought there was an obvious speed improvement that wasn't actually
there.

Apologies for my mistake.

rossum

On May 11, 6:44*pm, rossum <rossu...@coldmail.com> wrote:
Thank *you* for bringing closure to this subthread.
Everyone can (and does) make mistakes. *Acknowledging*
a mistake, especially in these newsgroups, is as rare
as spotting a beautiful butterfly on a stormy day.

I think mine was the bigger mistake. A few well chosen
comments in the source would have prevented any
confusion.

James

On May 11, 2:51*am, James Dow Allen <jdallen2...@yahoo.com> wrote:
I'm unclear why the program has a complexity of N^3 instead of N!
(which is the number of ways in which the stick can be cut.)

Greg

sophia wrote:
As I understand it, this is equivalent to finding an optimum binary
search tree, where the stick length has been normalized to 1. The cut
points represent keys, and the segment lengths between cuts represent
the probability that a search falls between (or at the ends, below or
above) the search keys. The top node of the BST represents the cut on
the initial stick, while the child subtrees represent the cuts on the
subdivided portions of the stick. The cost of the BST is the sum over
the nodes of the probability of each key comparison. This node cost
corresponds directly to length of the stick when the cut corresponding
to the key is performed.

Willem gave an example which had a stick of length 1, with cuts at 0.45,
0.5, and 0.55. As a BST tree his solution would look like this (use a
fixed width font):

+-(0.45,1)--+
v v
[0.45] +-(0.55,0.55)-+
v v
+-(0.5,0.1)-+ [0.45]
v v
[0.05] [0.05]

Each node is represented by (K,P) where K is the key (or cut point
position in the original stick) and P is the search probability (or
length of the stick at the time the corresponding cut was made). Each
leaf is represented by [Q] where Q is the probability the search finds
the leaf (or alternately Q is the length of corresponding cut segment).

Knuth's The Art of Computer Programming (Vol. 3) covers algorithms for
optimum BSTs in section 6.2.2. The Hu-Tucker algorithm can be used
since the probability that a search will match a key exactly is
effectively 0. A suitable implementation will create an optimum BST in
time O(N log N). It is more complex than dynamic programming algorithm
James Dow Allen gave, so I am not going to try to explain it here. It
has some similarities, however, to the algorithm for finding an optimal
Huffman coding. There may even be faster algorithms, since this seems
to be a well-studied area.

For those without access to Knuth's books, Google found the thesis at
http://www.cs.rit.edu/~std3246/thesis/thesis.html. This has a more
detailed description of the Hu-Tucker algorithm.

Jack Rouse

On Sun, 11 May 2008 23:27:41 -0700 (PDT), Greg Herlihy
<greghe@mac.com> wrote:

algorithm saves intermediate results so that duplicates among your N!
possibilities are saved and not recalculated. For example on a stick
with cuts at a, b, c, ... x, y, z there will be at some point the need
to calculate the best way to cut the substick f, g, h, i , j. Once
that substick has been calculated for the first time, if the result is
stored then that result can be retrieved in constant time (array
access in James' program) which reduces the run time of the algorithm
greatly. The 5 cut substick is encountered 21! times, only one of
which needs to be calculated.

rossum

On May 13, 1:29*am, Jack Rouse <Jack.Ro...@sas.com> wrote:
Clever algorithm! And clever of Jack Rouse to notice that
this "cutting" problem was equivalent to a search or coding
problem. Thnaks for the post!

In self-defense, I never claimed my approach was "optimal":
We can assume the O(N log N) and O(N^3) algorithms
give the same answer. One wonders if there is some
other algorithm, cleverer than James but not as clever as
Hu-Tucker, with some intermediate complexity, e.g. O(N^2).

BTW, although Hu-Tucker seems specially neat, I've always
conjectured that most bright students *should* be able to come
up with the closely related Huffman algorithm.
Have any teachers tested this "conjecture"?

James Dow Allen