単語記事: アルゴリズム

編集

アルゴリズムとは、「問題を解くための手続き」である。

概要

たとえば、「をAからBへ移動しなさい」という問題があった場合

  1. の前に移動する
  2. しゃがむ
  3. を持つ
  4. 立つ
  5. A地点からB地点へ移動する
  6. しゃがむ
  7. をおろす

といった、処理がなされるがこれがアルゴリズムである・・・・おそらく・・・たぶん・・・きっとそう

もう少し厳密な説明

アルゴリズムとは、「問題の解き方」のことである。「いかに問題の解き方を工夫するか」というのが、アルゴリズムの研究と言ってほぼ間違いない。

たとえば、1から100まで足し算することを考えてみよう(この「アルゴリズム」について知っている人は読み飛ばして良い)。

1に2を足したら3、3に3を足して6、6に4を足して……と手作業でがんばる人もいるかもしれない。実際、昔の人はそうやって足し算していた。しかし、この問題は、実は、簡単に解くことができる。(1+100)*100/2で解けるのだ。なぜだろうか? 縦軸の長さが1,2,3……の棒グラフを考えてみよう。階段状になったグラフは、反転してくっつければ横幅100(つまり足しあわせる要素の数だ)、縦幅101(つまり1+100、2+99……で全部101になる)の長方形になることがわかる。この長方形の面積(1+100)*100は、1から100まで足しあわせた数の、ちょうど2倍になっている。なぜならば、階段グラフを二つ用意し、ひっくり返して、くっつけたからだ。

このように、1から100まで足しあわせるのにも、愚直にがんばるという方式と、棒グラフを反転させてくっつけて2で割るという方法の二通りがあることがわかる。後者の方が計算量が小さいのは明らかだろう。体験してみたい人は、がんばって1から100まで筆算するのと、(1+100)*100/2を計算するのとを較してみればいい。(むろん、答えは愚直に1から100まで足すのと、簡単な方法で計算するのとで一致している必要がある。ほかにもっとうまいアルゴリズムを考えたら、ちゃんと検算する必要があるのだ)

つまり、アルゴリズムが優秀であれば、計算量を減らすことができるのだ。

計算量を減らすのが何の役に立つって? と思われるかもしれないが、これは非常に重要な問題で、第二次大戦以前からずーーーーっと脈々と研究が続けられてきた。なぜなら、計算する量が少なければ少ないほど、コンピュータが楽になるからだ。たとえば、古いパソコンニコニコを見ているとき、動画カクカクしてイラッとしたことはないだろうか? これも、コンピュータの処理が、計算量より低かったから生じる問題だ。つまり、ニコニコ動画が使っている「アルゴリズム」がさらにパワーアップすれば、古いパソコンでもヌルヌル字幕を動かせたりすることができるのだ。

それだけではない。たとえば今ひろく使われているRSA暗号は、「コンピュータに解読させようとすると、あまりに時間がかかりすぎる」という理由で全性が保たれている。つまり、「どんなRSA暗号でも速く解読するアルゴリズムを手に入れたぜ!」と宣言し、しかもそれが正しいと認められたなら、っ先にFBIやらインターポールやらペンゴンやらMI6やらがやってきて、とにかく世界が震撼するのは間違いない。

あなたがもし、すばらしいアルゴリズムを見つけることができれば、大な富と尊敬を得られる……かもしれない。

そういうわけで、アルゴリズムというのはコンピュータと切っても切り離せない問題だ。

さらに込み入った説明

コンピュータは、実は1930年代に理論が完成している。現在もコンピュータの根幹を支え続けている数学的基礎付けは、アランチューリングというイギリス数学者が作りあげたのだ。ここでは、その概略を述べよう。

コンピュータにとって、「難しい」問題とは何か?

ここで、但し書きをしておこう。

以下で扱う問題とは、「Yes」もしくは「No」の答えしか存在しない。

つまり、コンピュータピコピコガーガーと動いた後、「はい」か「いいえ」しか言ってくれないのだ。そういう問題だけを取り扱うことにしよう。たとえば、「0011という文字列は、0と1の数が等しいか?」といった問題だ。「1から100までに素数は何個ある?」みたいな問題は取り扱わない。取り扱うなら、「1から100までの素数の数は10個以上である」みたいな問題に変換することにしよう。

