algorithm - Use dynamic programming to find a polygonal chain that best fits a set of data points -


The question is said as the following:

Looking at the sequence of digits p_1 = ( x_1, y_1), ..., p_n = (x_n, y_n) and by it the x-coordinate (i.e. x_1 & lt; x_2 & lt; ... & lt; x_n) from left to right and 1 and n Between a number q we want that P1 to PN With the K-edges from the PN, which goes from left to right, want to reduce the sum of the vertical distance of the series points . O (n ^ 3) Design a dynamic programming algorithm to solve the problem in time. The method to calculate the sum of the vertical distance of p_a + 1 points. . , p_ap_b for line through p_b_ 1 is given by F (A, B).

Enter image details here

Because of testing for me It is difficult to write an example, so I do not know if my answer is correct or not.

The answer is as follows:

First of all, I define polygon chain interval on the PE of [i, j] = PI, the minimum sum of the vertical distance. And the answer should be C [N, K].

For the base case, I define c [i, 0] = 0 and c [i, j] = + infinity when j & gt; = I.

For the recursive formula, I see C [i, j] = minimum (1

l; i) {c, p, j-1] + f (p, i)} < / P>

Is anything wrong in my answer? Thank you.

example where the point is better to use P for a series ( set of p_i ). 

  P = {(0, 0), (1, 1), (3, 1), (4, 0)} k = 2 + (2,2) * (1, 1) * (3,1) * (0,0) * (4,0)   
 2 Points for a series with numbers in  P  Both have  f (1,4) = 2/3 .  (2, 2)  returns the series point as  f (1,4) = 0 .  
 The solution to the problem without any restriction,  P , is difficult to describe in a DP manner. It looks like a problem of regression with many obstacles.  
 I think that in this problem, it is expected to be from  P  for series points.  
  Update   
 is similar to the Lower Records original, such as j_random_hacker has been mentioned.  
 I think it's better to define a slightly different function. Define the minimum cost of the chain between  p_a  and  p_b  with the  e  edges  C (A, B, E) . The answer to our problem is  C (1, n, k) .  
  c (a, b, 1) = f (a, b) c (a, a + i, i) = 0 c (a, b, k) = inf, k & Gt; B-A   
 There are different recomputations that can be used. This is the 'length' of the last edge:  
  c (a, b, k + 1) = minutes (c (a, c, k) + c (i, b, 1) ), I for a + k, b-1

Comments

Post a Comment

Popular posts from this blog

Verilog Error: output or inout port "Q" must be connected to a structural net expression -

I get the error every time, I try to compile. I'm not sure why anyone can help is? I'm new to verilog. Module D_FF (clerk, d, reset_n, q); Input D, Clack, reset_en; Output Q; reg Q; lab4_gdl f1 (.lk (~ clk), d (d), .q.m (qm)); lab4_GDL f2 (.Clk (Clk), D (QM), .Q (Q)); Always start at @ (posedge clk, neggeous reset_n) (Reset_n == 0) Q & lt; = 0; Other questions & lt; = D; Edit End: The problem is what we are asking to do: In this section, you apply the memory / registration circuit on the AlterEdie 2 board. will do. The circuit has the following specifications: The present value of swift SW15-0 on the D2 board should be shown in four hexadecimal four sections of HEX3-0. This part of the circuit will be combination logic. To use an active-less asynchronous reset and KEY1 to use KEY0 as the clock input, you must store SW15-0in in a 16-bit register in the value The register should be enabled to have a 16-bit positive edge, which uses the embedded D flip-flo...
Read more

Installing croogo for cakephp -

I'm new to the keyboard, I want to install Crogo in KKPP 2.3. My question: The way to extract the file is: - Changing cakephp2.3 / app / plugging / folder in app (do not work. Error admin controller not found) or - CakePP-2.3.3 / app / (Not working ). Sorry for my bad english language: (please help me and thank you.) crogo a cms by kcfp has been developed ... meaning kkfp is already there .. just Croogo Download and read their documentation ... and try Google about some CMS ...
Read more

c# - ASP.NET MVC - Attaching an entity of type 'MODELNAME' failed because another entity of the same type already has the same primary key value -

In brief, the wrapper module is inserted during posting and the status of an entry is changed to 'modified' . Before changing the state, the state is set to 'separate', but calling attachments () causes the same error to be thrown away. I am using EF 6. Model / wrapper class public class avi model {public A is a {get; Set; } Public listing & lt; B & gt; B {received; Set; } Public cc {receipt; Set; }} Administrator edit public functioning (int? id) {if (id == null) {new HttpStatusCodeResult (HttpStatusCode.BadRequest); } If (! Conveyor Access (id.Value)) new HTTPTitus code result (HTTP status code. Forbidden); Var aViewModel = new AViewModel (); aViewModel.A = db.As.Find (id); If (aViewModel.Receipt == zero) {return HttpNotFound (); } aViewModel.b = db.Bs.Where (x => x.aid == id.Value) .Oolist (); AViewModel.Vendor = db.Cs.Where (x => x.cid == aViewModel.a.cID) .FirstOrDefault (); See Return (aViewModel); } [HTPFost] [Valid AntitiferousTeacon...
Read more