64 prisoners are housed in a super-max prison, with 100 rows of 100 cells on 100 floors. Each prisoner chooses six friends at random. He would prefer for his friends to be in the cells left, right, above, below, and forward and back of him. Provide an algorithm for placing prisoners in cells, which minimizes the average squared distance between a prisoner and each of his friends.

I wanted to clarify what it means for prisoners to be friends in your problem. Can one prisoner be friends only with 6 people that he chose (so each of those 6 chose him too) or he can be chosen by other prisoners too? In other word, how many edges go out of a vertex in that graph?

Friendships are mutual, but not predictive. In other words if A is friends with B and C, B and C are particularly likely to be friends.I guess a more interesting case would be to discover the predictiveness, and use it to optimize the algorithm. But the algorithm which works best in the random case...

Well, it hard because it is a discret optimisatio problem. One non-optimal algorithm would be to put all the prisoner on random cells. Then iteratively, you try to move one of them to et more point till you are on an optimal position. The problem is, you have a problem where i think there can be a lot of solution. I must think there can be maybe a big algebra lest square system that could help, but the problem is the cost matrix is function f the variable.BT, the algorithm I gave is (number of iterations) *O(number of cell) * O(number of prisoners). However, the number of iteration can be i am afraid quite big..

QuoteOriginally posted by: OmkThen iteratively, you try to move one of them to et more point till you are on an optimal position... BT, the algorithm I gave is (number of iterations) *O(number of cell) * O(number of prisoners). However, the number of iteration can be i am afraid quite bigDon't be afraid. I think the problem is that the rearrangement of whole groups may be necessary to find an improved layout, where you would not see any gradual improvement as you performed the rearrangement one-by-one. So how can you find groups to move as a whole? The solution, it seems, is to first find the solution with a smaller number of slots, say four quadrants, in each of which all prisoners are at a single point. If you know the best possible case with prisoner N in quadrant 1 is X, then you know there is no possible sub-improvement inside there that could beat X. So if you get better than X in some other finer arrangement, then you know that no finer arrangement could beat that. In other words, instead of comparing two full-detail arrangements, you look for a summary that delivers a best case, and a worst case. If see you the worst case of summary A - which summarizes 1,000 possible arrangements - beats the best case of B which summarizes 1,000 possible arrangements, then you discard B, and look for the best sub-arrangement of A that is actually possible.But anyway, I am trying to show that the random case doesn't exist in nature, and that things naturally collapse to stable patterns which can best be described in smaller and smaller numbers of dimensions in continuous space. So hopefully I will always be faced with an easier or more interesting algorithm...

This is an ideal problem for simulated annealing. The prisoners problem is essentially one of finding the lowest-energy crystallization of the atoms=prisoners in the lattice=prison cells. Simulated annealing lets the atoms find energy minima by jostling the atoms at high temperatures (subject to r-squared forces that draw them toward low-energy states) and then gradually reducing the temperatures until the system "freezes" in a local (hopefully near-global) minima.

Indeed, several years ago there was fairly popular and effective software that used simulated annealing to minimize chip distance between directly connected chips (hence wiring, hence heat dissipation) on circuit boards. It was called "Timberwolf" or some similar marketing inspired name.

TimberWolf was a package for laying out cells on an IC developed at Berkeley by Carl Sechen. The cells could be quite basic (like an and gate) or bigger macro blocks (like a 16 bit adder). During placement the goal is to create solutions where the:- Total Chip area is minimized by reducing interconnect length; While clustering connected cells together seems obvious, the placement should not result in situations where too much of routing has to happen in the same space leading to congestion and area bloat.- The length of interconnects in paths which are critical to meet timing goals are minimized.One of Sechen's student at Yale, William Schwartz runs the site www.twolf.com where he sells updated versions of these tools.You might find these lines funny from their Pricing Page but it is not uncommon for the leading commercial tools to sell for 10-20x this price!InternetCAD's Total Lease Package $25,000* per lease copy (per year)How can we charge such a low price?

QuoteOriginally posted by: BayAreaFanWhile clustering connected cells together seems obvious, the placement should not result in situations where too much of routing has to happen in the same space leading to congestion and area bloat.Electrical fields and magnetic fields are the same thing, aren't they? And doesn't photo and radio energy get transmitted in quantized packets?And if so, isn't it wrongheaded for a simulation of molecular dynamics to use a piece of hardware built for packets, and use it to calculate the influence of fields on billiard balls over a continuous space?If actual forces propagate as quanta, which move objects by rearranging the web of space in their wake, and if quanta of space "anneal" themselves to be isomorphous with a static hardware configuration (i.e. three-dimensional), then shouldn't forces be simulated to propagate through the hardware structure in lossless packets, rather than being retransmitted instantaneously between n(n-1)/2 bodies back and forth as degrading summaries of their position?You need a lot more IC's in parallel to simulate quark-range quanta. But they are much simpler, and you don't need any math, since the laws of physics manifest out of the propgation rules. And all data is only stored in one place.So if you were going to simulate dense molecular dynamics over long trajectories, would you try to shoehorn the euclidian/newtonian billiard ball method into a discrete circuit? Or would you propagate forces as changes in the shape of quantized space as recorded in an isomorphous circuit?