さて、閑話休題。

コンピュータにとって、「難しい」問題とは、そのものズバリ解くのにめちゃくちゃ時間がかかる問題のことだ。たとえばあるアルゴリズムでは、一秒でサラッと答えを出せるのに対して、ほかのアルゴリズムでは十分、一時間かかるとする。つまり、「難しい」問題に対しては、「さらに速く」解けるアルゴリズムが、「カッコイイのだ。だってさ、総統閣下演説に「ヤーーーッ!!」って即答するのがカッコイイでしょ? 一時間も二時間もかかってから、ようやく「ヤーッ」って叫んでも、今頃おせぇんだよと突っ込み入れられること間違いなし。「難しい」問題に、麗に即答するのがカッコイイアルゴリズムなのだ。

ただ、どれが難しくて、どれが易しいのかは、人間ではわからない。またどれだけ難しいかも、人間の判断基準とは異なる。なぜなら、アルゴリズムを適用するときには、コンピュータ役になるからだ。「こんなの簡単じゃん!」ということさえ、コンピュータには難しいこともある。

そこで、「コンピュータとは何者ぞ?」という定義を行おう。それが、次に述べる「チューリングマシン」である。

チューリングマシンとは?

チューリングマシンとは、簡単に言えば入列に対して結果を吐き出す、簡単なコンピュータモデルだ。ただし、厳密には数学的に定義されている。

チューリングマシンの定義:

Kの要素は状態、Σの要素は入記号、Γはテープ記号の有限集合、Fの要素は受理状態、sはKの要素のうち、初期状態とし、δはK×ΣからKへの写像であり、状態遷移関数とする。Bは空白記号とする。

チューリングマシン(TM) Mとは、K,Σ,Γ,δ,s,B,F として表される。ただし、Bを書き込むことはできない。

(KはQとする場合もある。また、sやFをq(init),q(acc)とする流儀もある。定義なので詳しくは教授に聞こう)

これだけでは何のことかさっぱりわからないかもしれないが、辛抱強く聞いてほしい。まず、次のようなモデルを考えてみよう。

問題:東京駅から大阪駅まで行けるか?(ただし、経路は問わないが、同じは二度と通らないこととする)

このとき、Kの要素「状態」の初期位置、つまりsは「東京駅」である。

東京駅から大阪駅まで行きたいときには、どんな方法があるだろう。まず考えられるのは新幹線に乗ることだ。東京駅から新幹線に乗ったら、「新幹線」という状態に遷移する。この「新幹線に乗る」という「遷移」を「状態遷移」という。あるいは、18きっぷを握りしめて東海道線に乗るかもしれない。これもまた状態遷移だ。

結局、新幹線JRを使って大阪駅に到着するとする。ここでは、「東京駅から大阪駅まで行く」という問題を達成できたわけだ。この状態をF、つまり「受理状態」と呼ぶ。逆に、日本中を放浪してしまい、遙か彼方インド地で尽きてしまったとする。これは「不受理」として処理される。

このように、チューリングマシンとは、問題が与えられ、それをウームウームと解いていく一種の機械と考えることができるのだ(そして驚くべきことに、現在のコンピュータはすべて、1930年代に生み出されたチューリングマシンと同じ考え方で構成されている!)

もっと数学的なアルゴリズム論では、問題はたとえば次のように構成される。

問題:00001111は、0と1の数が同じか?

これを解くチューリングマシンを考えるのはたやすい。「0の数だけカウントを1UPさせて、1に出会うとカウントをダウンさせる」というチューリングマシンを作ればよい。最後にカウントが0になっていたら、受理だ。逆に、問題が「0111は、0と1の数が同じか?」という問題を、さきチューリングマシンに解かせると、不受理となる。

アルゴリズムが「作れない」問題?

アルゴリズムは、すべての問題について手続きを与えてくれるわけではない。これを「非可解」な問題と呼ぶ。

