100 Essential Things You Didn't Know You Didn't Know (23 page)

These are all versions of a problem that computers find very time consuming to solve when the number of items to be packed and the number of ‘boxes’ in which to pack them becomes large.

Imagine that you can use large storage boxes that hold a maximum of 10 packages and you are given 25 packages of different sizes to stack in the boxes so as to use the smallest number of containers in the most efficient way. The sizes of the individual packages are as listed here:

6,6,5,5,5,5,4,3,2,2,3,7,6,5,4,3,2,2,4,4,5,8,2,7,1

First, let’s imagine that these packages arrive on a conveyor belt so you can’t sort them out as a group: you just stack them away one by one, as they come. The easiest strategy to follow is to put them into the first bin until the next won’t fit, and then start a new bin. You are not allowed to go back and fill empty spaces in earlier bins because they have been taken away. The strategy is sometimes called ‘Next Fit’. Here is how you end up filling the bins, starting from the left and adding a new one, as required. The 6-pack goes in the first box. The next 6-pack won’t fit so we start a 2nd box. The 5-pack won’t fit in there as well, so we start on a 3rd box. Adding the next 5-pack fills it and the next two 5-packs fill the next box and so on. Here is what ends up in the boxes if we follow this Next Fit prescription for the packages in the order given above :

[6], [6], [5,5], [5,5], [4,3,2], [2,3], [7], [6], [5,4], [3,2,2], [4,4], [5], [8,2], [7,1]

We have used 14 boxes and only three of them are full (the two [5,5]s and the [8,2]). The total amount of empty space in the unfilled boxes is 4+4+1+5+3+4+1+3+2+5+2 = 34.

The large amount of wasted space has been caused by the fact that we can’t go back and fill an empty space in an earlier box. How much better could you do if you could operate a packing strategy that allowed you to put packages in the first available box that had room? This is sometimes called ‘First Fit’ packing. Using First Fit, we start as before with a 6 and 6 in separate boxes then fill two boxes with two 5-packs. But the next is a 4-pack, which we can put in the first box with the 6. Next there is a 3-pack, which can fit in the second box with the 6-pack; then we can get two 2-packs and a 3-pack in the fifth box and so on, until we end by dropping the 1-pack back in the second box, which fills it. This is what the final packing allocation looks like:

[6,4], [6,3,1],[5,5],[5,5],[2,2,3,3],[7,2],[6,4],[5,2,2],[4,4],[5],[8],[7]

First Fit has done much better than Next Fit. We have only used 12 boxes, and the amount of wasted space is down to 1+1+2+5+2+3 = 14. We have managed to fill six of the boxes completely.

We can now start to see how we might do better still in this packing business. The wasted space tends to come when we end up with a big package later on. The spaces left in the earlier boxes are all small ones by then, and we have to start a new box for each new package. We could clearly do better if we could do some sorting of the packages into descending size order. This may not always be an option if you are handling luggage coming off an airline’s luggage belt, but let’s see how much it helps when you can do it.

If we sort our packages by descending order of size then we end up with the new list:

8,7,7,6,6,6,5,5,5,5,5,5,4,4,4,4,3,3,3,2,2,2,2,2,1

Now let’s try our old Next Fit strategy again with the sorting done – call it ‘Sorted Next Fit’. The first six packages all go in their own boxes, then we fill three boxes with pairs of 5-packs, and so on. The end result looks like this:

[8],[7],[7],[6],[6],[6],[5,5],[5,5],[5,5],[4,4],[4,4],[3,3,3],[2,2,2,2,2],[1]

Bad luck at the end! We had to use a new box just to accommodate that last 1-pack. Using Sorted Next Fit we have ended up needing 14 boxes again – just as we had to do without the sorting – and we have wastage of 34 again. This is just the same as with the unsorted Next Fit. But if that final 1-pack hadn’t been included we would have still needed 14 boxes for Next Fit but only 13 for Sorted Next Fit.

