Differences
This shows you the differences between two versions of the page.
| Both sides previous revisionPrevious revision | |||
| courses:cs211:winter2018:journals:cohene:home:chapter6 [2018/03/25 23:09] – [6.2: Principles of Dynamic Programming: Memoization or Iteration over Subproblems] cohene | courses:cs211:winter2018:journals:cohene:home:chapter6 [2018/03/26 03:03] (current) – [6.3: Segmented Least Squares: Multi-way Choices] cohene | ||
|---|---|---|---|
| Line 19: | Line 19: | ||
| ===== 6.3: Segmented Least Squares: Multi-way Choices===== | ===== 6.3: Segmented Least Squares: Multi-way Choices===== | ||
| + | The previous problems addressed in this chapter addressed recurrences based on binary choices. It is also possible to use recurrence with multi-way choices to find an optimal solution. The problem is similar to finding the line of best fit on a two dimensional set of axes. Our goal is to find the line with minimum error. A thought to the solution to this problem is to pass a set of lines through the points to minimize the error. This creates another issue, however, as this is not good problem formation. We could also try using brute force to find it, but this is also expensive. | ||
| + | This problem is known as the Segmented Least Squares Problem. It is the backbone of change detection, given certain data points, we want to find the points where a change occurs. For the Segmented Least Squares Problem, we can create segments of points and add a penalty to each partition by using a fixed multiplier and the error calculation. | ||
| + | To do so, we want to find a polynomial number of subproblems by partitioning n objects. We can use this to derive an algorithm. This algorithm would run in O(n^3) time. | ||