ところで、皆さんは「いつまでも動画の読み込みが終わらない……」と悩んだことはないだろうか? 動画データがたかだか有限なので、いつか待っていればなんとか100%読み込めるはずだ(ブラウザバグとかは抜きにして)。ところが、「本当にいつまでたっても解けるかどうかわからない」という問題がある。これを「非可解」と呼ぶ。

非可解の問題で一番有名なのは、チューリングマシンの停止問題だ。

問題:チューリングマシンは入に対して停止するか?

つまり、何らかの入が与えられたとき、チューリングマシンの動作が本当に止まるかどうか? というのは、非可解、つまりわからないのだ。

この手の問題にはアルゴリズムを作ることはできない。いつまでたっても、結局答えは出るかどうかわからないのだ。

再び:コンピュータにとって「難しい」問題とは?

では、最初に戻ってコンピュータにとって難しい問題とは何かを考えてみよう。

コンピュータは先に述べたように、チューリングマシンで模倣できる。現在使われているコンピュータは、まだ理論段階である量子コンピュータなんぞを除けば、すべてチューリングマシンの模倣だ。

だから、「難しい」問題のなかでも、頂点にいるのが「非可解」な問題なのだ。

じゃあ、非可解な問題を除いていけば、すべて可解なんじゃないか? つまり、非可解問題を除けば、コンピュータさんは何でも答えを出してくれるよね! という期待が当然わくことだろう。

本当にそうだろうか?

ネタバレをすると、解けます。でも……

「難しい問題」を解くアルゴリズム

さて、ここまで読み進めていただいたなら、もう次の問題はすんなりわかるだろう。

問題:東京駅から大阪駅まで行けるか?(ただし、経路は問わないが、同じは二度と通らないこととする)

これを計算機に解かせてみよう。可解かどうかはすぐにわかるはずだ。経路は問わないとはいえ、飛行機、まあ何にせよ有限個の経路しかない。あるいはそういうに制限をつけてもいいだろう。「鉄道を利用することにする」などなど。そうすれば、おのずとこの問題は、ごく直感的に「解けそうだな」という気分がする。

では、実際に解いてみよう。

まず入は、東京駅から出ているすべての路線だ。山手線京浜東北線京葉線中央線東北新幹線東海道新幹線etc……全部だ。そして、大阪駅からも多数の路線が出ている。東海道線環状線私鉄なども含めればさらに膨大になる。

この問題を、コンピュータに解かせると、次のようになる。

「えーっと、東京駅からは、山手線に乗ってみよう」
「おや、上野駅に着いたぞ。新幹線にも乗れるのか。東北に行ってみようかなぁ、それとも山手線に乗ったままにしようかなぁ……」
…… 
稚内に来てしまった。同じ路線はもう使えないから飛行機に乗るしかないなぁ」 
……
「ここはどこだ?」(北極で震えながら) →不受理

もうおわかりのように、コンピュータにとっては、大阪まで行き着こうと思うと総当たりで調べるしかないのだ。

方法が総当たりしかないというのは、コンピュータにとって、非常に難しい問題である。なぜなら、答えが出るまでずーーーっと待たなければならないからだ。ただし、「非可解」ではないので、何年かずーーーっとパソコンを動かしていれば答えが出るだろう。

しかし、「総当たりで調べる」というのも立アルゴリズムだ。逆に言えば、総当たりしかそれまで方法がないと思われていたアルゴリズムに、もっとうまいやり方を考えるというのがアルゴリズムの研究である。「難しい問題を易しく解く」と言い換えた方がいいだろうか。

このように、「コンピュータに解かせるには難しすぎるアルゴリズムしかない問題」のことをNP問題という。

もっと厳密に言えば、非決定性チューリングマシンによって(多項式時間で)解ける問題のことをNP問題という。

決定性・非決定性ってなーに?

それは難しい問題だ(人間にとって)。

