划分二维数组作为平等-AS-可能的和连续的区域？ [英] Divide 2D array into continuous regions of as-equal-as-possible sums?

问题描述

予有浮点数的2D阵列，我想要分化这个阵列成多个区域的任意数量的，使得所有的区域'元素的总和都或多或少相等。区域必须是连续的。通过如-相等如-可能，我的意思是区域和的标准偏差应减少尽可能

我这样做，因为我有对应于一个地区的居民的价值观的地图，我想这个划分区域划分为相对平等的人口群体。

谢谢！

解决方案

标准偏差的方法来衡量该部门是否接近相等。较低的标准差表示更接近的款项。

由于这个问题似乎NP喜欢聚集的问题， 可以用遗传算法得到良好的解决方案的问题： -

  

  
1. 标准偏差可以作为健身度量染色体。
  
2. 假设有k个传染地区那么每个基因（元件）将有k个值保持其中的区域的传染性性质之一。
  
3. 在应用遗传算法的染色体，并得到了k的该值的最佳染色体代固定金额后。
  
4. 变化ķ从2到n，并运用遗传算法得到最好的染色体。
  

I have a 2D array of floating-point numbers, and I'd like to divide this array into an arbitrary number of regions such that the sum of all the regions' elements are more or less equal. The regions must be continuous. By as-equal-as-possible, I mean that the standard deviation of the region sums should be reduced as much as possible.

I'm doing this because I have a map of values corresponding to the "population" in an area, and I want to divide this area into groups of relatively equal population.

Thanks!

解决方案

Standard deviation is way to measure that whether the divisions are close to equal. Lower standard deviation means closer the sums are.

As the problem seems n-p like clustering problems , Genetic algorithms can be used to get good solutions to the problem :-

1. Standard deviation can be used as fitness measure for chromosomes.
2. Consider k contagious regions then each gene(element) will have one of the k values which maintain the contagious nature of the regions.
3. apply genetic algorithm on the chromosomes and get the best chromosome for that value of k after a fixed amount of generations.
4. vary k from 2 to n and get best chromosome by applying genetic algorithms.

这篇关于划分二维数组作为平等-AS-可能的和连续的区域？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！