半環上の最大部分配列問題とKadane's algorithm

この記事はSunrise Advent Calendar 2019の9日目の記事です。

adventar.org

内容はごった煮ということなので、アルゴリズムと代数について書きます。

TL; DR

Kadane's algorithmと呼ばれる最大部分配列問題を $O(n)$ で解くアルゴリズムがある。
このアルゴリズムはトロピカル半環上で動作する。
つまり、半環上に一般化できる！

最大部分配列問題

最大部分配列問題（maximum subarray problem）とは、与えられた配列に対して、その連続部分配列のうち和が最大となるものの値を求める問題のことです。

形式化すると次のようになります（以下、添字は0-basedとします）。

入力：大きさ $n$ の数列 $\displaystyle (a_i)_{i=0}^{n-1}$
出力： $\displaystyle \max \left\{\sum_{k=i}^j a_k \mathrel{}\middle|\mathrel{} 0 \leq i \leq j \lt n \right\}$

Kadane's algorithm

Kadane's algorithmは最大部分配列問題を $O(n)$ で解くDPの一種です。以前記事を書いたので、こちら↓を見てください。

ark4rk.hatenablog.com

よく見ると、最大部分配列問題もKadane's algorithmもトロピカル半環上で議論できることがわかるので、それについて本記事で解説します。

半環

半環（rig*1）とは、以下を満たす加法と乗法の２項演算 $+$ 、 $\cdot$ をもつ集合 $R$ のことである：

は単位元をもつ可換モノイド（commutative monoid, abelian monoid）*2：
- $^\forall x, y, z\in R, (x+y)+z = x+(y+z)$ （結合律）
- $^\forall x\in R, 0+x=x+0=x$ （単位元の存在）
- $^\forall x, y\in R, x+y = y+x$ （可換）
は単位元をもつモノイド（monoid）：
- $^\forall x, y, z\in R, (x\cdot y)\cdot z = x\cdot (y\cdot z)$ （結合律）
- $^\forall x\in R, 1\cdot x=x\cdot 1=x$ （単位元の存在）
分配律（distributive law）：
- $^\forall x, y, z\in R, x\cdot(y+z) = (x\cdot y) + (x\cdot z)$
- $^\forall x, y, z\in R, (y+z)\cdot x = (y\cdot x) + (z\cdot x)$
absorption/annihilation law：
- $^\forall x\in R, 0\cdot x=x\cdot 0=0$

参考：https://ncatlab.org/nlab/show/rig

以下では、半環の構造を明示するときは $(R, +, 0, \cdot, 1)$ のように表記するものとします。

トロピカル半環

トロピカル半環（tropical rig）とは、半環 $(\mathbb{R} \cup \{-\infty\}, \oplus, -\infty, \otimes, 0)$ のことである。max-plus algebraとも呼ばれる*3。ここで、 $\oplus$ 、 $\otimes$ は次のように定義される：

$^\forall x, y\in \mathbb{R} \cup \{-\infty\}, x\oplus y := \max\{x, y\}$
$^\forall x, y\in \mathbb{R} \cup \{-\infty\}, x\otimes y := x + y$

$(\mathbb{R} \cup \{-\infty\}, \oplus, -\infty, \otimes, 0)$ が半環であることは、半環の定義の $R, +, 0, \cdot, 1$ をそれぞれ $\mathbb{R} \cup \{-\infty\}, \oplus, -\infty, \otimes, 0$ に置き換えると明らかです。

qiita.com

トロピカル半環上の最大部分配列問題

最大部分配列問題はトロピカル半環を用いて記述できることを示します。

表記

$\displaystyle \bigoplus_{k=i}^j a_k := \left( \cdots \left(\left(a_i \oplus a_{i+1}\right) \oplus a_{i+2}\right) \oplus \cdots \right) \oplus a_j$
$\displaystyle \bigotimes_{k=i}^j a_k := \left( \cdots \left(\left(a_i \otimes a_{i+1}\right) \otimes a_{i+2}\right) \otimes \cdots \right) \otimes a_j$

写像 $\bigoplus\colon 2^{\mathbb{R} \cup \{-\infty\}} \rightarrow \mathbb{R} \cup \{-\infty\}$ を次のように定義する：

$\bigoplus(\emptyset) := -\infty$
に対して
- 任意に $x \in S$ を一つ選び、 $\bigoplus(S) := (\bigoplus(S - \{x\})) \oplus x$ とする。