ごくおおざっぱに言えば、東京駅で、「中央線に乗ろうかな〜それとも山手線に乗ろうかな〜新幹線もいいな〜」とフラフラ迷ってるヤツがいたら、そいつは「非決定性」だ。非決定性なヤツは、次の行動のバリエーションがたくさんあって、東京駅からどこか遠くに行ってしまう可性がある。逆に、東京駅からは新幹線にしか乗りません(キリッ」というヤツは「決定性」という。決定性のチューリングマシンなら、「東京駅」というデータが送られたらすぐさま新幹線に乗るのだが、非決定性チューリングマシンはもしかしたら中央線に乗っているかもしれない。

人間にとっては理解しがたいかもしれないが、コンピュータにとっては、膨大な路線の網で、東京から大阪へ、しかも同じを二度以上通らずに行くルートが果たしてあるかどうかというのは、非常に時間を要する問題なのだ。たまたま新幹線に乗れたとしても、新大阪新快速に乗って寝過ごすという行動もあり得る。なんせ非決定性だから、運良く新大阪で降りられても、次の行動はさまざまなのだ。そういう場合、答えを出すにはさらに時間がかかるだろう。

つまり、非決定性チューリングマシンというのはマヌケなのだ。次の行動が決まっていない。だから東京駅から大阪駅まで行くのに、わざわざ東北新幹線に乗るというトンチキな行動を犯したりもする。そうして間違えながら、総当たりしまくって、よーーーーやく、大阪にたどり着いて「いやぁ答えをようやく見つけましたよ」と言ってきたりする。そこで、「仕方ないなぁ、答えを見つけたんだから他の場所にフラフラしててかかった時間は見逃してやるよ」と言ってやる。これがNP問題の定義である。

さらに詳しい定義:

ある問題が非決定性多項式時間限定チューリングマシンで解けるとき、その問題をクラスNPに入る(NP問題)と呼ぶ。

非決定性なので、ある様相(たとえば東京駅)から次の様相への遷移(新幹線に乗るとか、中央線に乗るとか)は複数存在してもかまわない。非決定的選択(フラフラ浮気しながらいろんなところに行く)を行って、初めて受理様相に達したとき、受理様相から初期状態への距離がO(n^k)で押さえられる(結果的に見ると、東京から大阪まではちゃんと行けましたね、ということが簡単に確認できる)。

このとき、東京から大阪にたどり着くまでに倒れちゃったとか、東京から大阪までアメリカ経由で行きましたとか、そういう他のルートにかかった時間は不問とする。

しかし、まあ、だいたい東京から大阪に行けと言ってるのにインドに行くようなヤツは信用ならないから、々は総当たりで必死ルートを探すわけだ。それはいったい何年かかるかわからないけれど、まあ、いずれは答えを出してくれる。だから非可解ではないけれども、時間がかかるという意味で、難しい問題には変わりない。

ところで、決定性チューリングマシンで多項式時間で解ける問題を、P問題という。状態に対して行動が一意的に定まっているマジメ君の解ける問題だ。マジメ君は、たとえば、「000111は0と1の数が同じか?」という問題で、0を数えてる途中に浮気して1を数え始めたりしない。

々は、マジメ君しか信用したくないので、できれば浮気者の非決定性チューリングマシンでしか解けない問題を、なんとかマジメ君に解いてもらおうとして努している。つまり、非決定性チューリングマシンで解くような問題を、マジメ君は総当たりを必死に始めるので、それがいたたまれないのだ。当然、マジメ君にもっと簡単に解いてもらう方法があるんじゃないだろうか? という疑問がわき上がってくる。

NP≠P?

マジメ君必死に総当たりを始める中、だんだんNP問題の数が増えてきた。これはマジメ君には荷が重いなぁ、どうにかしてマジメ君の計算量を減らしてやれないかなぁとみんな必死で考えていたのだ。

で、ある日、Steve Cookという人物は、「じゃあNP問題の中で、一番難しいヤツを探してやんよ!」と言って、NPという概念を生み出した。「この問題が解けちゃったら、ほかのNP問題もスゲー簡単に解けちゃうんだぜ!」という問題を探そうとしたのだ。

具体的には、問題QがNP全——つまり最強に難しい問題——であるとき、問題Qが簡単に解けてしまうアルゴリズムが見つかった(これを具体的には決定性チューリングマシンで解ける、P問題という)ならば、ほかのあらゆるNPの問題は簡単に解ける(P問題になる)という問題だ。

そして確かに、そういう問題は見つかった。が、一個見つかったが最後、づる式に大量にNP全な問題が出てきてしまった。あのぷよぷよや、テトリスさえも、NP全であることがバレてしまったのだ。最強の問題がゴロゴロしていて、最近では見つかっても「あっそ」扱いされるレベルなのだ。

NP問題でググってここにくるかもしれない人に付け加えておくと、NP問題の検算は簡単だ。上の例のように、東京駅から大阪駅まで行くルートを見て、ちゃんとルールを破らずに一筆書きでやってきたかどうかをチェックするのは簡単である。これは決定性チューリングマシンで解ける、つまりP問題である。検算がP問題になるというのもNP問題の定義なので、P問題は実はNP問題に含まれる(これ以上はややこしいので、もっと知りたい人は大学に行くように)。

一般にNP問題を解くアルゴリズムの研究は、非常に難しいとされている。P問題はキッチリ計算できるのに、NP問題は解くためにかかる時間が非常に大きい。もし、NP問題がP問題のように、弊を恐れず言うと「簡単に」解けるようなことがあれば、先に述べたように全世界が震撼する。が、やっぱり理なんじゃねーの、というのが大方の見解だ。なぜなら、多くの数学者や計算機科学者たちが挑み続けているにもかかわらず、ずーっとNP全な問題が簡単に解けるようなアルゴリズムは見つかっていないからだ。だから、みんなNPはPとイコールではないと思っている。これをP≠NP予想といい、新たな明を見いだせたなら、あなたにはクレイ数学研究所から万ドルがもれなくもらえる予定だ。

で、結局アルゴリズムってなんだったの?

ようするに、問題を解く手続き。

それで間違っちゃいないんだけど、もっと難しい問題をはらんでいる、ということを紹介しておいた。

ここまできっちり読み進めてくれたなら、「難しい問題」の意味も「解けるけど時間がかかりすぎる」という意味だと理解していただけたと思うが、めて——難しい問題に対して、よりよいアルゴリズム提供すること、つまりより速く解けるアルゴリズムを発見することが、アルゴリズム研究者の要な研究テーマになっている。そのアルゴリズムによっては、最初に簡単に述べたように、暗号をバンバン解読して国家転覆させることさえも、不可能じゃないかもしれない。

アルゴリズムは、もしかしたら世界を変えるかもしれない、スゴイものなのだ。

 NHK教育:ピタゴラスイッチより (アルゴリズム体操)

こっちむいて二人で前習え~♪、あっちむいて二人で前習え~♪
こっちむいて二人で前習え~♪、あっちむいて二人で前習え~♪
手を横に、あら危ない、頭を下げればぶつかりません。~♪
手を横に、あら危ない、頭を下げれ大丈夫~♪
ぐるぐるぐる、ぐるぐるぐる、ぐーぐーる~♪、ぐるぐるぐる、ぐるぐるぐる、ぐーぐーる~♪
ぱっちん、ぱっちん、がしん、がしん~♪、ぱっちん、ぱっちん、がしん、がしん~♪
ぱっちん、ぱっちん、がしん、がしん~♪、ぱっちん、ぱっちん、がしん、がしん~♪
すって吐くのが深呼吸~♪すって吐くのが深呼吸~♪

 

NHK教育:ピタゴラスイッチより (アルゴリズム行進)

※ 1歩進んで前習え
   1歩進んで偉い人
   ひっくりかえってぺこりんこ
   横に歩いてきょろきょろ
   ちょっとここらでひらおよぎ
   ちょっとしゃがんで拾い
   空気入れますしゅうしゅう
   空気がはいってぴゅうぴゅう
(※ 3回ぐらいループする)
そろそろ、終わりかな、そろそろ、終わりかな、そろそろ、終わりかな、おわり

 

関連動画


 

関連記事


【スポンサーリンク】

携帯版URL:
http://dic.nicomoba.jp/k/a/%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0
ページ番号: 688712 リビジョン番号: 1679062
読み:アルゴリズム
初版作成日: 08/11/04 17:12 ◆ 最終更新日: 12/11/15 07:25
編集内容についての説明/コメント: 関連動画の修正
記事編集 / 編集履歴を閲覧

アルゴリズムについて語るスレ

40 : ななしのよっしん :2013/05/21(火) 18:45:26 ID: 7W78XD/xh3
>>37を受けて、ちょっと考えてみた。
以下、記事主さんでない流解釈だらけです。間違ってたら摘もらえると有りがたかったり。

K (状態集合)
  これは到達できる場所の集合
  東京京都新大阪大阪、新神戸三ノ宮etc……
  経路を鉄道に限らないなら関空伊丹空港神戸港……とにかく到達補地全部。
  当然インド地や北極なんかも入るね。
 本文だと「新幹線に乗る」とかも状態として扱ってたけど、これは後述のΣ、Γの要素と扱った方がいいというの解釈(´・ω・`)

s (開始状態) は東京駅、F (受理状態) は大阪駅
B (空白記号) はただの特殊記号。あんま深く考えなくていい。
(省略しています。全て読むにはこのリンクをクリック!)
41 : ななしのよっしん :2013/05/21(火) 18:46:33 ID: 7W78XD/xh3
>>40 続き
最後にΣ(入記号)、Γ(テープ記号)、δ(遷移関数)。
  これは本文の例で例えると難儀なので、新しく例を。
  偶然捕まえた行く人に、「東京から大阪まで行きたいねんけど、どないせやええんでっしゃろか?」と聞いて、その筋をメモったとする。
 (このメモをマシンへの入と思ってね。)

  そしたらメモ通りの交通機関に乗るよな?
  そのメモに出てくる交通機関集合がΓ。東海道新幹線JR京都線とかこれまたいろいろ。
  んで、最初は新幹線新大阪についたら京都線っていうように、その状態ごとに参照する交通手段がΣ。

  δはそれを式で書いただけ。
  δ(東京, 新幹線)=新大阪  δ(新大阪, 京都線)=大阪って感じ。
(省略しています。全て読むにはこのリンクをクリック!)
42 : ななしのよっしん :2013/05/29(水) 18:44:19 ID: sylco5qXED
>>sm18847458

この動画の終わりで言われる通りの数え方を
数分で済ませるアルゴリズムってどんなのなの?
43 : ななしのよっしん :2013/06/02(日) 20:51:30 ID: HWu6D5SJ1k
>>42
「ZDD」で検索すると出てくる
44 : ななしのよっしん :2013/06/02(日) 21:05:05 ID: aJdhIHexGc
以前Javaコンパイラのサンプルで、ソートするアルゴリズム
速さを視覚的に較するサンプルがあったのを思い出したが、
ああいう視覚的なものを子供のころから何気なく見せておけば
将来天才になったりするんだろうか
45 : ななしのよっしん :2013/06/02(日) 23:08:34 ID: 8yj1rlXi0C
初めての人にも気持ちが伝わるように配慮されててよい記事だと思います. しかし多少正確性を書く部分がありますので補足しますと,東京大阪にいけるかを判定するのは線形でできますし,最短経路をめるのも有名なダイキストラ法というアルゴリズムがあります. 
46 : ななしのよっしん :2013/08/13(火) 17:53:31 ID: 3sha79MaOD
インド地の件で花京院思い出したわ
47 : ななしのよっしん :2013/11/23(土) 03:32:48 ID: rPJro5lQaG
が初めて触って理解したアルゴリズムバブルソートだったな。あの頃はオブジェクト指向を理解するのに大変だったな。
48 : ななしのよっしん :2013/12/18(水) 15:52:44 ID: I1JNR4tLSx
「手続き」ってのはプログラム作る時は確かにそうなんだけど、
プログラムを使う・遊ぶ側になると
「思考パターン」や「行動パターン」に近いイメージになるなあ。
ゲームとしてアルゴリズムという言葉が使われる場合はそんな感じ。
49 : ななしのよっしん :2014/02/14(金) 22:21:44 ID: 4hR+S0kzCG
最初の方はともかく
途中からWikipediaの記事かの如く
読みにくさ全開だな
  JASRAC許諾番号: 9011622001Y31015