From: ram@zedat.fu-berlin.de   
      
     To wrap a paragraph, I wrote a Python script that searched for   
     the best wrap, given a quality function that included penalties   
     for interpunction near the end of a line (but not at the end)   
     or adjacent lines that differed greatly in length.   
      
     It worked, but as the number of lines approached ten, it became   
     painfully slow.   
      
     By an incredible twist of fate, I came across a chapter of   
     a book that explained dynamic programming and how to use it   
     to reduce the complexity of global paragraph wrapping from   
     exponential to quadratic!   
      
     So I modified my script yesterday, and today all the paragraphs   
     you read here are wrapped by the new script, because I configured   
     my editor to run paragraphs through this script whenever I press   
     a certain sequence of keys.   
      
     So how does this work?   
      
     An exponential paragraph wrapping algorithm tries every   
     combination of break points and gets a quality score for each.   
     I think my first program must have looked like this. I may have   
     eliminated some obviously bad line breaks, but basically it   
     must have been an exponential algorithm.   
      
     The dynamic programming algorithm, as I understand it, works like   
     this and can still find the global optimum: I have a loop that   
     goes through each possible break point just once (which would be   
     linear). Then this loop has an inner loop that goes through each   
     previous breakpoint (now it's quadratic). The previous breakpoints   
     have already been evaluated. So it can easily find the best   
     combination of a previous breakpoint and a possible break at the   
     current position. This is the quality score for a break at the   
     current position. Finally, you start at the break point just after   
     the last word of the paragraph and go from there to all the best   
     preceding break points to identify the lines of the result.   
      
     However, it seems to me that I am a bit limited in the quality   
     measure function, because this function seems to support best   
     quality measures that only consider the current line and maybe the   
     combination of the current line with the preceding line. The global   
     quality measure function I had before could also easily measure   
     such global quantities as the standard deviation of the lengths of   
     all the lines of the result. This is not accessible to the dynamic   
     programming algorithm as I understand it, because when it is in the   
     middle of the paragraph, it does not yet know the lengths of all   
     the lines, and when it is at the end of the paragraph, it cannot   
     change decisions that have already been made.   
      
     The same book also gave another problem that could supposedly be   
     solved using dynamic programming: In a restaurant you are shown   
     five dishes in a sequence, and you can choose one to eat. You are   
     shown only one dish at a time and do not know which dish will be   
     shown next. Once you accept or reject a dish, you cannot go back on   
     your decision. If you do not choose any of the first four dishes,   
     this means that you would inevitably eat the last one. How should   
     you proceed to maximize the probability of getting the best dish?   
      
     The solution given in the book begins by explaining that you   
     assign a quality score between 0 and 1 to each dish you see.   
     So the question is how to proceed to maximize the probability   
     of eating a dish with a quality score as high as possible . . .   
      
   --- SoupGate-Win32 v1.05   
    * Origin: you cannot sedate... all the things you hate (1:229/2)