読者です 読者をやめる 読者になる 読者になる

大学院生(情報科学)のブログ

モチベーション維持のためのブログです。

最大部分配列問題

要素の和を最大化する{A}の連続する部分配列を発見する問題を最大部分配列問題と呼ぶ.

例えば、配列{A[13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7]}と与えられたとき、最大部分配列は{A[7 \cdots 10]}で和は43である.

この問題を分割統治を用いて解く.

分割は配列の中央点{mid}を基準にし{A[low \cdots mid]}{A[mid+1 \cdots high]}に分ける.この時、最大部分配列は{A[low \cdots mid]}{A[mid+1 \cdots high]}または、中央点をまたいで出現する.

また、部分配列は元の配列より小さいので、再帰的に最大部分配列を求める事ができる.

したがって、中央をまたぐ部分配列の中での最大部分配列を求め、求めた3つの部分配列の中から最大となるものを取り出せば良い.

{mid}は簡単に求まる.中央点をまたぐ最大部分配列は{A[i \cdots mid]}{A[mid+1 \cdots j]}を求め、結合すれば良い.

{find\_ max\_ crossing\_ array}は配列{A}と添字{low,mid,high}を引数とし、中央点をまたぐ最大部分配列の境界を定める2つの添字と最大部分列に属する要素の和を返す.

2,3行目で{A[i \cdots mid]}{A[mid+1 \cdots j]}の配列の初期化を行っている.
8行目の{for}文では{A[i \cdots mid]}の最大値を取る{i}を求める.10行目で{A[i+1 \cdots mid]}{A[i \cdots mid]}の大きさを比較し、{A[i \cdots mid]}の方が大きい場合、11行目で部分配列の先頭を{i}に更新する.

14行目の{for}文では同様にして、最大値を取る{A[mid+1 \cdots j]}を求める.

{find \_ max \_ crossing \_array}を用いて最大部分配列問題を解く{find\_ max\_ array}を以下に示す.

2行目の{if}文では要素が一つの配列、つまりインスタンスが基底か否かを判定する.基底の場合、要素はただ一つであるので、この要素の添字を両端の添字とし、その添字と要素を3行目で返している.
5行目では中間点を計算する.6行目で左最大部分配列、7行目では右最大部分配列を再帰的に決定する.8行目は中央点をまたぐ最大部分配列を求めている.
9行目からの条件分岐で3つの部分配列を比較し、最大となる配列を最大部分配列とし結果を返している.

実行結果
{A = [13,-3,-25,20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7] \\
print\;find\_ max\_ array(A,0,len(A)-1)\\
(7,10,43)}


分割統治法とマージソート

以前紹介した挿入ソートは逐次添加法を用いている.

部分配列{A[0\cdots j-1]}をソートした後、1つの要素{A[j]}を正しい場所に挿入する事によってソートされた{A[0\cdots j]}を得た.

多くの結うようなアルゴリズムの構造は再帰であり、その多くの場合、分割統治法に基づいて設計されている.

分割統治法では、問題を元の問題と類似してはいるがサイズが小さいいいくつかの部分問題に分割し、これらの部分問題を再帰的に解いた後、その回を組み合わせて元の問題に対する解を構成する.

以下に3つの段階から構成される再帰の各レベルを示す.

分割 : 問題をいくつかの同じ問題のより小さいインスタンスである部分問題に分割
統治 : 部分問題を再帰的に解く事によって統治する.(部分問題のサイズが十分小さい場合は直接的な方法で解く)
結合 : 部分問題の解を組み合わせて元の問題の解を得る
ここで、分割統治法に従って構成されているマージソートについて紹介する.

マージソートの各段階を以下に示す.

分割 : ソートすべき長さ{n}の列を2つの{\frac{n}{2}}に分割
統治 : マージソートを用いて2つの部分列を再帰的にソート
結合 : 2つのソートされた部分列をマージしてソートされた解を作る
再帰が底をつくのはソートすべき列の長さが1になったときであり、長さ1の配列はソート済みなので何もしない.

マージソートは補助関数の{merge(A,p,q,r)}を用いてソート済みの列を結合する.
{A}は配列、{p,q,r}は添字であり、{p \leq q < r}を満たす.
部分列{A[p\cdots q-1]}{A[q\cdots r]}が共にソート済みであると仮定し、これらを結合する事で単一のソート済み配列{A[p\cdots r]}を得る.

また、番兵と呼ばれる特別な値を持たせる事でプログラムを簡単にしている.この番兵を底に置く事で、判定条件を省略している.今回は番兵に{\infty}を持たせている.

6,8行目の[tex;{for}]文では{A[p \cdots q]}を左部分列に、{A[q+1 \cdots r]}を右部分列に格納している.
10,11行目は左右の部分列の末尾に番兵を格納している.
14行目の{for}文では左右の先頭の要素の内小さい方を{A}に挿入している.
14行目のループの各繰り返しは不変式を維持している.(正当性の証明は省略するが初期条件、ループ内条件、終了条件を確かめる)

この{merge}を用いて{merge\_ sort(A,p,r)}を構築する.
{A[p \cdots r]}に格納された要素をソートする.{p \geq r}のとき、部分列は要素を一つしか含まないのでソート済みである.
それ以外のときは{A[p \cdots r-1]}再帰的に分割する.

f:id:fooloveup:20170315193530p:plain

実行結果
{
A = [5,2,4,7,1,3,2,6] \\
print\; merge\_ sort(A,0,7) \\
[1, 2, 2, 3, 4, 5, 6, 7]}

ループ不変式

