Prev: Requesting critique of spec of my new MayLoad utility (similarto Unix 'make')
Next: B+ tree
From: sophia on 7 May 2008 12:24
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)
From: Nathaniel Calloway on 7 May 2008 13:32
sophia <sophia.agnes(a)gmail.com> writes:

> 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)

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
From: Greg Herlihy on 7 May 2008 13:56
On May 7, 9:24 am, sophia <sophia.ag...(a)gmail.com> wrote:
> 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)

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
From: Willem on 7 May 2008 14:45
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
 | 
Pages: 1
Prev: Requesting critique of spec of my new MayLoad utility (similarto Unix 'make')
Next: B+ tree