$\oplus$ は可換かつ結合律が成り立つので、 $\bigoplus(S)$ の演算結果は一意に定まり写像 $\bigoplus$ はwell-definedである。

最大部分配列問題

上記の表記を用いると、最大部分配列問題は次のように書き直せる：

入力：大きさ $n$ の数列 $\displaystyle \{a_i\}_{i=0}^{n-1}$
出力： $\displaystyle \bigoplus \left( \left\{\bigotimes_{k=i}^j a_k \mathrel{}\middle|\mathrel{} 0 \leq i \leq j \lt n \right\} \right)$

以下では

\begin{align} \displaystyle x := \bigoplus \left( \left\{\bigotimes_{k=i}^j a_k \mathrel{}\middle|\mathrel{} 0 \leq i \leq j \lt n \right\} \right) \end{align}

とします。

トロピカル半環上のKadane's algorithm

Kadane's algorithmがトロピカル半環上の最大部分配列問題に対しても適用できることを示します（これの証明を書き換えただけです）。

まず、 $\bigoplus$ の計算の順序は問われないので

\begin{align} x = \bigoplus_{j=0}^{n-1} \bigoplus_{i=0}^j \bigotimes_{k=i}^j a_k \end{align}

と表せます。ここで $\displaystyle s_j := \bigoplus_{i=0}^j \bigotimes_{k=i}^j a_k$ とおくと、 $\displaystyle x = \bigoplus_{j=0}^{n-1} s_j$ となります。また、 $s_0 = a_0$ です。さらに $^\forall j \gt 0$ に対して次の関係式が成り立ちます。

\begin{align} s_{j} &= \bigoplus_{i=0}^j \bigotimes_{k=i}^j a_k \\ &= \left( \bigoplus_{i=0}^{j-1} \bigotimes_{k=i}^j a_k \right) \oplus \left( \bigoplus_{i=j}^j \bigotimes_{k=i}^j a_k \right) \\ &= \left( \left( \bigoplus_{i=0}^{j-1} \bigotimes_{k=i}^{j-1} a_k \right) \otimes a_j \right) \oplus a_j & \because \text{分配律} \\ &= \left( s_{j-1} \otimes a_j \right) \oplus a_j \end{align}

つまり

$s_0 = a_0$
$^\forall j \gt 0$ に対して $s_{j} = \left( s_{j-1} \otimes a_j \right) \oplus a_j$

が成り立つので、トロピカル半環の半環としての性質のみでKadane's algorithmを使えることが示されました。

半環上のKadane's algorithm

これまでの議論から一般の半環についてもKadane's algorithmが適用できることがわかります。

実装すると次のようになります（D言語）：

T kadane(
  T,              // 型
  alias plusFun,  // 加法の２項演算
  T plusIdentity, // 加法の単位元
  alias multFun,  // 乗法の２項演算
  T multIdentity  // 乗法の単位元
)(T[] as) {
  alias _plusFun = binaryFun!plusFun;
  alias _multFun = binaryFun!multFun;
  T res = plusIdentity;
  T s = multIdentity;
  foreach(a; as) {
    s = _plusFun(_multFun(s, a), a);
    res = _plusFun(res, s);
  }
  return res;
}

これを用いて通常の最大部分配列問題を解く例です：

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4033280#1

応用例

いくつか応用できそうな例を上げます。

半環 $(\mathbb{Z}, +, 0, \cdot, 1)$

半環 $(\mathbb{Z}, +, 0, \cdot, 1)$ 上の"最大部分配列問題"は

\begin{align} \sum_{0 \leq i \leq j \lt n} \prod_{k=i}^j a_k \end{align}

を解く問題になります。上の関数kadaneを用いると

long ans = kadane!(long, "a+b", 0, "a*b", 1)(as);

で $O(n)$ で求まります*4。

半環 $(\{0, 1, \ldots, 2^B - 1\}, \oplus, 0, \land, 2^B - 1)$

$(\{0, 1, \ldots, 2^B - 1\}, \oplus, 0, \land, 2^B - 1)$ は半環です。ここで

$B$ は、非負整数の定数*5
$\oplus$ は、各桁について排他的論理和を行う演算
$\land$ は、各桁について論理積を行う演算

を表すものとします。この半環上の"最大部分配列問題"は

\begin{align} \bigoplus_{0 \leq i \leq j \lt n} \bigwedge_{k=i}^j a_k \end{align}

