Thank you very much for your detailed comments and very interesting project.

Yes, the site I visited was as you discuss, a medium sized building which cost $300 million to build, very expensive. Apparently using heavy particles (actually not just a proton but a whole carbon atom I believe) works well for deep targets but you know all this. It was very interesting though it was wierd to see even small children following the route which requires you to climb over and under the beam tube. Though the staff did not appreciate my asking (quietly to the side) if you would die from lethal x-ray dose etc. if you are in the donut shaped corridor holding the beam when it is turned on.. apparently it is accelerated to 80% of the speed of light.

About the dose entering from the side it does seem (superficially to me sorry and I know nothing of course of diffraction in the body but..) there would be a shadow from bones or at least more radiation absorbed on the side of the body the radiation comes from? That is, I thought it is absorbed within a foot of the surface. Oh well sorry to bug you with silly questions, the packing and pyramid shaping ideas are quite interesting!

I have not used it in large problems but just for fun there is Damian Conway's module series Quantum::Superpositions which provides the "any" and "all" words. It seems that some problems can be more easily stated in those terms, but really the best seems to me to try and make lots of blocks by hand and then translate some of the procedures you develop as you go along into bits of the program. Also possibly dynamic programming (blokhead mentioned this above it seems..) such as that used to find alignments of genetic sequences, where you solve many sub-problems first based on a set of scoring rules, then find a path through the solutions, to find the most efficient solution.

The above approach is different from the way I was thinking about it, but the part I should stress is that depending on the scoring rules you create, a dynamic programming approach can create different outcomes as to what is the most efficient. Obviously, you might think, but it can be subtle. For example there is the Smith-Watermann method in genomics. You can end up with more sensitivity, or more preference for a certain type of solution, depending on whether you want to penalize certain kinds of mutations, gaps, or end features. In these cases it seems best to experiment with variations, and also consider statistical/practical issues (for example statistically where beam is coming from or what shapes are more dangerous, or what shapes are easier to build).

If you are aligning two genetic sequences with dynamic programming, you end up drawing a matrix with one sequence (of letters A,T,G or C) for each axis. You start in the upper left corner and go right, then go to the next line when done. Basically you use the scoring rules to decide what score to write into a given cell, based on its coordinates and the contents of nearby (i.e. the previous) cell. When done filling in the whole matrix, you then go to the lower right hand corner and using another rule basically draw arrows towards the upper left corner, seeking the highest scoring valid cell. Basically this is supposed to give you the best sequence alignment and can be done by hand. So dynamic programming would suggest a similar kind of a procedure for your problem.

Also it appears to me that we really want to solve this for the whole length of the body, in other words not just a single pyramid but a number of pyramids running from feet to head. So continuity will be important as a way to reduce cost (well unless you have only short pieces available) and to reduce seams. However it will become more computationally complex to solve for the whole body, and very hard to test a solution by eyeball to see if it makes sense. I wonder if I understand this correctly. If so, the seam between two pyramid units should be considered as a penalty and you have to have a piece that bridges the two.

My own guess is that I would penalize cases in which vertical seams are created at all (since a single piece makes it easier to manufacture), and highly penalize a double seam (since a lot of radiation could leak through to sensitive tissue), if I am interpreting the pyramid to mean the beam is coming from the top of the pyramid, i.e. the base of the pyramid is actually against the patient's body, sideways, with the beam coming horizontally into the body from the top of the pyramid in through the base of the pyramid and then into the patient. In which case a vertical seam is bad, which is why you want to stagger or "build up" the pyramid like bricks.

In this case the drawing tilly provided might not be selected, depending on the rules, because it has lots of vertical seams, both dangerous radiation wise as well as perhaps using too many strips (we are ignoring how many thick pieces you have available).

Also you need to penalize or disallow solutions that are impossible to build (if they are?) such as a pyramid with a hole in it. To me it seems that you should be inputting not the widths and thicknesses of metal pieces, but the desired beam density at each coordinate, and a way to determine the beam density you get from a given solution, if that is what you are trying to determine.

Anyway, the most important thing to do is to determine how to score potential solutions.

Anyway, if you need something to get the juices flowing, here are some pages to look at: algorithm design and Design Patterns in Dynamic Programming. I just googled for "how to" and "dynamic programming" but also noticed that there are lots of kinds of "heuristic programming" methods. Also dynamic programming can take a long time for large data sets, maybe this is not a problem of yours.

Finally, and this is not really my field, but there is a whole field of bin packing, set covering and partioning problems. One famous problem is the "knapsack problem". There are different algorithms that go by names like linear programming, simulated annealing, continuous relaxation and others. I'm not qualified to give you an overview of this sort of thing and my guess is that you don't have enough data to be worrying so much about the search algorithm, you should pay most attention to the definition of the problem.

By the way I did find (google for radiation and "dynamic programming") a reference to computation of radiation doses PDF and as HTML from google. These people talk about something like what I hypothesized, using the CT scan to compute doses, but say it is too big a problem computationally and so use a heuristic called a Markov decision problem, or MDP. Anyway, google says that variants of dynamic programming are indeed used widely for radiation planning over time, though this is possibly a different problem from yours.

Hope this thread helps you in working out this problem.