長さ N の大きな配列があります。次のように言いましょう。
2 4 6 7 6 3 3 3 4 3 4 4 4 3 3 1
この配列を P 個の部分配列に分割する必要があります (この例でP=4は妥当です)。各部分配列の要素の合計がシグマにできるだけ近くなるように、次のようにします。
sigma=(sum of all elements in original array)/P
この例では、sigma=15.
わかりやすくするために、1 つの考えられる結果は次のようになります。
2 4 6 7 6 3 3 3 4 3 4 4 4 3 3 1
(sums: 12,19,14,15)
除算を手作業で行う方法に基づいた非常に単純なアルゴリズムを作成しましたが、合計が (14,14,14,14,19) である除算が 1 よりも悪いという条件を課す方法がわかりません。つまり (15,14,16,14,16) です。
前もって感謝します。
まず、考えられる解ごとに入力、出力、および測定値を指定して、最適化問題を形式化しましょう (これがあなたの興味に合うことを願っています)。
正の整数の配列Aと正の整数Pが与えられた場合、各部分配列の合計と部分配列の完全な合計 (sum( A )/ P ) の差が最小になるように、配列AをP個の重複しない部分配列に分割します。 .
入力:正の整数の配列A。Pは正の整数です。
出力: A の各部分配列の長さを表すP個の非負整数の配列SA 。これらの部分配列の長さの合計はAの長さと等しくなります。尺度: abs(sum( sa )-sum( A )/ P ) は、各sa ∈ { sa | sa = ( A i , …, A i +<em>SA j ) for i = (Σ SA
j )、0 からP -1 までのj }。
入力と出力は、有効なソリューションのセットを定義します。メジャーは、複数の有効なソリューションを比較するためのメジャーを定義します。また、完全解との差が最小となる解 (最小化問題) を探しているため、測度も最小にする必要があります。
この情報があれば、measure関数を実装するのは非常に簡単です (ここでは Python で):
def measure(a, sa):
sigma = sum(a)/len(sa)
diff = 0
i = 0
for j in xrange(0, len(sa)):
diff += abs(sum(a[i:i+sa[j]])-sigma)
i += sa[j]
return diff
print measure([2,4,6,7,6,3,3,3,4,3,4,4,4,3,3,1], [3,4,4,5]) # prints 8
現在、最適解を見つけるのは少し難しくなっています。
バックトラッキング アルゴリズムを使用して有効なソリューションを見つけ、メジャー関数を使用してそれらを評価できます。基本的に、すべての可能な有効な解を表すために、合計で length( A ) になるP個の非負の整数の可能な組み合わせをすべて試します。これにより、有効なソリューションを見逃すことはありませんが、基本的には力ずくのアプローチであり、最善のソリューションよりも優れているとは言えないいくつかのブランチを省略できるという利点があります。たとえば、上記の例では、すでに≤ 38のソリューションがある場合、[9,…] (メジャー> 38)でソリューションをテストする必要はありません。
ウィキペディアの擬似コード パターンに従うと、bt関数は次のようになります。
def bt(c):
global P, optimum, optimum_diff
if reject(P,c):
return
if accept(P,c):
print "%r with %d" % (c, measure(P,c))
if measure(P,c) < optimum_diff:
optimum = c
optimum_diff = measure(P,c)
return
s = first(P,c)
while s is not None:
bt(list(s))
s = next(P,s)
グローバル変数P、optimum、およびは、 A、P、およびsigmaの値と、最適解とその尺度をoptimum_diff保持する問題インスタンスを表します。
class MinimalSumOfSubArraySumsProblem:
def __init__(self, a, p):
self.a = a
self.p = p
self.sigma = sum(a)/p
次に、非常に単純なrejectandaccept関数を指定します。
def reject(P,c):
return optimum_diff < measure(P,c)
def accept(P,c):
return None not in c
これは、測定値がすでに最適なソリューションを超えている候補を単純に拒否します。そして、私たちは有効な解決策を受け入れています。
値を含めることができるようになったため、measure関数もわずかに変更されています。cNone
def measure(P, c):
diff = 0
i = 0
for j in xrange(0, P.p):
if c[j] is None:
break;
diff += abs(sum(P.a[i:i+c[j]])-P.sigma)
i += c[j]
return diff
残りの 2 つの機能はfirst、nextもう少し複雑です。
def first(P,c):
t = 0
is_complete = True
for i in xrange(0, len(c)):
if c[i] is None:
if i+1 < len(c):
c[i] = 0
else:
c[i] = len(P.a) - t
is_complete = False
break;
else:
t += c[i]
if is_complete:
return None
return c
def next(P,s):
t = 0
for i in xrange(0, len(s)):
t += s[i]
if i+1 >= len(s) or s[i+1] is None:
if t+1 > len(P.a):
return None
else:
s[i] += 1
return s
基本的に、リストの次の値がリストの最後の値でない場合はリストの次の値をfirst置き換えるか、リストの最後の値の場合は有効なソリューションを表す残りの値に置き換えます (ここでは少し最適化します)。リストに値がありません。単純に右端の整数を 1 だけインクリメントするか、インクリメントが合計制限に違反する場合は戻ります。None0NoneNonenextNone
bt問題のインスタンスを作成し、グローバル変数を初期化し、ルートで呼び出すだけです。
P = MinimalSumOfSubArraySumsProblem([2,4,6,7,6,3,3,3,4,3,4,4,4,3,3,1], 4)
optimum = None
optimum_diff = float("inf")
bt([None]*P.p)
ここで私が間違っていなければ、もう 1 つのアプローチは動的計画法です。
P [ pos , n ] は、 n 個のサブアレイが作成された場合に、位置posまで蓄積された最小の「ペナルティ」として定義できます。明らかに、そのようないくつかの位置 pos' があります。
P[pos', n-1] + ペナルティ(pos', pos) = P[pos, n]
pos' = 1..pos で最小化できます。
単純な実装は O(N^2 * M) で実行されます。ここで、N - 元の配列のサイズと M - 分割数です。
@Gumbo の答えは明確で実用的ですが、length(A) が 400 より大きく、P が 8 よりも大きい場合、多くの時間を消費します。
実際、非常に高速なソリューションは、動的計画法を使用することです。
正の整数の配列 A と正の整数 P が与えられた場合、各サブ配列の合計とサブ配列の完全な合計 (sum(A)/P) の差が最小になるように、配列 A を P 個の重複しないサブ配列に分割します。 .
測定:
、ここで、
は部分配列 の要素の合計
、
は P 部分配列の合計の平均です。
これは、標準偏差の定義を使用しているため、合計のバランスを確認できます。
配列 A には N 個の要素があると仮定します。Q(i,j)は、A の最後の i 要素を j サブ配列に分割したときの最小メジャー値を意味します。D(i,j)は(sum(B)-sum(A)/P)^2、配列 B が A ( 0<=i<=j<N) の i ~ j 番目の要素で構成される場合を意味します。
問題の最小の尺度は、Q(N,P) を計算することです。そして、次のことがわかります。
Q(N,P)=MIN{Q(N-1,P-1)+D(0,0); Q(N-2,P-1)+D(0,1); ...; Q(N-1,P-1)+D(0,N-P)}
ということで、動的計画法で解けるようになりました。
Q(i,1) = D(N-i,N-1)
Q(i,j) = MIN{ Q(i-1,j-1)+D(N-i,N-i);
Q(i-2,j-1)+D(N-i,N-i+1);
...;
Q(j-1,j-1)+D(N-i,N-j)}
したがって、アルゴリズムのステップは次のとおりです。
1. Cal j=1:
Q(1,1), Q(2,1)... Q(3,1)
2. Cal j=2:
Q(2,2) = MIN{Q(1,1)+D(N-2,N-2)};
Q(3,2) = MIN{Q(2,1)+D(N-3,N-3); Q(1,1)+D(N-3,N-2)}
Q(4,2) = MIN{Q(3,1)+D(N-4,N-4); Q(2,1)+D(N-4,N-3); Q(1,1)+D(N-4,N-2)}
... Cal j=...
P. Cal j=P:
Q(P,P), Q(P+1,P)...Q(N,P)
The final minimum Measure value is stored as Q(N,P)!
To trace each subarray's length, you can store the
MIN choice when calculate Q(i,j)=MIN{Q+D...}
D(i,j) のスペース。
Q(N,P)の計算時間
純粋なブルート フォーシング アルゴリズムと比較すると時間
がかかります。
以下の作業コード（私はphp言語を使用しました）。このコードは部品の数量自体を決定します。
$main = array(2,4,6,1,6,3,2,3,4,3,4,1,4,7,3,1,2,1,3,4,1,7,2,4,1,2,3,1,1,1,1,4,5,7,8,9,8,0);
$pa=0;
for($i=0;$i < count($main); $i++){
$p[]= $main[$i];
if(abs(15 - array_sum($p)) < abs(15 - (array_sum($p)+$main[$i+1])))
{
$pa=$pa+1;
$pi[] = $i+1;
$pc = count($pi);
$ba = $pi[$pc-2] ;
$part[$pa] = array_slice( $main, $ba, count($p));
unset($p);
}
}
print_r($part);
for($s=1;$s<count($part);$s++){
echo '<br>';
echo array_sum($part[$s]);
}
コードは以下のような部分合計を出力します
13
14
16
14
15
15
17
私は次のことがうまくいくかどうか疑問に思っています：
左から、すぐsum > sigmaに2つに分岐します。1つはそれをプッシュする値を含み、もう1つはプッシュしない値を含みます。rightSum = totalSum-leftSumおよびを使用して、右側のデータを再帰的に処理しますrightP = P-1。
したがって、最初は合計= 60
2 4 6 7 6 3 3 3 4 3 4 4 4 3 3 1
次に、の場合2 4 6 7、sum = 19> sigmaなので、次のように分割します。
2 4 6 7 6 3 3 3 4 3 4 4 4 3 3 1
2 4 6 7 6 3 3 3 4 3 4 4 4 3 3 1
次に、とをそれぞれ7 6 3 3 3 4 3 4 4 4 3 3 1と6 3 3 3 4 3 4 4 4 3 3 1で処理します。P = 4-1sum = 60-12sum = 60-19
これにより、O（P * n）になると思います。
1つまたは2つの値がはるかに大きい場合は問題になる可能性がありますが、シグマ以上の値の場合は、おそらくそれを独自のパーティションに配置できます（配列を前処理してこれらを見つけることが最善のアイデアかもしれません（そして削減する）適切に合計））。
それが機能する場合は、二乗和誤差（またはそれに近い誤差）を最小限に抑える必要があります。これは、望ましい測定値のようです。
バックトラッキングに基づくアルゴリズムを提案します。ランダムに選択されたメイン関数は、元の配列から要素を選択し、分割された配列に追加します。追加ごとに、元のソリューションよりも優れたソリューションを取得するためにチェックします。これは、偏差を計算する関数を使用して達成され、ページに新しい要素を追加するたびに区別されます。とにかく、目的の解に到達できず、プログラムが強制終了するようなループに独自の変数を追加するとよいと思いました。望ましい解決策とは、if の条件によって課される条件に関してすべての要素を追加することを意味します。
sum=CalculateSum(vector)
Read P
sigma=sum/P
initialize P vectors, with names vector_partition[i], i=1..P
list_vector initialize a list what pointed this P vectors
initialize a diferences_vector with dimension of P
//that can easy visualize like a vector of vectors
//construct a non-recursive backtracking algorithm
function Deviation(vector) //function for calculate deviation of elements from a vector
{
dev=0
for i=0 to Size(vector)-1 do
dev+=|vector[i+1]-vector[i]|
return dev
}
iteration=0
//fix some maximum number of iteration for while loop
Read max_iteration
//as the number of iterations will be higher the more it will get
//a more accurate solution
while(!IsEmpty(vector))
{
for i=1 to Size(list_vector) do
{
if(IsEmpty(vector)) break from while loop
initial_deviation=Deviation(list_vector[i])
el=SelectElement(vector) //you can implement that function using a randomized
//choice of element
difference_vector[i]=|sigma-CalculateSum(list_vector[i])|
PutOnBackVector(vector_list[i], el)
if(initial_deviation>Deviation(difference_vector))
ExtractFromBackVectorAndPutOnSecondVector(list_vector, vector)
}
iteration++
//prevent to enter in some infinite loop
if (iteration>max_iteration) break from while loop
いくつかのコードウィッチが計算された偏差の量でインクリメントする場合、最初に追加することでこれを変更できます。aditional_amount=0 iteration=0 while { ... if(initial_deviation>Deviation(difference_vector)+additional_amount) ExtractFromBackVectorAndPutOnSecondVector(list_vector, vector) if(iteration>max_iteration) { iteration=0 aditional_amout+=1/some_constant } iteration++ //秒を削除 if最初のバージョンから }
これは、1 次元のビン パッキング問題の場合と非常によく似ています。http://www.cs.sunysb.edu/~algorith/files/bin-packing.shtmlを参照してください。関連書籍のThe Algorithm Design Manualで、Skienna はfirst-fit reduction approach を提案しています。つまり、ビンのサイズ (平均 = 合計 / N) を計算し、残りの最大のオブジェクトを、余裕のある最初のビンに割り当てます。ビンをいっぱいにしなければならないところまで到達するか、運が良ければ完璧にフィットします。Skiena が述べているように、「First-fit reduction には直感的な魅力があります。最初にかさばるオブジェクトをパックし、小さなオブジェクトが隙間を埋めることができることを願っているからです。」
以前の投稿者が言ったように、問題は NP 完全であるように見えるため、適切な時間内に完全に解決することはできず、ヒューリスティックを探す必要があります。
最近これが必要になり、次のようにしました。
[[sum:0],[sum:0]...[sum:0]]initial配列を返します。これはJSのコードです。
function groupTasks(tasks,groupCount){
var sum = tasks.reduce((p,c) => p+c),
initial = [...Array(groupCount)].map(sa => (sa = [], sa.sum = 0, sa));
return tasks.sort((a,b) => b-a)
.reduce((groups,task) => { var group = groups.reduce((p,c) => p.sum < c.sum ? p : c);
group.push(task);
group.sum += task;
return groups;
},initial);
}
var tasks = [...Array(50)].map(_ => ~~(Math.random()*10)+1), // create an array of 100 random elements among 1 to 10
result = groupTasks(tasks,7); // distribute them into 10 sub arrays with closest sums
console.log("input array:", JSON.stringify(tasks));
console.log(result.map(r=> [JSON.stringify(r),"sum: " + r.sum]));あなたの問題は、目的をどのように定義するかに応じて、最小メイクスパン スケジューリング問題と非常に似ているか同じです。最大値を最小化したい場合、|sum_i - sigma|まさにその問題です。
ウィキペディアの記事で参照されているように、この問題は に対して NP 完全ですp > 2。グラハムのリスト スケジューリング アルゴリズムは に最適でp <= 3、 の近似比を提供します2 - 1/p。他のアルゴリズムとその概算については、Wikipedia の記事を参照してください。
このページに記載されているすべてのアルゴリズムは、別の目的のために解決されているか、正しくない/準最適であるか、NP の問題を解決するために使用できます :)
最大フローアルゴリズムを使用できます。