Differences

This shows you the differences between two versions of the page.

--- courses:cs211:winter2014:journals:alyssa:chapter_6.3 [2014/03/25 20:48] – created hardnetta
+++ courses:cs211:winter2014:journals:alyssa:chapter_6.3 [2014/03/25 23:51] (current) – hardnetta
@@ Line 1: / Line 1: @@
 ====== Chapter 6.3: Segmented Least Squares ======
+In previous problems, we've developed recurrence relations based on a binary choice, either //n// belonged to the optimal solution or it didn't. This problem, however, involves **multiway** choices; i.e. at each step, we have a polynomial number of possibilities to consider for the structure of the optimal solution.
+A good example problem is one where we try to find the line(s) of best fit for a set of points. We are given a set of points //P={(x_1,y_1), (x_2,y_2),..., (x_n,y_n)}// with //x_1<x_2<...<x_n//. We will use //p_i// to denote the point //(x_i,y_i)//. We must first partition //P// into some number of segments. The penalty of a partition is the sum of the following terms:
+  - The number of segments into which we partition //P//, times a fixed, given multiplier //C>0//
+  - For each segment, the error value of the optimal line through that segment
+Our goal is to find a partition of minimum penalty.
+===== Algorithm =====
+In this problem, it is important to remember that the last point //p_n// belongs to a single segment in the optimal partition, and that segment begins at some earlier point //p_i//. Knowing that the last segment is //p_i,...,p_n//, we can remove those points from consideration and solve the problem on the remaining points //p_1,...p_i-1//. So the algorithm looks like this:
+Segmented-Least-Squares(n):
+  * M[0...n]
+  * M[0]=0
+  * For all pairs i < = j:
+  * compute the error e_i,j for the segment p_i,...,p_j
+(end for)
+  * For j=1,2,...,n:
+  * compute M[j]=min(e_i,j+C+OPT(i-1)) for 1 < = i < = j
+  * return M[n]
+Find-Segments(j):
+  * if j=0 then return nothing
+  * else:
+  * find an i that minimizes e_i,j+C+M[i-1]
+  * return the segment {p_i,...,p_j} and the result of Find-Segments(i-1)
+Computing all e_i,j values is O(n^3) running time, and the remaining problem runs in O(n^2) time.
+I would rate this section a 7. I understood it, but I feel like they could have done a better job setting up the problem. I think the motivation for the problem was explained better in class than in this section.