Using Dynamic Programming in Word Processing:
High-end desktop publishing systems now arrange entire
paragraphs at a time, using dynamic programming to break the
paragraph into lines in such a way that various critiera
are optimized. Often there are "penalties" for certain
features, such as too much or too little space between
words, hypheating a word, and others. By experimentation,
I constructed the example below, where in the 9th line
"(M)" is changed to "(MMM)" (neither of which belongs in the
quotation). Ordinary low-tech word processors use a greedy
strategy to arrange each line as it is needed and never
adjust earlier lines to get some improvement. But below
a small change in the 9th lines causes changes in lines
3-8. The later lines are also affected, but we would expect that.
Notice that each blue portion
on the left is moved down a line to become the
orange
portion on the right.
Revision date:2012-11-04.
(Please use ISO
8601, the International Standard.)
