1. If the village I and village j (i
W (I, j) as the sum of the distance to the nearest station them clearly w (I, j)=0, if j - I=1.
2. Set S (I, k) for the former village I set in the k station and the first k set under the condition of the ith village, I before a village the minimum value of the sum of the distances to the nearest station,
S (I, k)=min {S (I - 1, k - 1) + w (I - 1, I), S (I - 2 k - 1) + w (I - 2, I),... , S (k - 1 k - 1) + w (k - 1, I)} the if (i> K> 1)
S (I, k)=0 if (i<=k)
S (I, 1)=?
3. Additional n + 1 village and cn + 1 & gt; 2 cn, then the whole problem of the optimal solution for S (n + 1, m + 1),
()
Based on the above ideas, write complete recursive equations,
And solving:,3,7,9,13,23,28,38,40,56,62,65 {0} the best results, set in the 5 station
Analysis of time complexity, thinking about how to optimize the calculation of w (I, j),
CodePudding user response:
Directly on the K - means algorithm