前回の記事で挿入ソートのソースコードを示したが、その正当性を今回は示す.

def insert_sort(A):
		for j in range(1,len(A)):
			key = A[j]
			i = j - 1
			while i >= 0 and A[i] > key:
				A[i+1] = A[i]
				i = i - 1
			A[i+1] = key
		return A

for文の{j}は、トランプで言うところの、左手に挿入しようとしている「現在のカード」を示す.
したがって、部分配列A[0,{\cdots},j-1]はソート済みの配列であり、A[j+1,{\cdots},n]はソートが行われいない配列である.
ここで、既にソートされているA[0,{\cdots},j-1]が持つループ不変式を定式化する.

  • 初期条件 : ループ実行開始直前ではループ不変式は真
  • ループ内条件 : あるk回目の繰り返しの直前でループ不変式が真ならば、{k+1}回目の直前でも真
  • 終了条件 : ループが停止した時、アルゴリズムの正当性の証明に繋がる有力な性質が不変式から得られる

初期条件とループ内条件を見ると数学的帰納法に類似しているように見える.
実際この二つを示されたら全ての繰り返しにおいてループ不変式は死んである.
しかし、ループ不変式を用いて正当性を示すのに最も重要なのは第3の性質である.
この停止性が数学的帰納法の相違点である.(数学的帰納法は無限に適用するのに対し、今回はループが停止すると「帰納」を停止する.)

これらを用いて、挿入ソートの不変性を示す.

  • 初期条件 : ループ開始直前{(j=1)}の直前はソート済み部分配列は{A[0]}と要素を一つしか含まないので、ソート済みなのは明らか.したがって、開始直前では真.
  • ループ内条件 : キーである{A[j]}を挿入するべき場所が見つかるまで{A[j-1],A[j-2],\cdots}をそれぞれ1つずつ右に移し、空いた場所に{A[j]}の値(キー)を挿入する.こうすることで、部分配列{A[0\cdots,j]}はソート済みになる.(厳密には{while}文についての正当性も示す必要があるがここでは割愛)
  • 終了条件 : {for}文の終了条件は{j > n-1}を満たすときである.

したがって、停止時には{j = n}である.
部分配列{A[0\cdots,n-1]}はソート済みであり、配列全体であるので、配列全体がソート済みであると結論できる.

以上より、アルゴリズムは正当であることが示された.

今後も、余力があればアルゴリズムの正当性についても考えて行きたいが、アルゴリズムの紹介だけで終わってしまうかもしれない...

・ソーティング問題の定式化と言葉の定義

入力: {n}個の数の列({a_{1},a_{2},\cdots,a_{n})}
出力: {a_{1}^{'} \leq a_{2}^{'} \leq \cdots \leq a_{n}^{'}} である入力列の置換({a_{1}^{'},a_{2}^{'},...,a_{n}^{'})}

キー(key):ソートしたいと思っている数値

・挿入ソート
少数の要素を効率よくソートするアルゴリズム

ex) トランプの手札をソート

  1. 左手を空にする
  2. 裏向きに置かれたカードを1枚ずつ引き、左手の正しい位置に挿入
  3. 正しい位置は右から左へと順に既に持っているカードと比較する

以下にpythonで書いたinsert_sortを示す.
引数にはソートする長さ{n}の配列を取る.
アルゴリズムは入力された数列をその場でソートする.
出力はソートされた配列が返される.

def insert_sort(A):
		for j in range(1,len(A)):
			key = A[j]
			i = j - 1
			while i >= 0 and A[i] > key:
				A[i+1] = A[i]
				i = i - 1
			A[i+1] = key
		return A

実行結果
Input:[5, 2, 4, 6, 1, 3]
Output:[1, 2, 3, 4, 5, 6]

アルゴリズムの正当性を示すことは次にまわす.

M1になるまでにアルゴリズムとデータ構造を復習しようと思って学校の図書館から「アルゴリズムイントロダクション」を借りてきました。

 

アルゴリズムイントロダクション 第3版 総合版 (世界標準MIT教科書)

アルゴリズムイントロダクション 第3版 総合版 (世界標準MIT教科書)

  • 作者: T.コルメン,R.リベスト,C.シュタイン,C.ライザーソン,Thomas H. Cormen,Clifford Stein,Ronald L. Rivest,Charles E. Leiserson,浅野哲夫,岩野和生,梅尾博司,山下雅史,和田幸一
  • 出版社/メーカー: 近代科学社
  • 発売日: 2013/12/17
  • メディア: 大型本
  • この商品を含むブログ (7件) を見る
 

 この本は、数多くの「東京大学大学院情報理工学研究科創造情報学専攻」志願者向けの院試ブログで紹介されていたものです。

高いし、分厚いし自分のお金で買うのはちょっと難しいですね。。。笑

(鈍器と言われているほど分厚いです)

 

さて、M1になるまでの一ヶ月間で読めるところまで読み進めたいと思います。

pythonでコード書いて、それをあげて行こうかなと思ってます。

 

はじめまして

 

はじめまして。

卒業研究が無事終わり、学部生としての4年間は残すところ卒業式だけとなりました。

 

そこで、来春から大学院生になるので、研究、勉強のモチベーションを維持するための(自己満)ブログを開設することにしました。

 

とりあえず自己紹介

在籍:某大学情報科学科(卒業見込み)

専攻(興味ある分野):機械学習自然言語処理

TOEIC:700点半ば

使用言語:python

資格:基本情報技術者

 

今後は、勉強で得た知識の忘備録、TOEICやら応用情報の勉強忘備録及び結果、興味深い論文の紹介などをしていきたいと思います。