2

まずは1Dの場合。N 個の数値の配列が与えられた場合、それを n 個のチャンクに分割して、チャンク平均に対する各要素の距離の 2 乗の合計が最小になるようにします。たとえば、[0.1,0.3,2,1.2,1.3] を 3 つに分割するように求められた場合、最適解は [[0.1,0.3],[2],[1.2,1.3]] です。

動的計画法を使用すると、これは O(N * n) で簡単に解決できます。

次に 2D ケースです。(N,M) 行列が与えられ、それを n*m チャンクに分割したいと考えています。ソリューションは、不規則な間隔のグリッドのように見える必要があります。これは、n 個の水平カットと m 個の垂直カットのセットです。

これはよりトリッキーに思えます。水平方向のカットを固定することで最適な垂直方向のカットを動的に見つけることができますが、それはどこにも通じないようです。可能なすべての水平カット O(C(M,m)) を列挙するのは扱いにくいです。

多項式時間でこれを行う方法はありますか?

4

1 に答える 1

0

これは NP-Hard 問題によく似ているように思えます: http://en.wikipedia.org/wiki/K-means_clusteringなので、多項式時間アルゴリズムは存在しないと思います。

于 2013-02-09T02:12:32.083 に答える