を解く問題になります。上の関数kadaneを用いると

long ans = kadane!(long, "a^b", 0, "a&b", (1L<<B)-1)(as);

で $O(n)$ で求まります。

半環 $(2^{\Sigma^*}, \cup, \emptyset, \cdot, \{\varepsilon\})$

$(2^{\Sigma^*}, \cup, \emptyset, \cdot, \{\varepsilon\})$ は半環です。ここで

$\Sigma$ は、アルファベット全体の集合（有限集合）
$\Sigma^*$ は、 $\Sigma$ 上の言語、つまり $\Sigma$ 上の有限列全体の集合
$2^{\Sigma^*}$ は、 $\Sigma^*$ の冪集合
$\cup$ は、集合の意味での和集合
は、各文字列のペアを連結（concatenate）してできる文字列全体の集合を求める演算：
- $^\forall A, B \in 2^{\Sigma^*}, A \cdot B := \{ st \in \Sigma^* \mid s\in A \land t \in B \}$
$\varepsilon$ は、空文字列

を表すものとします。この半環上の"最大部分配列問題"は、列 $\displaystyle (A_i)_{i=0}^{n-1} \in (2^{\Sigma^*})^n$ に対して

\begin{align} \left\{ a_i a_{i+1} \cdots a_j \mathrel{}\middle|\mathrel{} 0 \leq i \leq j \lt n \land (a_i, \ldots, a_j) \in \prod_{k=i}^j A_k \right\} \end{align}

を解く問題になります。つまり、文字列集合の配列に対して、連続した各要素内の文字列を順番に連結したときに生じるすべての文字列を列挙する問題となります。

bool[string][] As = [
  ["abc": true],
  ["": true],
  ["d": true, "e": true],
  ["test": true]
];

で文字列集合の配列が与えられたとき、関数kadaneを用いると

kadane!(
  bool[string],
  (A, B) {
    bool[string] res;
    foreach(a; A.keys) res[a] = true;
    foreach(b; B.keys) res[b] = true;
    return res;
  },
  null,
  (A, B) {
    bool[string] res;
    foreach(a; A.keys) foreach(b; B.keys) {
      res[a~b] = true;
    }
    return res;
  },
  ["": true]
)(As).keys.sort.writeln;

によって

["", "abc", "abcd", "abcdtest", "abce", "abcetest", "d", "dtest", "e", "etest", "test"]

と出力されます。この計算量は、各２項演算の計算量が $O(1)$ ではないので、全体で $O(n)$ にはならないことに注意してください。この問題に関しては Kadane's algorithm を単純に適用するより効率的な方法がある可能性があります。

感想

アルゴリズムの対象を抽象化することによって、ひとつのアルゴリズムが様々な問題に適用できる例（ここではKadane's algorithm）を見つけることができました。

最後の応用例のように、元の問題とは大きくかたちが異なる問題に対しても同一アルゴリズムを適用できるのは、抽象化のたのしいところだと思います。

代数はいいぞ。

思いついたものを書いただけなので、参考文献は特にありません。

*1:A ring without negatives。semiringと言うこともあるが、文献によってはsemiringは単位元の存在を要求しない場合があるので注意。

*2:逆元の存在も要求、つまり群であれば $R$ は環（ring）となる。

*3:半環 $(\mathbb{R} \cup \{\infty\}, \min, \infty, +, 0)$ をトロピカル半環の定義とする文献もある。こちらはmin-plus algebraとも呼ばれる。

*4:このままだと簡単にオーバーフローしてしまうため、実際に競プロで出題されるなら $n$ の制約が小さいかmodで求めるかになりそうです。

*5: $B=0$ のときは自明環になります。自明環は環です。

Ark's Blog

引っ越しました→ https://blog.arkark.dev/

半環上の最大部分配列問題とKadane's algorithm

TL; DR

最大部分配列問題

Kadane's algorithm

半環

トロピカル半環

トロピカル半環上の最大部分配列問題

表記

最大部分配列問題

トロピカル半環上のKadane's algorithm

半環上のKadane's algorithm

応用例

半環 $(\mathbb{Z}, +, 0, \cdot, 1)$

半環 $(\{0, 1, \ldots, 2^B - 1\}, \oplus, 0, \land, 2^B - 1)$

半環 $(2^{\Sigma^*}, \cup, \emptyset, \cdot, \{\varepsilon\})$

感想