Finally, let’s see what happens with a ‘Sorted First Fit’ strategy. Again, the first six packages go into separate boxes, the six 5-packs then fill three more boxes, but then the sorting comes into its own. Three of the 4-packs fill the boxes with the 6-packs in, while the other 4-pack starts a new box. The remaining packages fill the gaps nicely, leaving only the last box unfilled:

[8,2],[7,3],[7,3],[6,4],[6,4],[6,4],[5,5],[5,5],[5,5],[4,3,2,1],[2,2,2]

We have used 11 boxes, and the only wasted space is 4 in the last box. This is far superior to the performance of our other strategies and we could ask whether it is the best possible result. Could there be another packing strategy that used fewer boxes than 11? It is easy to see that there couldn’t. The total size of all the packages we have is 1 × 8 + 2 × 7 + 3 × 6 + . . . + 5 × 2 + 1 × 1 = 106. Since each box can only contain packages of total size 10, all the packages require at least 106/10 = 10.6 boxes to accommodate them. So we can never use fewer than 11 boxes, and there will always be no fewer than at least 4 waste spaces.

In this case, we have found the best possible solution by using the Sorted First Fit method. If you look back at the very simple problem we looked at in the last section, fitting objects of three sizes into a jar, we were really using the Sorted First Fit strategy because we put the bigger objects in before the smaller ones. Unfortunately, packing problems are not all this easy. In general, there is no quick method for a computer to find the best way of packing any given assortment of packages into the smallest number of boxes. As the sizes of the boxes get bigger and the variety of sizes of the packages grows, the problem becomes computationally very hard and will eventually, if the number of packages gets big enough and their sizes diverse enough, defeat any computer to find the best allocation in a given time. Even in this problem, there are other considerations that might render the Sorted First Fit only second best. The sorting of the
packages
, on which the efficiency of the method depends, takes time. If the time taken to box up the packages is also a consideration, then just using fewer boxes may not be the most cost-effective solution.

74

Crouching Tiger

Tyger! Tyger! burning bright

In the forests of the night.

William Blake

A little while ago a tragic incident occurred at San Francisco Zoo, when Tatiana, a small (!) 135-kilogram Siberian tigress jumped over the wall of its enclosure, killed one visitor, and left two others seriously injured. Press reports quoted zoo officials as being amazed by the evidence that the tiger had managed to leap over the high wall around its enclosure: ‘She had to have jumped. How she was able to jump that high is amazing to me,’ said the zoo’s Director, Manuel Mollinedo. Although at first it was claimed that the wall around the tiger enclosure was 5.5 metres high, it later turned out to be only 3.8 metres, a good deal lower than the 5 metres recommended for safety by the American Association of Zoos and Aquariums. But should we feel safe with any of these numbers? Just how high could a tiger jump?

The wall was surrounded by a dry moat that was 10 metres wide, and so the captive tiger faced the challenge of high-jumping 3.8 metres from a running start at a horizontal distance of at least 10 metres away from the wall at take-off. Over short distances on the flat a tiger can reach top speeds of more than 22 metres per second (i.e. 50 miles per hour). From a 5-metre start, it can easily reach a launch speed of 14 metres per second.

The problem is just that of launching a projectile. It follows a parabolic path up to its maximum height and then descends. The minimum launch speed V that will achieve the vertical height h from a launch point at a distance x in front of the wall is given by the formula

V
²
= g (h + √(h
²
+ x
²
))

Where g = 10 m/s
²
is the acceleration due to Earth’s gravity. Notice some features of the equation that show that it makes sense: if gravity were made stronger (g gets bigger) then it is harder to jump, and the minimum launch-speed, V, must get bigger. Similarly, as the height of the wall, h, gets bigger or the distance away at take-off, x, increases, a larger launch-speed is needed to clear the wall.

