This topic continues the theme of graphs or networks from the section on graph-colouring. In this case we are interested in placing ice cream vans at optimal places in a network so that they can serve the maximum number of people with the minimum number of vans. We could have chosen a large number of alternative items with a similar problem, for example post boxes, fire and ambulance stations, telephone junction boxes, and so on.
The problem here is to place ice cream vans at nodes or junctions in the graph so that all other nodes are no more than one step away. What is the smallest number of vans you can place on the graph? There are 26 nodes so one solution would be to use 26 vans but this would place vans just one edge apart and there would not be enough custom to sustain them all. You must look for a solution with far fewer vans than this.
Study the solution and note the cunning way that the problem has been constructed.
Now design your own maps and try them out on other members of the class. When you join nodes to hide your underlying sub-nodes do not join the solution intersections, join only the non-solution intersections.
Notice how easy it is to create a graph and how difficult it is to find a solution to it. A graph is an example of a one-way function, a function that is easy one way but hard the other way. We shall meet one-way functions again in cryptography.
Can you solve a problem like this by 'brute force', that is try every possible combination until you find the right one? Starting with one van there are 26 possible locations (nodes) on the second map, that's fairly obvious.
With 2 vans there are rather more combinations. With a van on any node there are 25 others for the second one to be on so there are 26 x 25 combinations (650; as it doesn't matter which van occupies a node you would only need to check half of the combinations (325).
With 3 vans there are 650 x 24 combinations (52,000) but five sixths of these can be ignored giving 2,600 real combinations to consider. (The three vans can occupy three nodes in six ways, 1-2-3, 1-3-2, 2-1-3, 2-3-1, 3-1-2 and 3-2-1, but we don't care which van is on which node so we can ignore 5 of these combinations.)
With 4 vans there are 14,950 combinations (why?), with 5 vans 65,780 and with 6 vans 230,230 combinations (which explains why it was so hard to find the solution by hand).
The maths here is quite interesting. To find the total combinations for the vans we multiply 26 x 25 and divide by 2 for 2 vans giving 325.
For 3 vans we multiply 26 x 25 x 24 as for any pair of vans there are 24 nodes for the third van to occupy. We divide 15,600 by 6 because the 3 vans can be arranged in 6 different ways and we don't care what way.
For 4 vans we multiply 26 x 25 x 24 x 23 to find the total combinations (358,800). We know that we can reject some of these but how many? What do we divide by? The answer is 14,950 so we divide by ?? Why this number?
The answer is the number of combinations of 4 vans on 4 nodes, which we could work out manually but there is a sequence here: 2, 6, ?? We know the sequence of divisors so far and the next one follows in the same sequence but what is the sequence and what is the next number?
Hint: the divisor for 3 vans was derived from the numbers 1, 2 and 3 (how do you get 6 from these?) The divisor for 4 vans was derived from 1, 2 ,3 and 4 (what is the divisor? Try 358,800/14950: how can you get this number more easily than writing out the combinations in full?)
The solution for the smallest number of vans (known as the 'dominating set') is 230,230 combinations, which is rather too many to check by hand!
Pascal's triangle can be used to find combinations such as 'how many ways to draw 3 cards from 52 in a deck?' or 'how many ways to choose 2 hats from 5?' or 'how many ways can you draw 6 numbered balls from 49?'.
To solve the first of these we look in row 52 and at the 3rd number along, which happens, if you draw out the triangle, to be 22,100. (numbering starts at 0, or simply ignore the 1s and start numbering at 1.)
The answer to the second problem is 10 and the answer to the third (your chance of getting 6 numbers out of 49) is 13,983,816.
Likewise for the vans, with 26 vans and one choice the number of choices is 26. For two vans the number is in the 26th row and 2 numbers along is 325. For 3 vans we go 3 numbers along row 26 where we find 2600 and so on. For 6 vans Pascal's triangle shows 230,230.
So we have found a quick way to find the permutations and we have also shown how Pascal triangle numbers are calculated:
for a given n choose m do n x n-1.. n-m and divide by n!.
e.g. 6 vans on 26 nodes: 26 x 25 x 24 x 23 x 22 x 21 / 6! = 165,765,600 / 720 = 230,230.
With so many possible combinations of vans and nodes to consider we will either get lucky and find the right one by chance or we are unlikely ever to find it. In the real world the ice cream vans would find a reasonable sub-optimal solution and not worry about the optimal one. In the real world the optimal solution would be influenced by other factors such as the length of the edges (this is ignored in the graph), waiting restrictions on the roads and the number and type of people who live and move along the streets - their age, whether they have ice cream at home, whether there are shops nearby, and so on.
Still, we are unlikely to find a solution by brute force to a problem of this scale unless we use a computer. Computers are very good at carrying out identical tasks millions of times and finding the desired solution. Computers have doubled in speed roughly every 18 months for 30-40 years so they have got better and better at solving problems like this. This leads us to throw bigger and bigger problems at them...
Actually, finding the correct solution involves considerably more calculations than we have shown so far. For any combination we need to check the distance of the nearest van from each node as no node should be more than one edge from a van.
Each node may or may not have a van. For a network of 3 nodes there are 8 possible combinations of vans: none-none-none, 1-none-none, 1-2-none, 1-none-3, 1-2-3, none-2-none, none-2-3, none-none-3. For a network of 4 nodes there are 16 combinations (24) and for 26 nodes there are 226 = 67,108,864 combinations (which again explains why it was so hard to find a solution earlier). This is quite a large number of combinations to check and this is quite a small network...
For a practical solution an ice cream salesman would park outside a popular place and pay the local traffic wardens not to move him away from the double yellow line... (You might have thought all this talk about ice cream was light-hearted but in Scotland they had an ice cream war...)
This is particularly sensible because no one actually knows whether there exists a method that is better than brute force at finding a minimum set of locations. The number of combinations of locations for vans grows exponentially with the number of nodes in the graph. With 3 nodes there are 23 combinations of vans, with 26 there are 226 and with 100 there are 2100, which is a seriously large number. This is called an exponential-time algorithm as the amount of time required to solve the problem grows exponentially with the number of nodes or intersections.
A polynomial-time algorithm is one that grows with the square, cube or nth power of the number of nodes on the graph, for example 262 or 265. A polynomial-time algorithm should be faster for larger graphs as the number of combinations will be less beyond a certain point.
With three nodes there are 2n combinations (23 = 8) for an exponential algorithm but n2 solutions (32 = 9) for a polynomial algorithm. For 4 nodes the number of combinations is the same (24, 42) but beyond that point the polynomial equation produces fewer combinations than the exponential one (25=32, 52=25, and so on). For any value of n there will always be a point where the polynomial equation produces fewer combinations than the exponential - you can explore this in a spreadsheet.
Where n=2 the polynomial produces a smaller result very quickly:
| Nodes | Polynomial: nodes ^ n | Exponential: n ^ nodes | |
| n=2 | n=2 | ||
| 1 | 1 | 2 | |
| 2 | 4 | 4 | |
| 3 | 9 | 8 | |
| 4 | 16 | 16 | |
| 5 | 25 | 32 | |
| 6 | 36 | 64 | |
| 7 | 49 | 128 | |
| 8 | 64 | 256 |
Where n=10 it takes a little longer for the exponential function to catch up:
| Nodes | Polynomial: nodes ^ n | Exponential: n ^ nodes | |
| n=10 | n=10 | ||
| 1 | 1 | 10 | |
| 2 | 1,024 | 100 | |
| 3 | 59,049 | 1000 | |
| 4 | 1,048,576 | 10,000 | |
| 5 | 9,765,625 | 100,000 | |
| 6 | 60,466,176 | 1,000,000 | |
| 7 | 282,475,249 | 10,000,000 | |
| 8 | 1,073,741,824 | 100,000,000 | |
| 9 | 3,486,784,401 | 1,000,000,000 | |
| 10 | 10,000,000,000 | 10,000,000,000 | |
| 11 | 2.59374E+10 | 1E+11 | |
| 12 | 6.19174E+10 | 1E+12 |
And so on: the exponential function eventually produces bigger results than the polynomial.
However, as said earlier, it is not known whether there is a polynomial-time solution for graph-colouring problems like the map-colouring problem, the school timetable, scheduling problems and the ice cream van problem. If a polynomial-time solution could be found to any one of these problems, or thousands like them, then, because they are fundamentally similar, that solution could be applied to all of them. As no such solution has yet been found we continue to rely on brute force, intuition, good luck or a sub-optimal solution.
These problems are called NP-complete (NP=non-deterministic polynomial). This means that a problem could be solved in a reasonable amount of time if there was a computer that could try out an arbitrarily large amount of solutions at once. This would require an arbitrarily large computer so there is no prospect of a solution as such a thing does not exist (yet!). The set of problems is complete because a solution to one could be applied to the solution of any. There is a strong suspicion that there is no solution apart from a brute-force exponential one but no one has so far proved this.
Click Back to return