StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>The basic premise of dynamic programming is to optimize (lower the 'cost' or in this case, error) of a problem recursively while storing the cost of subproblems as you go so they are not recomputed (this is called memoization).</p> <p>It's a little late so I'm not gonna get too detailed, but it seems the part you have the most problem with is the core DP itself. DP is needed here because of the 'segmeneted' quality. As your PDF shows, finding the best-fit line by least squares is simple and does not require DP.</p> <blockquote> <p>Opt(n) - e(i, n) + C + Opt(i-1) --- our cost function where<br> C is the constant cost of a new line segment (without which the problem is trivial and we would just make new line segments for every two points)<br> e(i, n) is the error of the points i to n with ONE segment (not recursive)<br> Opt(i-1) is the least cost recursively from the first point to the (i-1)th</p> </blockquote> <p>Now the algorithm</p> <blockquote> <p>Ensure the list of points is sorted by x values<br> M[0] = 0 --- self explanatory<br> For all pairs (i, j) with i < j: find e(i,j) ---- (this will require nested for/foreach loops, or a comprehension kind of structure. Store these values in 2D array!)<br> For (j=1..n): M[j] = min([Opt(j) for i in range(1,j)]</p> </blockquote> <p>So basically, find the one-line cost between any two possibly points, store in e<br> Find the least cost up to j, for j between 1 and n. Values along the way will help with later computation, so store them! Note that i is a parameter to Opt as well. M[n] is the total optimized cost.</p> <p>Question for you - How can you determine where segmentation occurs? How can you use this, and M, to detetermine the set of line segments once its all over? </p> <p>Hope this helps!</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload