ねりあずぶろぐ

雑多です。

コータス先生の動的計画法講座 part1

ナップサック問題

ナップサック問題とは、それぞれ価値と重さが与えられた荷物と最大容量(入る最大の重さ)の決まったナップサックがあり、そのナップサックにどの荷物を入れれば価値を最大にできるかという問題(正確な問題文は「ナップサック問題」でググろう)。
今回はナップサック問題を数学的に考えてみます。次回はもう少しプログラミング的内容で書きます。

f:id:nerianighthawk:20170705205354p:plain(クチートちゃん)「コータス先生、こんにちは!今日は動的計画法について学びました!」

f:id:nerianighthawk:20170705210126p:plain(コータス先生)「こんにちは、クチートくん。それで、動的計画法についてはわかったのかい?」

f:id:nerianighthawk:20170705205354p:plain「はい、ナップサック問題をやったんですが、漸化式が{{\rm dp}(i, j) = {\rm max}({\rm dp}(i-1, j), {\rm dp}(i-1, j-w(i))+ v(i))}で与えられることがわかりました!」

f:id:nerianighthawk:20170705210126p:plain「ほう、わかったというのはちゃんと導くことができたということかな?」

f:id:nerianighthawk:20170705205354p:plain「うっ…そう言われると…」

f:id:nerianighthawk:20170705210126p:plain「ほら、いつも何か新しい式を学んだときはしっかりと導き出せるようにしとけって言ってるだろう?」

f:id:nerianighthawk:20170705205354p:plain「そうですね、これじゃただの暗記問題ですもんね。」

f:id:nerianighthawk:20170705210126p:plain「それじゃあナップサック問題について考えてみようか。まずはmax関数を定義しよう。」

{ \displaystyle
{\rm max}:\mathcal{P}_{\rm fin}(\mathbb{N})\to\mathbb{N}\\
{\rm max}(A) = a \ {\rm s.t.} \ \forall x \in A[a \geq x]
}

f:id:nerianighthawk:20170705205354p:plain「あの、何書いてあるのか全然わからないんですが。」

f:id:nerianighthawk:20170705210126p:plain「まあ、要するに有限な自然数の集合から最大のものを取って来るっていうだけだよ。」

f:id:nerianighthawk:20170705205354p:plain「はぁ…なるほど。」

f:id:nerianighthawk:20170705210126p:plain「そして、このmax関数を使ってナップサック問題の式をそのまま書くと以下のようになるよ。」

{ \displaystyle
f(N, W) = {\rm max}(\{v(1)x_{1} + \dots + v(N)x_{N}\ |\ w(1)x_{1} + \dots + w(N)x_{N} \leq W,\\
\hspace{100pt}x_{j}\in\{0,1\}\ (j=1,\dots ,N)\}
}

f:id:nerianighthawk:20170705205354p:plain「この式もわかんないです…」

f:id:nerianighthawk:20170705210126p:plain「この式はわかった方がいいね、ここから漸化式にもっていく必要があるからね。」

f:id:nerianighthawk:20170705205354p:plain「max関数はさっき定義した集合の最大値を見つける関数ですよね?中の集合は…v(1)からv(N)は価値で、それにxたちをかけて足してる?このxたちはなんですか?」

f:id:nerianighthawk:20170705210126p:plain「xは後ろの条件を見てもらえばわかると思うけど、{0, 1}の集合から取って来てるだろう?つまりオンオフを考えるためのものだよ。0なら入れない、1なら入れる。」

f:id:nerianighthawk:20170705205354p:plain「あ、なるほど、ナップサックに入れるかどうかを決めるためのものだったんですね。それなら後ろの重さについての条件も理解できます。」

f:id:nerianighthawk:20170705210126p:plain「よし、じゃあここから漸化式を作って行こうか。と言っても最適性の原理さえ知っていればそんなに難しくないんだけどね。」

f:id:nerianighthawk:20170705205354p:plain「最適性の原理?なんですかそれ?」

f:id:nerianighthawk:20170705210126p:plain「最適性の原理は『最適解の部分解は,元の問題の部分問題の最適解である』というものだよ。証明もできるけど、まあ常識的に考えても部分解が最適解じゃなかったら元の解も最適解じゃないよね。」

f:id:nerianighthawk:20170705205354p:plain「なるほど。これがどう使えるんでしょう?」

f:id:nerianighthawk:20170705210126p:plain「さっきの式に対して最適性の原理を考えると、任意のk≦Nとy≦Wに対してf(k,y)が部分問題の最適解になることがわかるよ。」

f:id:nerianighthawk:20170705205354p:plain「おお、なるほど!じゃああとはf(k-1,y)からf(k,y)を導けばいいので…{f(k,y) = f(k-1,y) + v(k)}でしょうか?」

f:id:nerianighthawk:20170705210126p:plain「おいおい、焦りすぎだよ。それじゃあいくらでも入れられるじゃないか。それにクチートくんが最初に言った公式とも合ってないよ。」

f:id:nerianighthawk:20170705205354p:plain「あ、そうですね。重さも考慮にいれなくちゃいけないし、常に価値が足されるわけではないですよね…。そのためのxですね。k番目のxが0のパターンはf(k-1,y)と変化がないのでそのまま、xが1のパターンは価値が足されるんですがそのために容量を確保しなくちゃいけないのでその分の重さw(k)を引けばいいんでf(k-1,y-w(k))+v(k)ですね!あとはどうやってxを決めるかですね…。」

f:id:nerianighthawk:20170705210126p:plain「それも今回話をしたよ。問題をよく考えて、今回やったことを思い出して見て。」

f:id:nerianighthawk:20170705205354p:plain「えっと、問題は最適解を見つけること。つまり価値をより大きくすること。ということはxが0か1かはそのときの価値が大きい方を取ればいいから…max関数です!」

f:id:nerianighthawk:20170705210126p:plain「それだ!じゃあ早速書いて見て!」

f:id:nerianighthawk:20170705205354p:plain「つまり漸化式は{f(k, y) = {\rm max}\{f(k-1, y),\ f(k-1, y-w(i))+ v(i)\}}ですね!」

f:id:nerianighthawk:20170705210126p:plain「そうだね、ちなみにk=1のときはyとw(1)の大きさを比べてyの方が小さければ0、大きければv(1)を入れてあげればいいよ。」

f:id:nerianighthawk:20170705205354p:plain「そうですね。漸化式なので初期値も用意しなくちゃですよね。」

f:id:nerianighthawk:20170705210126p:plain「これでクチートくんが最初に言っていた漸化式を求めることができたね。」

f:id:nerianighthawk:20170705205354p:plain「難しいですけど、面白いですね。最適性の原理は他にも応用が利きそうです。」

f:id:nerianighthawk:20170705210126p:plain「お、いい目をしているね。キーワードは動的計画法や多段階決定過程だから調べてみるといいよ。」

f:id:nerianighthawk:20170705205354p:plain「はい、精進します!」

f:id:nerianighthawk:20170705210126p:plain「それじゃあ今日はここまでにしようか。」

f:id:nerianighthawk:20170705205354p:plain「ありがとうございましたー!」


まとめ
ナップサック問題の漸化式は以下で与えられる。
{ \displaystyle
f(1,y) =
\begin{cases}
0&(y \lt w(1))&\\
v(1)&(w(1)\leq y)&
\end{cases}
\\
f(k, y) = {\rm max}\{f(k-1, y),\ f(k-1, y-w(i))+ v(i)\}\hspace{10pt}(2\leq k \leq N)
}

コータス先生の正規表現講座

とある日のクチートちゃんとコータス先生の会話

f:id:nerianighthawk:20170705205354p:plain(クチートちゃん)「コータス先生、こんにちは!」

f:id:nerianighthawk:20170705210126p:plain(コータス先生)「こんにちは、今日はどうしたんだい?」

f:id:nerianighthawk:20170705205354p:plain「はい、早速本題ですが正規表現ワイルドカードの違いがどうしてもわからなくて…。」

f:id:nerianighthawk:20170705210126p:plain「なるほど、たしかにごっちゃにしている人は多いねぇ…。ちなみにクチートくんの認識はどうなんだい?」

f:id:nerianighthawk:20170705205354p:plain「えっと、ワイルドカード正規表現も文字列の検索に使うものですよね?ワイルドカードの方が表現力が少ないなぁって感じる程度ですね。」

f:id:nerianighthawk:20170705210126p:plain「うん、まあ間違ってはないけど、その認識だと違いはわかりづらいかもなぁ。でも表現力っていうのは一つの違いだと思ってくれていいかな。文字列検索で使えるものというのも間違ってはいないから、文字列検索をする上での使用感の違いから入る方がいいかもね。」

f:id:nerianighthawk:20170705205354p:plain「でもひとくくりに正規表現と言っても実際はいくつも種類がありますよね?だったらワイルドカードも表現力の低い正規表現ってことになりませんか?」

f:id:nerianighthawk:20170705210126p:plain「あー、その認識はまずいね。なぜなら正規表現ワイルドカードでは文字列の検索の仕方が根本的に違うからね。」

f:id:nerianighthawk:20170705205354p:plain「説明をお願いします!」

f:id:nerianighthawk:20170705210126p:plain「そうだねぇ、例えば下の2つは同じように文字列検索をできるよね?」

ワイルドカード:あい*えお
正規表現   :あい.*えお

f:id:nerianighthawk:20170705205354p:plain「そうですね、どちらも"あい"の後に任意の文字が0文字以上続いて"えお"ってなっている文字列を検索します。」

f:id:nerianighthawk:20170705210126p:plain「そうだね、でもクチートくんの言った考え方はワイルドカード寄りの考え方なんだ。ワイルドカードでは、任意の文字を表す記号(だいたいは"*“と”?“)を扱って文字列検索を行うよ。」

f:id:nerianighthawk:20170705205354p:plain「え、じゃあ正規表現だとどういう考え方なんですか?」

f:id:nerianighthawk:20170705210126p:plain正規表現だと、『"あい"と"えお"の間に任意の文字が0文字以上続くような文字列の集合の中に存在する文字列を検索する』と考えるよ。」

f:id:nerianighthawk:20170705205354p:plain「そういえば、正規表現は文字列の集合を1つの文字列で表現したものだっていうのをどこかで読みましたね…。いまいちピンと来てないんですが、もう少し砕いた説明はありませんか?」

f:id:nerianighthawk:20170705210126p:plain「そうだね、いきなり文字列の集合だとか言われてもよくわかんないよね。じゃあまず簡単に0~9上での正規表現を考えてみようか。」

f:id:nerianighthawk:20170705205354p:plain「0~9上での正規表現???」

f:id:nerianighthawk:20170705210126p:plain「そう、文字としては{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}(以下この集合をNとおく)の10個の文字だけを使った正規表現だよ。」

f:id:nerianighthawk:20170705205354p:plain「なるほど、実用性は低そうですが、理解する上では重要なんでしょうね。」

f:id:nerianighthawk:20170705210126p:plain「デデン!それでは問題です!」

f:id:nerianighthawk:20170705205354p:plain(突然なんか始まった…)

f:id:nerianighthawk:20170705210126p:plain正規表現は文字列の集合です。では、N上の正規表現"..“はどんな集合でしょう?」

f:id:nerianighthawk:20170705205354p:plain「えっと、".“が任意の1文字を表す正規表現で今は0~9の文字しか使えないから…。答えは{00, 01, 02, …, 99}です!」

f:id:nerianighthawk:20170705210126p:plain「正解!正解したあなたにはどくけしをプレゼント!」

f:id:nerianighthawk:20170705205354p:plain(私、毒無効なんだけどなぁ…)

f:id:nerianighthawk:20170705210126p:plain「第2問!N上の正規表現で"0*“はどんな集合でしょう?」

f:id:nerianighthawk:20170705205354p:plain「2問目あるんですか!えっと、"*“は直前の文字が0文字以上続くの意味なので、答えは{0, 00, 000, 0000, …, 00000, …}ってあれ?無限集合になってしまいました…。」

f:id:nerianighthawk:20170705210126p:plain「残念、不正解!でも無限集合になってしまったからではないよ、むしろ無限集合になることは構わないよ。ちなみに正解は{, 0, 00, 000, 0000, …, 00000, …}。空の文字を忘れているよ。」

f:id:nerianighthawk:20170705205354p:plain「あ、そうか。0文字以上だから空の文字を含めなくちゃいけないんですね!」

f:id:nerianighthawk:20170705210126p:plain「どうだろう?少しは正規表現をわかってもらえたかな?」

f:id:nerianighthawk:20170705205354p:plain「そうですね、今になって考えるとワイルドカード正規表現って全然違うものなんだなと感じます。」

f:id:nerianighthawk:20170705210126p:plain「それはよかった。厳密に定義しようとするともう少し数学に詳しくないといけないから、その話はまた今度だね。」

f:id:nerianighthawk:20170705205354p:plain「はーい!今日はありがとうございました!」

まとめ

ワイルドカード:任意の文字を表す記号を使う。語源はトランプのワイルドカード(どんなカードにでもなれるカード)から来ているので、同じようなものだと考えて良い。 正規表現:文字列の集合を一つの文字列で表現する表現方法。何かしらの文字の集合が用意されており、その上に定義される。文字列検索の際はその集合の元として存在するかどうかで検索する。