Let’s look at the set-up of the San Francisco Zoo’s tiger enclosure shown above. The wall was 3.8 metres high, but the tiger is bulky and its centre would have to clear
^fn1
about 4.3 metres to get cleanly over the wall because Siberian tigers are about 1 metre high at the shoulder. (We will neglect the possibility that it clings on and scrambles over the wall – always likely though.) This gives V
²
= 9.8(4.3 + √(18.5 + 100)) = 148.97 (m/s)
²
, so V is 12.2 m/s.

This is within the launch-speed capability of a tiger, and so it could indeed have cleared the wall. Raise the wall to 5.5 metres so the tiger needs to raise its centre by 6 metres to clear the wall and the tiger needs to launch at 13.2 metres per second to clear the wall. As the Director said, ‘Obviously now that something’s happened, we’re going to be revisiting the actual height.’

^fn1
In these problems the projectile is taken to be a mass of negligible size located at its centre (a so-called ‘point’ mass). Of course, a tiger has a very significant size and is in no sense a point. However, we shall neglect this and treat the tiger as if it had its whole mass located at its centre.

75

How the Leopard Got His Spots

Then the Ethiopian put his five fingers close together . . . and pressed them all over the Leopard, and wherever the five fingers touched they left five little black marks, all close together . . . Sometimes the fingers slipped and the marks got a little blurred; but if you look closely at any Leopard now you will see that there are always five spots – off five black fingertips.

Rudyard Kipling, ‘How the Leopard Got His Spots’

Animal markings, particularly on big cats, are some of the most spectacular things we see in the living world. These patterns are by no means random, nor are they determined solely by the need for camouflage. The activators and inhibitors that encourage or block the presence of particular pigments flow through the embryonic animal in accord with a simple law that dictates how their concentrations at different points depend on the amount of production of that pigment by chemical reactions and the rate at which it spreads through the skin. The result is a wavelike spread of signals, which will activate or suppress different colour pigments. The resulting effects depend on several things, like the size and shape of the animal and the wavelength of the pattern waves. If you were to look at a large area of skin surface, then the peaks
and
troughs of these waves would create a regular network of hills and valleys of different colours. The appearance of a peak occurs at the expense of the inhibiting tendency, and so you get a pronounced stripe or spot against a contrasting background. If there is a maximum concentration that is possible in a particular place, then the build-up of concentration will eventually have to spread out, and spots will merge, turning into patches or stripes.

The size of the animal is important. A very small animal will not have room for many ups and downs of the pigment-activating wave to fit along and around its body, so it will be one colour, or perhaps manage to be piebald like a hamster. When the animal is huge, like an elephant, the number of ups and downs of the waves is so enormous that the overall effect is monochrome. In between the big and the small, there is much more scope for variety, both from one animal to the next and over an animal’s body. A cheetah, for example, has a spotty body but a stripy tail. The waves create separate peaks and troughs as they spread around the large and roughly cylindrical body of the cheetah, but when they spread to the thin cylindrical tail they were much closer together and merged to create the appearance of stripes. This tendency gives a very interesting mathematical ‘theorem’ that follows from the behaviour of the colour concentration waves on animals bodies: animals with spots can have striped tails but striped animals cannot have spotted tails.

76

The Madness of Crowds

The future belongs to crowds.

Don Delillo,
Mao II

If you have ever been in a huge crowd, at a sports event, a pop concert or a demonstration, then you may have experienced or witnessed some of the strange features of people’s collective behaviour. The crowd is not being organised as a whole. Everyone responds to what is going on next to them, but nonetheless the crowd can suddenly change its behaviour over a large area, with disastrous results. A gentle plodding procession can turn into a panic-stricken crush with people trying to move in all directions. Understanding these dynamics is important. If a fire breaks out or an explosion occurs near a large crowd, how will people behave? What sort of escape routes and general exits should be planned in large stadiums? How should religious pilgrimages of millions of worshippers to Mecca be organised so as to avoid repeating the deaths of hundreds of pilgrims that have occurred in the past, as panic generates a human stampede in response to overcrowding?