On Fri, Jan 18, 2008 at 12:09:14AM +0100, Andreas L Delmelle wrote:
> I have always somehow assumed there to be a threshold in the most common 
> cases. In the sense that certain (maybe in fact even the bulk of) feasible 
> breaks can already be excluded quite early, even if the sequence consists 
> of millions of elements. Simply because they would, in intermittent runs, 
> repeatedly be considered to be 'bad' breaks, or because they become 'worse' 
> than the previous run.
> Something like this happens already, in a way, I think, albeit very deeply 
> embedded inside the algorithm, and a bit late too...
> Once we start determining actual breaks, the further we progress in the 
> page-sequence, the more layout-possibilities that need to be excluded. We 
> simply cannot consider all of them, including the ones that would lead to 
> unreasonable results.

Study the book, Andreas. Donald Knuth has treated all this, in a
manner that is quite complete. As Vincent said, this is the principle
of dynamic programming.

Earlier feasible pagebreaks are kept 'alive' because later feasible
pagebreaks keep a chain of references to them. Early feasible
pagebreaks that are not part of a 'best' chain of pagebreaks up to one
of the active nodes, are not referenced anymore and therefore
disappear from memory.


Simon Pepping
home page: http://www.leverkruid.eu

Reply via email to