🏥 🚛 🌸 最大サブアレイまたは最大サブアレイ問題を見つけるための高岡忠雄アルゴリズム 🚖 🥉 👩🏽‍⚖️

少し前に、Acceler8 2011並列プログラミングコンテストが開催されました。問題の本質は、この行列で最大の部分行列を見つけることでした（見つかった部分行列の要素の合計は最大でなければなりません）。短い「グーグル」の後、特定の高岡忠雄アルゴリズムが他のアルゴリズムよりも速くこの問題を解決することがわかりました。

「コールは受け入れられました！」そして、私はそれを実現することを目標に、可能な限りこのアルゴリズムを探し始めました。並列化が不十分であり、その複雑さにかなり大きな定数が含まれているという事実にもかかわらず。

しかし、発見されたのは高岡忠雄自身による英語の記事だけでした（これらの記事の 1つです）。翻訳しなければなりませんでした。

アルゴリズムのアイデアそのものは、最初はとてつもなく単純に思えました。

最初に、a [1..i、1..j]のような行列のすべてのプレフィックス和s [i、j]を計算する必要があります。制限s [i、0] = s [0、 j] =0。明らかに、これは時間O（mn）で行われます。

主なアルゴリズム：

マトリックスが1つの要素であることが判明した場合、その値を返します。

そうでなければ：

m> nの場合、行列を90度回転します。
したがって、m≤nです。

A_leftを左半分の解としましょう。
A_rightは右半分のソリューションです。
A_column-列中心のタスクのソリューション（中心線と交差する最大のサブマトリックスを見つける）
一般的な解決策は、3つの最大値です。

再帰によってA_leftとA_rightが見つかった場合、A_columnを手動で見つける必要があります。

元の記事でこの解決策を見つけることについて書かれたものは次のとおりです。

「 列中心のタスクは次のように解決できます。

A_column = max（k = 1：i-1、l = 0：n / 2-1、i = 1：m、j = n / 2 + 1：n）{s [i、j]-s [i、 l]-s [k、j] + s [k、l]}。

iとkを修正し、lとjを変更して残りの式を最大化します。 これは、次の式と同等です。

i = 1、...、mおよびk = 1、...、i-1。

A_column [i、k] = max（l = 0：n / 2-1、j = n / 2 + 1：n）{−s [i、l] + s [k、l] + s [i、j ]-s [k、j]}

s ∗ [i、j] = −s [j、i]とする。 この式は次のように縮小できます。

A_column [i、k] = −min（l = 0：n / 2-1）{s [i、l] + s ∗ [l、k]} + max（j = n / 2 + 1：n）{ s [i、j] + s ∗ [j、k]} "

次に、高岡忠雄の他のタスクに言及する必要があります：距離行列乗算（この用語を翻訳することは想定していません）。

一番下の行は次のとおりです。

DMMの目標は、要素が実数である2つのn次元行列A = a [i、j]およびB = b [i、j]の距離積C = ABを計算することです。

c [i、j] = min（k = 1：n）{a [i、k] + b [k、j]}

c [i、j]の本質は、頂点の3つの層で構成される非循環指向グラフの第1層から第3層の頂点jまでの頂点iからの最小距離です。これらの頂点には、各レイヤーで1、...、nの番号が付けられ、1番目のレイヤーのiから2番目のレイヤーのjまでの距離はa [i、j]で、2番目のレイヤーのiから3番目のレイヤーのjまでの距離はb-[i、j ]。明らかに、この式は最小値ではなく最大値を計算するために簡単に縮小できます-これは最大のパスを見つけるタスクです。

したがって、この定義を使用すると、次のものを取得できます。

式A_column [i、k] = −min（l = 0：n / 2-1）{s [i、l] + s ∗ [l、k]} + max（j = n / 2 + 1：n ）{s [i、j] + s ∗ [j、k]}式の最初の部分は最小がDMM、2番目が最大-DMMであることがわかります。 S1とS2をそれぞれ要素（i、j）がs [i、j-1] s [i、j + n / 2]である行列とする。任意の行列Tについて、T ∗を転置および否定によってTから取得した行列とします。次に、S1とS1 ∗を最小値に「乗算」して下三角行列を取得し、S2とS2 ∗を最大値に「乗算」して下三角行列を取得し、最後に前の行列から減算することにより、上式を計算できます。最大値を計算すると、答えが得られます。

A_column = max（DMM_max（S2 * S2 ∗）-DMM_min（S1 * S1 ∗））

次に、サイズnxnの行列AおよびBのDMM問題を解くための擬似コードが変換されます。

Copy Source | Copy HTML / n B list[ i ], .. list[ i ] i ; / V = { 1 , ..., n}; for i := 1 to n do begin for k := 1 to n do begin cand[k]:=first of list[k]; d[k] := a [ i , k] + b [k, cand[k]]; end; / V d[ 1 ], ..., d[n]; / S - ; /* 1 : */ while |S| ≤ n − n log n do begin / v ; / cand[v] S; c[ i , cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; for w in W do while cand[w] is in S do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; U := S; /* 2 : */ while |S| < n do begin / v ; if cand[v] is not in S then begin / cand[v] S; c[v, cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; end else W = {v}; for w in W do cand[w]:=next of list[w]; while cand[w] is in U do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; end.

Copy Source | Copy HTML / n B list[ i ], .. list[ i ] i ; / V = { 1 , ..., n}; for i := 1 to n do begin for k := 1 to n do begin cand[k]:=first of list[k]; d[k] := a [ i , k] + b [k, cand[k]]; end; / V d[ 1 ], ..., d[n]; / S - ; /* 1 : */ while |S| ≤ n − n log n do begin / v ; / cand[v] S; c[ i , cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; for w in W do while cand[w] is in S do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; U := S; /* 2 : */ while |S| < n do begin / v ; if cand[v] is not in S then begin / cand[v] S; c[v, cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; end else W = {v}; for w in W do cand[w]:=next of list[w]; while cand[w] is in U do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; end.

Copy Source | Copy HTML / n B list[ i ], .. list[ i ] i ; / V = { 1 , ..., n}; for i := 1 to n do begin for k := 1 to n do begin cand[k]:=first of list[k]; d[k] := a [ i , k] + b [k, cand[k]]; end; / V d[ 1 ], ..., d[n]; / S - ; /* 1 : */ while |S| ≤ n − n log n do begin / v ; / cand[v] S; c[ i , cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; for w in W do while cand[w] is in S do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; U := S; /* 2 : */ while |S| < n do begin / v ; if cand[v] is not in S then begin / cand[v] S; c[v, cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; end else W = {v}; for w in W do cand[w]:=next of list[w]; while cand[w] is in U do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; end.

Copy Source | Copy HTML / n B list[ i ], .. list[ i ] i ; / V = { 1 , ..., n}; for i := 1 to n do begin for k := 1 to n do begin cand[k]:=first of list[k]; d[k] := a [ i , k] + b [k, cand[k]]; end; / V d[ 1 ], ..., d[n]; / S - ; /* 1 : */ while |S| ≤ n − n log n do begin / v ; / cand[v] S; c[ i , cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; for w in W do while cand[w] is in S do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; U := S; /* 2 : */ while |S| < n do begin / v ; if cand[v] is not in S then begin / cand[v] S; c[v, cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; end else W = {v}; for w in W do cand[w]:=next of list[w]; while cand[w] is in U do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; end.

Copy Source | Copy HTML / n B list[ i ], .. list[ i ] i ; / V = { 1 , ..., n}; for i := 1 to n do begin for k := 1 to n do begin cand[k]:=first of list[k]; d[k] := a [ i , k] + b [k, cand[k]]; end; / V d[ 1 ], ..., d[n]; / S - ; /* 1 : */ while |S| ≤ n − n log n do begin / v ; / cand[v] S; c[ i , cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; for w in W do while cand[w] is in S do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; U := S; /* 2 : */ while |S| < n do begin / v ; if cand[v] is not in S then begin / cand[v] S; c[v, cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; end else W = {v}; for w in W do cand[w]:=next of list[w]; while cand[w] is in U do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; end.

Copy Source | Copy HTML / n B list[ i ], .. list[ i ] i ; / V = { 1 , ..., n}; for i := 1 to n do begin for k := 1 to n do begin cand[k]:=first of list[k]; d[k] := a [ i , k] + b [k, cand[k]]; end; / V d[ 1 ], ..., d[n]; / S - ; /* 1 : */ while |S| ≤ n − n log n do begin / v ; / cand[v] S; c[ i , cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; for w in W do while cand[w] is in S do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; U := S; /* 2 : */ while |S| < n do begin / v ; if cand[v] is not in S then begin / cand[v] S; c[v, cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; end else W = {v}; for w in W do cand[w]:=next of list[w]; while cand[w] is in U do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; end.

Copy Source | Copy HTML / n B list[ i ], .. list[ i ] i ; / V = { 1 , ..., n}; for i := 1 to n do begin for k := 1 to n do begin cand[k]:=first of list[k]; d[k] := a [ i , k] + b [k, cand[k]]; end; / V d[ 1 ], ..., d[n]; / S - ; /* 1 : */ while |S| ≤ n − n log n do begin / v ; / cand[v] S; c[ i , cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; for w in W do while cand[w] is in S do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; U := S; /* 2 : */ while |S| < n do begin / v ; if cand[v] is not in S then begin / cand[v] S; c[v, cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; end else W = {v}; for w in W do cand[w]:=next of list[w]; while cand[w] is in U do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; end.

Copy Source | Copy HTML / n B list[ i ], .. list[ i ] i ; / V = { 1 , ..., n}; for i := 1 to n do begin for k := 1 to n do begin cand[k]:=first of list[k]; d[k] := a [ i , k] + b [k, cand[k]]; end; / V d[ 1 ], ..., d[n]; / S - ; /* 1 : */ while |S| ≤ n − n log n do begin / v ; / cand[v] S; c[ i , cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; for w in W do while cand[w] is in S do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; U := S; /* 2 : */ while |S| < n do begin / v ; if cand[v] is not in S then begin / cand[v] S; c[v, cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; end else W = {v}; for w in W do cand[w]:=next of list[w]; while cand[w] is in U do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; end.

Copy Source | Copy HTML / n B list[ i ], .. list[ i ] i ; / V = { 1 , ..., n}; for i := 1 to n do begin for k := 1 to n do begin cand[k]:=first of list[k]; d[k] := a [ i , k] + b [k, cand[k]]; end; / V d[ 1 ], ..., d[n]; / S - ; /* 1 : */ while |S| ≤ n − n log n do begin / v ; / cand[v] S; c[ i , cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; for w in W do while cand[w] is in S do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; U := S; /* 2 : */ while |S| < n do begin / v ; if cand[v] is not in S then begin / cand[v] S; c[v, cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; end else W = {v}; for w in W do cand[w]:=next of list[w]; while cand[w] is in U do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; end.

Copy Source | Copy HTML / n B list[ i ], .. list[ i ] i ; / V = { 1 , ..., n}; for i := 1 to n do begin for k := 1 to n do begin cand[k]:=first of list[k]; d[k] := a [ i , k] + b [k, cand[k]]; end; / V d[ 1 ], ..., d[n]; / S - ; /* 1 : */ while |S| ≤ n − n log n do begin / v ; / cand[v] S; c[ i , cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; for w in W do while cand[w] is in S do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; U := S; /* 2 : */ while |S| < n do begin / v ; if cand[v] is not in S then begin / cand[v] S; c[v, cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; end else W = {v}; for w in W do cand[w]:=next of list[w]; while cand[w] is in U do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; end.

Copy Source | Copy HTML / n B list[ i ], .. list[ i ] i ; / V = { 1 , ..., n}; for i := 1 to n do begin for k := 1 to n do begin cand[k]:=first of list[k]; d[k] := a [ i , k] + b [k, cand[k]]; end; / V d[ 1 ], ..., d[n]; / S - ; /* 1 : */ while |S| ≤ n − n log n do begin / v ; / cand[v] S; c[ i , cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; for w in W do while cand[w] is in S do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; U := S; /* 2 : */ while |S| < n do begin / v ; if cand[v] is not in S then begin / cand[v] S; c[v, cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; end else W = {v}; for w in W do cand[w]:=next of list[w]; while cand[w] is in U do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; end.

Copy Source | Copy HTML / n B list[ i ], .. list[ i ] i ; / V = { 1 , ..., n}; for i := 1 to n do begin for k := 1 to n do begin cand[k]:=first of list[k]; d[k] := a [ i , k] + b [k, cand[k]]; end; / V d[ 1 ], ..., d[n]; / S - ; /* 1 : */ while |S| ≤ n − n log n do begin / v ; / cand[v] S; c[ i , cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; for w in W do while cand[w] is in S do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; U := S; /* 2 : */ while |S| < n do begin / v ; if cand[v] is not in S then begin / cand[v] S; c[v, cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; end else W = {v}; for w in W do cand[w]:=next of list[w]; while cand[w] is in U do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; end.

Copy Source | Copy HTML / n B list[ i ], .. list[ i ] i ; / V = { 1 , ..., n}; for i := 1 to n do begin for k := 1 to n do begin cand[k]:=first of list[k]; d[k] := a [ i , k] + b [k, cand[k]]; end; / V d[ 1 ], ..., d[n]; / S - ; /* 1 : */ while |S| ≤ n − n log n do begin / v ; / cand[v] S; c[ i , cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; for w in W do while cand[w] is in S do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; U := S; /* 2 : */ while |S| < n do begin / v ; if cand[v] is not in S then begin / cand[v] S; c[v, cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; end else W = {v}; for w in W do cand[w]:=next of list[w]; while cand[w] is in U do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; end.

Copy Source | Copy HTML / n B list[ i ], .. list[ i ] i ; / V = { 1 , ..., n}; for i := 1 to n do begin for k := 1 to n do begin cand[k]:=first of list[k]; d[k] := a [ i , k] + b [k, cand[k]]; end; / V d[ 1 ], ..., d[n]; / S - ; /* 1 : */ while |S| ≤ n − n log n do begin / v ; / cand[v] S; c[ i , cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; for w in W do while cand[w] is in S do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; U := S; /* 2 : */ while |S| < n do begin / v ; if cand[v] is not in S then begin / cand[v] S; c[v, cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; end else W = {v}; for w in W do cand[w]:=next of list[w]; while cand[w] is in U do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; end.

Copy Source | Copy HTML / n B list[ i ], .. list[ i ] i ; / V = { 1 , ..., n}; for i := 1 to n do begin for k := 1 to n do begin cand[k]:=first of list[k]; d[k] := a [ i , k] + b [k, cand[k]]; end; / V d[ 1 ], ..., d[n]; / S - ; /* 1 : */ while |S| ≤ n − n log n do begin / v ; / cand[v] S; c[ i , cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; for w in W do while cand[w] is in S do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; U := S; /* 2 : */ while |S| < n do begin / v ; if cand[v] is not in S then begin / cand[v] S; c[v, cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; end else W = {v}; for w in W do cand[w]:=next of list[w]; while cand[w] is in U do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; end.

Copy Source | Copy HTML / n B list[ i ], .. list[ i ] i ; / V = { 1 , ..., n}; for i := 1 to n do begin for k := 1 to n do begin cand[k]:=first of list[k]; d[k] := a [ i , k] + b [k, cand[k]]; end; / V d[ 1 ], ..., d[n]; / S - ; /* 1 : */ while |S| ≤ n − n log n do begin / v ; / cand[v] S; c[ i , cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; for w in W do while cand[w] is in S do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; U := S; /* 2 : */ while |S| < n do begin / v ; if cand[v] is not in S then begin / cand[v] S; c[v, cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; end else W = {v}; for w in W do cand[w]:=next of list[w]; while cand[w] is in U do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; end.

Copy Source | Copy HTML / n B list[ i ], .. list[ i ] i ; / V = { 1 , ..., n}; for i := 1 to n do begin for k := 1 to n do begin cand[k]:=first of list[k]; d[k] := a [ i , k] + b [k, cand[k]]; end; / V d[ 1 ], ..., d[n]; / S - ; /* 1 : */ while |S| ≤ n − n log n do begin / v ; / cand[v] S; c[ i , cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; for w in W do while cand[w] is in S do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; U := S; /* 2 : */ while |S| < n do begin / v ; if cand[v] is not in S then begin / cand[v] S; c[v, cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; end else W = {v}; for w in W do cand[w]:=next of list[w]; while cand[w] is in U do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; end.

Copy Source | Copy HTML / n B list[ i ], .. list[ i ] i ; / V = { 1 , ..., n}; for i := 1 to n do begin for k := 1 to n do begin cand[k]:=first of list[k]; d[k] := a [ i , k] + b [k, cand[k]]; end; / V d[ 1 ], ..., d[n]; / S - ; /* 1 : */ while |S| ≤ n − n log n do begin / v ; / cand[v] S; c[ i , cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; for w in W do while cand[w] is in S do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; U := S; /* 2 : */ while |S| < n do begin / v ; if cand[v] is not in S then begin / cand[v] S; c[v, cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; end else W = {v}; for w in W do cand[w]:=next of list[w]; while cand[w] is in U do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; end.

Copy Source | Copy HTML / n B list[ i ], .. list[ i ] i ; / V = { 1 , ..., n}; for i := 1 to n do begin for k := 1 to n do begin cand[k]:=first of list[k]; d[k] := a [ i , k] + b [k, cand[k]]; end; / V d[ 1 ], ..., d[n]; / S - ; /* 1 : */ while |S| ≤ n − n log n do begin / v ; / cand[v] S; c[ i , cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; for w in W do while cand[w] is in S do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; U := S; /* 2 : */ while |S| < n do begin / v ; if cand[v] is not in S then begin / cand[v] S; c[v, cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; end else W = {v}; for w in W do cand[w]:=next of list[w]; while cand[w] is in U do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; end.

Copy Source | Copy HTML / n B list[ i ], .. list[ i ] i ; / V = { 1 , ..., n}; for i := 1 to n do begin for k := 1 to n do begin cand[k]:=first of list[k]; d[k] := a [ i , k] + b [k, cand[k]]; end; / V d[ 1 ], ..., d[n]; / S - ; /* 1 : */ while |S| ≤ n − n log n do begin / v ; / cand[v] S; c[ i , cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; for w in W do while cand[w] is in S do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; U := S; /* 2 : */ while |S| < n do begin / v ; if cand[v] is not in S then begin / cand[v] S; c[v, cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; end else W = {v}; for w in W do cand[w]:=next of list[w]; while cand[w] is in U do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; end.

Copy Source | Copy HTML / n B list[ i ], .. list[ i ] i ; / V = { 1 , ..., n}; for i := 1 to n do begin for k := 1 to n do begin cand[k]:=first of list[k]; d[k] := a [ i , k] + b [k, cand[k]]; end; / V d[ 1 ], ..., d[n]; / S - ; /* 1 : */ while |S| ≤ n − n log n do begin / v ; / cand[v] S; c[ i , cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; for w in W do while cand[w] is in S do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; U := S; /* 2 : */ while |S| < n do begin / v ; if cand[v] is not in S then begin / cand[v] S; c[v, cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; end else W = {v}; for w in W do cand[w]:=next of list[w]; while cand[w] is in U do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; end.

Copy Source | Copy HTML / n B list[ i ], .. list[ i ] i ; / V = { 1 , ..., n}; for i := 1 to n do begin for k := 1 to n do begin cand[k]:=first of list[k]; d[k] := a [ i , k] + b [k, cand[k]]; end; / V d[ 1 ], ..., d[n]; / S - ; /* 1 : */ while |S| ≤ n − n log n do begin / v ; / cand[v] S; c[ i , cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; for w in W do while cand[w] is in S do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; U := S; /* 2 : */ while |S| < n do begin / v ; if cand[v] is not in S then begin / cand[v] S; c[v, cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; end else W = {v}; for w in W do cand[w]:=next of list[w]; while cand[w] is in U do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; end.

Copy Source | Copy HTML / n B list[ i ], .. list[ i ] i ; / V = { 1 , ..., n}; for i := 1 to n do begin for k := 1 to n do begin cand[k]:=first of list[k]; d[k] := a [ i , k] + b [k, cand[k]]; end; / V d[ 1 ], ..., d[n]; / S - ; /* 1 : */ while |S| ≤ n − n log n do begin / v ; / cand[v] S; c[ i , cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; for w in W do while cand[w] is in S do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; U := S; /* 2 : */ while |S| < n do begin / v ; if cand[v] is not in S then begin / cand[v] S; c[v, cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; end else W = {v}; for w in W do cand[w]:=next of list[w]; while cand[w] is in U do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; end.

Copy Source | Copy HTML / n B list[ i ], .. list[ i ] i ; / V = { 1 , ..., n}; for i := 1 to n do begin for k := 1 to n do begin cand[k]:=first of list[k]; d[k] := a [ i , k] + b [k, cand[k]]; end; / V d[ 1 ], ..., d[n]; / S - ; /* 1 : */ while |S| ≤ n − n log n do begin / v ; / cand[v] S; c[ i , cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; for w in W do while cand[w] is in S do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; U := S; /* 2 : */ while |S| < n do begin / v ; if cand[v] is not in S then begin / cand[v] S; c[v, cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; end else W = {v}; for w in W do cand[w]:=next of list[w]; while cand[w] is in U do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; end.

Copy Source | Copy HTML / n B list[ i ], .. list[ i ] i ; / V = { 1 , ..., n}; for i := 1 to n do begin for k := 1 to n do begin cand[k]:=first of list[k]; d[k] := a [ i , k] + b [k, cand[k]]; end; / V d[ 1 ], ..., d[n]; / S - ; /* 1 : */ while |S| ≤ n − n log n do begin / v ; / cand[v] S; c[ i , cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; for w in W do while cand[w] is in S do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; U := S; /* 2 : */ while |S| < n do begin / v ; if cand[v] is not in S then begin / cand[v] S; c[v, cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; end else W = {v}; for w in W do cand[w]:=next of list[w]; while cand[w] is in U do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; end.

Copy Source | Copy HTML / n B list[ i ], .. list[ i ] i ; / V = { 1 , ..., n}; for i := 1 to n do begin for k := 1 to n do begin cand[k]:=first of list[k]; d[k] := a [ i , k] + b [k, cand[k]]; end; / V d[ 1 ], ..., d[n]; / S - ; /* 1 : */ while |S| ≤ n − n log n do begin / v ; / cand[v] S; c[ i , cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; for w in W do while cand[w] is in S do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; U := S; /* 2 : */ while |S| < n do begin / v ; if cand[v] is not in S then begin / cand[v] S; c[v, cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; end else W = {v}; for w in W do cand[w]:=next of list[w]; while cand[w] is in U do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; end.

Copy Source | Copy HTML / n B list[ i ], .. list[ i ] i ; / V = { 1 , ..., n}; for i := 1 to n do begin for k := 1 to n do begin cand[k]:=first of list[k]; d[k] := a [ i , k] + b [k, cand[k]]; end; / V d[ 1 ], ..., d[n]; / S - ; /* 1 : */ while |S| ≤ n − n log n do begin / v ; / cand[v] S; c[ i , cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; for w in W do while cand[w] is in S do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; U := S; /* 2 : */ while |S| < n do begin / v ; if cand[v] is not in S then begin / cand[v] S; c[v, cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; end else W = {v}; for w in W do cand[w]:=next of list[w]; while cand[w] is in U do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; end.

Copy Source | Copy HTML / n B list[ i ], .. list[ i ] i ; / V = { 1 , ..., n}; for i := 1 to n do begin for k := 1 to n do begin cand[k]:=first of list[k]; d[k] := a [ i , k] + b [k, cand[k]]; end; / V d[ 1 ], ..., d[n]; / S - ; /* 1 : */ while |S| ≤ n − n log n do begin / v ; / cand[v] S; c[ i , cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; for w in W do while cand[w] is in S do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; U := S; /* 2 : */ while |S| < n do begin / v ; if cand[v] is not in S then begin / cand[v] S; c[v, cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; end else W = {v}; for w in W do cand[w]:=next of list[w]; while cand[w] is in U do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; end.

Copy Source | Copy HTML / n B list[ i ], .. list[ i ] i ; / V = { 1 , ..., n}; for i := 1 to n do begin for k := 1 to n do begin cand[k]:=first of list[k]; d[k] := a [ i , k] + b [k, cand[k]]; end; / V d[ 1 ], ..., d[n]; / S - ; /* 1 : */ while |S| ≤ n − n log n do begin / v ; / cand[v] S; c[ i , cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; for w in W do while cand[w] is in S do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; U := S; /* 2 : */ while |S| < n do begin / v ; if cand[v] is not in S then begin / cand[v] S; c[v, cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; end else W = {v}; for w in W do cand[w]:=next of list[w]; while cand[w] is in U do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; end.

Copy Source | Copy HTML / n B list[ i ], .. list[ i ] i ; / V = { 1 , ..., n}; for i := 1 to n do begin for k := 1 to n do begin cand[k]:=first of list[k]; d[k] := a [ i , k] + b [k, cand[k]]; end; / V d[ 1 ], ..., d[n]; / S - ; /* 1 : */ while |S| ≤ n − n log n do begin / v ; / cand[v] S; c[ i , cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; for w in W do while cand[w] is in S do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; U := S; /* 2 : */ while |S| < n do begin / v ; if cand[v] is not in S then begin / cand[v] S; c[v, cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; end else W = {v}; for w in W do cand[w]:=next of list[w]; while cand[w] is in U do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; end.

Copy Source | Copy HTML / n B list[ i ], .. list[ i ] i ; / V = { 1 , ..., n}; for i := 1 to n do begin for k := 1 to n do begin cand[k]:=first of list[k]; d[k] := a [ i , k] + b [k, cand[k]]; end; / V d[ 1 ], ..., d[n]; / S - ; /* 1 : */ while |S| ≤ n − n log n do begin / v ; / cand[v] S; c[ i , cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; for w in W do while cand[w] is in S do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; U := S; /* 2 : */ while |S| < n do begin / v ; if cand[v] is not in S then begin / cand[v] S; c[v, cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; end else W = {v}; for w in W do cand[w]:=next of list[w]; while cand[w] is in U do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; end.

Copy Source | Copy HTML / n B list[ i ], .. list[ i ] i ; / V = { 1 , ..., n}; for i := 1 to n do begin for k := 1 to n do begin cand[k]:=first of list[k]; d[k] := a [ i , k] + b [k, cand[k]]; end; / V d[ 1 ], ..., d[n]; / S - ; /* 1 : */ while |S| ≤ n − n log n do begin / v ; / cand[v] S; c[ i , cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; for w in W do while cand[w] is in S do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; U := S; /* 2 : */ while |S| < n do begin / v ; if cand[v] is not in S then begin / cand[v] S; c[v, cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; end else W = {v}; for w in W do cand[w]:=next of list[w]; while cand[w] is in U do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; end.

Copy Source | Copy HTML / n B list[ i ], .. list[ i ] i ; / V = { 1 , ..., n}; for i := 1 to n do begin for k := 1 to n do begin cand[k]:=first of list[k]; d[k] := a [ i , k] + b [k, cand[k]]; end; / V d[ 1 ], ..., d[n]; / S - ; /* 1 : */ while |S| ≤ n − n log n do begin / v ; / cand[v] S; c[ i , cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; for w in W do while cand[w] is in S do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; U := S; /* 2 : */ while |S| < n do begin / v ; if cand[v] is not in S then begin / cand[v] S; c[v, cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; end else W = {v}; for w in W do cand[w]:=next of list[w]; while cand[w] is in U do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; end.

Copy Source | Copy HTML / n B list[ i ], .. list[ i ] i ; / V = { 1 , ..., n}; for i := 1 to n do begin for k := 1 to n do begin cand[k]:=first of list[k]; d[k] := a [ i , k] + b [k, cand[k]]; end; / V d[ 1 ], ..., d[n]; / S - ; /* 1 : */ while |S| ≤ n − n log n do begin / v ; / cand[v] S; c[ i , cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; for w in W do while cand[w] is in S do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; U := S; /* 2 : */ while |S| < n do begin / v ; if cand[v] is not in S then begin / cand[v] S; c[v, cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; end else W = {v}; for w in W do cand[w]:=next of list[w]; while cand[w] is in U do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; end.

Copy Source | Copy HTML / n B list[ i ], .. list[ i ] i ; / V = { 1 , ..., n}; for i := 1 to n do begin for k := 1 to n do begin cand[k]:=first of list[k]; d[k] := a [ i , k] + b [k, cand[k]]; end; / V d[ 1 ], ..., d[n]; / S - ; /* 1 : */ while |S| ≤ n − n log n do begin / v ; / cand[v] S; c[ i , cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; for w in W do while cand[w] is in S do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; U := S; /* 2 : */ while |S| < n do begin / v ; if cand[v] is not in S then begin / cand[v] S; c[v, cand[v]] := d[v]; / W = {w|cand[w] = cand[v]}; end else W = {v}; for w in W do cand[w]:=next of list[w]; while cand[w] is in U do cand[w]:= next of list[w]; / W d[w] = a [ i , w]+ b [w, cand[w]]; end; end.

この記事では、キューにバイナリヒープを使用することをお勧めします。後のバージョンでは、フィボナッチヒープを使用するとプロセスをさらに高速化できることが示されましたが、残念なことに、完全に実装することはできませんでした。したがって、バイナリを使用しました。

しかし、この擬似コードを実装しても、解決策が機能しないことがわかりました。 S1とS2を計算する段階で明らかなエラーが見つかりました。これらの行列を構築するための記述された規則は、アルゴリズムが正しく機能するのに十分ではありませんでした。そして、詳細な説明を見つけた記事はありませんでした。したがって、マトリックス自体を作成する必要がありました。

そのため、ソートとチェックに何時間も費やした後、次のルールが得られました。

Sを行列Aのプレフィックス行列とします。

次に、次元m x n / 2の行列S1には0の最初の列が含まれ、残りのn / 2-1列には接頭辞行列Sの最初の列が含まれます。

サイズn / 2 x mの行列S1 ∗には、0の最初の行と列が含まれ、残りの部分行列は、プレフィックス行列Sの最初の行と列の否定と転置です。

（k = n div 2 + n mod 2）

次元m x kの行列S2には、k番目から始まる接頭辞行列Sの列が含まれます。

次元k x mの行列S2 ∗：0の最初の列。次に、k番目の列から開始して、接頭辞行列Sの列を転置および否定します。

一般的に、アルゴリズムは理解と実装が非常に困難であることが判明し、例外的な速度に対する期待を満たしていませんでした（追加の最適化は実行されませんでした）。

同じ記事では、このアルゴリズムはO（n ^ 3 * log（log（n））/ log（n））時間で動作すると主張し、また、大きな行列の他のアルゴリズムと比較してアルゴリズムがより高速に動作することを述べています（明らかに非常に大きい）。

誰かが興味を持っているか、重要である場合、ここに私の実装のソースがあります（プロに書かれているので、「理解しやすさ」は保証できません）。この記事が誰かを助けてくれたらとてもうれしいです（このアルゴリズムでの調査に多くの時間を費やしたのは無駄ではありませんでした！）。

最大サブアレイまたは最大サブアレイ問題を見つけるための高岡忠雄アルゴリズム

More articles: