<   2011年 06月 ( 20 )   > この月の画像一覧

ボーカロイド名曲リスト

YouTube で気になったボーカロイドの曲のリスト。皆独創的なのは、売れる売れないに関係なく本当に創りたいものを作っているから。初音ミク、ニコニコ動画がなかったら難しかった。

[GUMI] 会いたい : 人間の歌い方にそっくりなのに驚いた。曲もいい。
[鏡音リン] メランコリック : おそらく名曲。プロモーションビデオもいい。英語のコメントでも絶賛の嵐。ビデオに出てくるキリンが大人気のようだ。addicting で何度でも聞きたくなる。[初音ミク]
[巡音ルカ] ルカルカナイトフィーバー : ルカ、ルカ、ナイトフィーバー ♪ こずえ
[初音ミク] laven Polkka : 振り回されるネギが有名
[初音ミク] トルコ行進曲 : トルコ行進曲を初音ミクが歌うとこうなる?
[初音ミク] ワールドイズマイン : トヨタのカローラの宣伝で有名、「世界で..」という部分のフレーズのスケールが大きい。
[初音ミク・GUMI] マトリョシカ : カリンカ、マリンカ ...
[巡音ルカ] Just Be Friends : これを聞くと胸が苦しくなるが、美しい曲。プロモーションビデオピコ
[鏡音リン] 炉心融解 : 言葉にできない孤独感、苛立ち、自殺したら救われるのではないかという破滅的な願望を歌っているが、テンポの速いリズムと透明感のある旋律が心地よい。
[初音ミク] みくみくにしてあげる : みくみくにされてしまった。多分 ...
[初音ミク] 初音ミクの消失 : 超高速滑舌。ボーカロイドならではの超絶テクニック。
[初音ミク] ロミオとシンデレラ : 旋律がおしゃれ。どういうところがと聞かれても答えられないが ...
[初音ミク] メルト : メモするまでもなく有名。なぜか、初夏の朝の涼しい風をイメージしてしまう。
[MEIKO] 悪食娘コンチータ : 怖い。No panエスペイ
[初音ミク] 私は人間じゃないから : 歌詞が ... 。 曲がすばらしい。
[初音ミク] ハロ/ハワユ : 優しい旋律と歌声、英語のコメントでも高評価。初音ミクsoft で声質が優しくなっている。 踊ってみた
[巡音ルカ] ハッピーシンセサイザー : こんなコメントがあった。 --- う・・・うるさいわね!ロボットじゃなくてボーカロイドよ!ロボ­ットでもボーカロイドでも可愛いのは可愛いのよ!歌もいいのよ! --- 拍手。
[初音ミク] 指切り : ジャポネスク
[初音ミク・KAITO] サンドリヨン : サンドリヨンとはフランス語でシンデレラのことだそうだ。コゲ犬・むっち版にはびっくり。
[初音ミク] 君をのせて : 天使の歌声
[初音ミク] ハジメテオノト : アニメ・エクスポ2011 の最終曲
[初音ミク] Nyan Cat : これも初音ミク? Youtube 月間アクセスランキング世界1?
[初音ミク] Last Night, Good Night : レクイエム。とびきり美しい歌。
[初音ミク] Po pi po : 野菜ジュースのコマーシャルソング? 米国では一番人気。
[歌和サクラ] ブラック ロック シューター : ボーカロイドではないのですが。初音ミク版
[鏡音リン] す..すき..大好き : 気持ちが高まっていく終盤の部分が圧巻。
[初音ミク・巡音ルカ] ワールスエンド・ダンスホール : ホップステップで踊ろうか!! 何て格好いいんだ!!
[ヤマイ(初音ミク)] えっ?あぁ、そう。 : CDが出た。初音ミク曲のカバー
[初音ミク] 家に帰ると妻が必ず死んだふりをしています : これを歌うミクの声が天使に聞こえる。
[初音ミク] ペテン師が笑う頃に : 暗くて、汚くて、かっこいい。
[初音ミク] 初音ミクで「ネギの歌」 : 初音ミクはネギ好き。スーパーマリオの曲
[弱音ハク] オワタ☆レクイエム : 弱音ハクは鬱状態のミク?
[初音ミク] くるっと・おどって・初音ミク : ケロロ軍曹のエンディングを初音ミクが踊ってみた。
[3DCG] くるっと・おどって・初音ミク [ねんどろいど] : ケロロ軍曹のエンディングを初音ミクが踊ってみた。3DCG版。
[重音テト] おちゃめ機能 : いきなりハイテンションのボーカルが始まるのが楽しい。[こずえ×みりん]のダンスからこっちへ来た。
[初音ミク・巡音ルカ] magnet : Mikunopolis 2011 の中で歌われていなかったという不満が多かった。古典的名曲。
[ボーカロイド] 人柱アリス : 蠱惑的な悪夢をみているような。海外でも人気が高い。
[初音ミク] Soar : 背中に装着するタイプのジェットエンジンで空を飛び回ったらこんな感じになる?
[鏡音レン] パラジクロロベンゼン : この歌に意味はないよ。この歌に罪はないよ。この歌の意味はベンゼン。
[GUMI] モザイクロール : 愛したっていいじゃないか。
[初音ミク Append] Hirari, Hirari : 癒される。
[初音ミク] Cardioid : 眠れない夜に聞く歌。ゼフィリア・バージョンも。
[初音ミク] シューベルトのアヴェ・マリア : 聞き惚れてしまった。ドイツの人も幸せになったとか。Ave MariaPavarotti
[初音ミク] むかしむかしのきょうのぼく : だからバイバイ、昔々の今日の僕。Once Upon A Me
[初音ミク] 白い雪のプリンセスは : かがみよ、かがみよ、かがみさん。だからイントロは大切だ。
[VOCALOIDミュージカル] Alice in Musicland : ブラボー! ブラボー! ブラボー! 英語字幕付き
[GUMI] 隠れオタクでごめんなさい : 古典的な構成。なぜか植木等の歌を思い出した。でも、かわいい。Sorry for Being a Closet Otaku
[GUMI] マジで恋する5分前 : upbeat。胸キュン。参照: 『マジで恋する5秒前』
[初音ミク] バスルームガーデン : 声が初音ミクではないみたいな。Alice in Musicland の作者の作品。
[初音ミク] 脱げばいいってモンじゃない : だまれ!だまれ!だまれ!だまれ! .... 切ない。
[初音ミク] FREELY TOMORROW : 調声が凄い。人間みたい。
[GUMI] クワガタにチョップしたらタイムスリップした : これから君は、何度も何度も傷ついて ... 。 英語版
[初音ミク] ミラクルペインティング : ミラクルペインティング ♪~
[弱音ハク・亞北ネル] ツマンネ? : 亞北ネルの作品を見たくなったから。オワタPの作品にはボーカロイドにたいする愛を感じる。
[初音ミク] 深海少女 : 沈む、沈む。深く、深く。
[初音ミク] Vocaloid On Ice ~Miku Hatsune's ICE☆SHOW : フィギュアスケートを演じるミク
[初音ミク] 『リア充爆発しろ!』 : リア充爆発しろ! .... もうそんな年ではないのだけれど。「ねえ、ねえ」と言うミクの声がかわいい。
[初音ミク] 1925 : 意外、意外、いけるものね。かっこいい曲に、かっこいい歌詞、それに初音ミク。この辺がボーカロイドの魅力?
[初音ミク] BAD : マイケル・ジャクソンの曲のミクによるダンスカバー。惚れた。
[巡音ルカ] Scarborough Fair : なつかしい歌。ルカの英語力はなかなかのもの。Simon & GarfunkelSarah Brightman鏡音リン・レンLyrica
[巡音ルカ] Ding-Dong : 艶っぽいルカ。
[Miku Hatsuneo] glow : ネルのドラムスが格好いい。
[霊夢とリン] Volare : 髭面のリン?
[Touhou] Bad Apple : 夢をみているよう。
[初音ミク] ハロー プラネット : 悲しいけれど、希望を感じさせる物語。
[初音ミク] ルララ♪ : ねるどらむPのプロモーションビデオは癖になる。
[Charamell] Charamelldansen : すみません、ボーカロイド曲ではないのです。
[初音ミク] Dear : 耳にやさしい。
[初音ミク] 桜の雨 : 教室の窓から桜の雨 ... 。
[歌愛ユキ] a Wonder of Aisya : インストロメンタルもメロディーも新鮮。びっくりした。ボーカロイドには限界はないのか?PVの色彩が!!
[初音ミク] サラリーマンのうた : 一生懸命働いて家に帰ってただ寝るだけ ♪
[きゃりーぱみゅぱみゅ] PONPONPON : またまたボーカロイドではありません。中田ヤスタカです。[きゃりーれんれん]
[巡音ルカ・初音ミク] トゥインクル×トゥインクル : かわいいテクノポップ。こずえといくらのダンスカバーがある。
[巡音ルカ] ARPK : い~ちパカ、に~ぃパカ ... 。月葉
[鏡音リン] te-yut-te : Cute! 
[キキ] Nostalgic : メイコ曲のカバー
[初音ミク] Can't I Even Dream? 夢見てもいいじゃないの : 歌詞は聞き取れなくても美しい曲
[GUMI・鏡音レン] 嗚呼、素晴らしきニャン生 : 僕の夢は、ニャン、ニャン、ニャン
[初音ミク] マッシュルームマザー : マッシュルームって何なのだろう?
[初音ミク] 骸骨楽団とリリア : ジャズ
[巡音ルカ] CORRUPTIONGARDEN-3DPV : PVがすごい
[GUMI Whisper+歌愛ユキ] 君とまた、会える日まで。: エキゾチック
[巡音ルカ] 時のオルゴール(Music Box of Time) English Subbed : レトロな感じは嫌いじゃない。
[初音ミク] Souvenir : 不覚にも泣きそうになった。
【IA】メテオ : 物語性がある。ビデオはニコ動で見るともっと感動的。
[PR]
by tnomura9 | 2011-06-28 07:32 | ボーカロイド | Comments(0)

メランコリック

単なるメモのリンク

メランコリックを踊ってみた

メランコリック

メランコリック合唱 Tianshi のメランコリック Melancholic with English Subs

日本語の「可愛い」は KAWAII という国際語になっているらしい。確かに色っぽいというのとも子どもがかわいらしいというのとも違う女の人の魅力をあらわす用語で、日本人が発見した分類らしい。ロリータファッションは、フランスでは顰蹙ものだそうだ、センスの良さを追求するあまり、フランスの若者は単色のシンプルな服装になってしまうとTVで報道していた。しかし、実際にはゴスロリの服は、若い女の子には密かに人気があるということだった。

アメリカのトヨタ自動車が宣伝のキャラクターに初音ミクを採用したり、ロサンゼルスのアニメエクスポで初音ミクのライブがあると聞いて、一体どういう事なのかとYouTube界隈をさまよってみた。いろいろ見聞きしているうちに、現代のネット上の若者の音楽やファッションに対するセンスが面白くなってのめりこんでしまった。

こういう感覚は昔からあった(たとえば女子高生のルーズソックスなど)のかもしれないが、いま、初音ミクと動画サイトというメディアを得て、爆発的に発展しつつある。また、その潜在的パワーは十分経済的な効果も期待できうるものになろうとしているのだろう。もちろん、そのお膳立てをするのは大人だろうが、この新しい動きをきちんと把握していないとせっかくの宝を持ち腐れにしてしまうかもしれない。

愛川こずえの属する Danceroid もせっかく「愛川こずえ」と「いとくとら」という才能を抱えながら、AKB48の真似をして制服を着せて群舞の中で歌ったり踊ったりさせている。おじさんたちが過去の成功の法則にしがみつく限り、せっかくの宝を錆びつかせてしまう可能性は大いに高い。経済的な成功は後からついてくるものだとしっかり我慢して、未知の分野の動きを観察するくらいの余裕を持つのが立派なオトナなのではないのだろうか。

ボーカロイド関係の動きが、著作権がらみで変な動きになっているような気がする。Linux はソフト自体はフリーだがそれに関連する多くの収益事業を生み出している。自由なアクセスによって成長している分野に下手に権利関係の制限を与えると、その爆発的な成長力を阻害して結局は得るものも得られなくなってくるかもしれない。権利を守ったときの利益と、権利を緩めたときの成長による利益を予測して比較するのは不可能だろうが、慎重に検討する必要があるのではないか。
[PR]
by tnomura9 | 2011-06-26 13:57 | ボーカロイド | Comments(0)

World is mine を歌ってみた。

初音ミクのホログラムのライブで歌われた『World is mine』。音域が広すぎて歌えなさそうな歌だが、信じられないことに色々な人が歌っている。

以下はいろいろな歌い手の歌へのリンク。

うさリツカ花たんちょうちょガゼルベェェェェジュ

人間やる気になれば不可能に見えることもできるようになるのだなとびっくりしたが、ついに、男の人が女の人の音域で歌う両声類という歌い手も現れてしまった。

ピコGero。 ..... 両声類ではないけど .... うさYamai
ちなみにオリジナルは、これ

おまけ

『サンドリヨン』(こげ犬・むっち)
[PR]
by tnomura9 | 2011-06-26 07:27 | ボーカロイド | Comments(0)

ルカルカナイトフィーバー

ルカルカナイトフィーバー』はSAM作曲によるボーカロイド巡音ルカの歌だ。

ボーカロイドは音域を広げやすいので、人間が歌うのは不可能ではないかと思っていたが、実谷ななが歌っている(『ルカルカナイトフィーバー』を歌ってみた)。さすがに、高音部はファルセットになってしまっているが、聴き応えがある。人気が出たのでCDも発売されているようだ。

この実谷ななのカバーに、当時高校生だった愛川こずえが振り付けをつけて踊っている(『ルカルカナイトフィーバー』を踊ってみた)。手足の速い動きや、ポーズの美しさ、体のバランスのよさが、他の踊り手とは一線を画している。

ボーカロイドの歌が発表されると、一斉にいろいろな人がカバーをしたり、プロモーションビデオを作るので、そのうち名作と言えるものも現れてくる。こういうのを「初音ミク現象」とでも言えるのではないだろうか。版権などがはっきりしない中で、いろいろな人が自由にアイディアを持ち寄ってワイワイやっているうちに思いも寄らないものが出来上がってくる。

ボーカロイドを使って素人が、素晴らしい作品を世に知らしめるというのは実際には難しいかもしれないが、ひとつのアイディアを色々なひとが発展させるというこの自由なやり方はなくならないで欲しい気がする。

イノベーションは「自由」という乗り物に乗って進んでいくからだ。

おまけ

恋愛サーキュレーション踊ってみたこれも ... 。

さらに...

ルカルカナイトフィーバー比較版
[PR]
by tnomura9 | 2011-06-24 12:52 | ボーカロイド | Comments(0)

三女神降臨 Kalafina

今年の7月にロサンゼルスで開催されるアニメエキスポに、アニメソングの Kalafina というグループが出演するというのをネットのニュースで見た。不思議な名前のグループで聞いたことがなかったので検索してみた。次のリンクをたどってもらえばPVを鑑賞できる。

Youtube Mix for Kalafina

女性のボーカル3人のユニットで、中世ヨーロッパ風の旋律を歌っている。声の美しさや歌唱力が見事で、ハーモニーが素晴らしい。音程やリズムが正確だし、息つぎの時の呼吸もきちんと殺している。長音も揺れることなく安定して伸びやかに続く。3人がそれぞれの旋律を主張し合うような複雑なハーモニーが歌に立体感を与えていた。エキゾチックな旋律やリズムと相まって、しばし、陶然と別の世界をさまよっている気分になった。

これが、アニソンとして歌われているのだろうか。驚いた。

Kalafina についての英語のブログも漁ってみたが、概ね好評だった。あるブログには、彼女らの歌を評して、neo-classic gothic pop と書いていた。日本語に訳すと、新古典的、ゴシック調ポップとなるのだろうか。

よく考えたら、いきなりこのようなジャンルの歌のコンサートを開いても、あまり聞く人はいないのではないかと思う。しかし、最初に人気のアニメの主題歌やエンディングとして聞いていたら、抵抗なくその世界観に入り込むことができ、やがて虜になってしまうのだろう。サブカルチャーとしてのアニメと芸術性の高い音楽が融合できるいい例なのかもしれない。

日本のアニメが世界に受け入れられているのは、単なる好奇心からだけではないのだろう。その芸術性を無視して単に商業的な成功を狙ってもうまくいかないだろう。

おまけ

Kalafina はライブも凄い
[PR]
by tnomura9 | 2011-06-20 12:56 | ボーカロイド | Comments(0)

World is mine

TOYOTA USA が新しいカローラの宣伝に初音ミクを登用したというニュースは知っている人も多いだろう。

初音ミクとはDTMのユーザーが自作の歌を、人間のボーカルの代わりに歌わせることのできるコンピュータプログラムだ。発売当初はこのソフトがDTMソフトにしては例外的な売れ行きを示したので話題になった。また、パッケージに描かれた長いツインテールのキャラクターも評判になっていた。ところが、それが、いつの間にか、トヨタの新車のキャラクターに選ばれるまでになっていた。一体何が起こったのだろう。

初音ミクのソフトが登場して以来、多くの人が自作の歌や、初音ミクのキャラクターを扱った動画を作成しては動画サイトで発表してきた。そのうねりは次第に大きくなり、百万単位のアクセス数を記録するような作品も出てきている。そうして、ついに、初音ミクという架空のキャラクターのホログラムと実際の人間がコラボするライブステージまで登場してきた。そのひとつが次の動画だ。

World is mine

ホログラムの歌に熱狂する実在の人間たちの様子が奇妙といえば奇妙だが、オタクの一風変わった活動と片付けられないものがある。Youtube に発表されたこれに類するボーカロイドのプロモーションビデオを見ると、その質の高さと、楽曲の新しさに驚くだろう。今までに聞いたことのない曲、見たことのないビデオ影像があふれているのだ。

この記事でそれらについて感想を述べるには、あまりに多くのものがあり整理できないが、ボーカロイドというコンピュータプログラムと作品を発表するための舞台を提供する動画サイトが起爆剤となって、今までにない才能の開花の動きが日本で起きつつあるのではないかという気がする。この動きが他の国ではなく日本にだけ顕著なのは、他ならぬこの初音ミクというソフトが存在しているからなのではないだろうか。

初音ミクのホログラムライブは、7月にはロサンゼルスでもトヨタUSAのスポンサーで開催されるそうだ。既にチケットは完売らしい。米国民がこれをどう受け取るのか危ぶむ声も多いが、Youtube に転載されているニコニコ動画の作品のヒット数を見ると、ひょっとしたら面白いことが起きるかもしれないという気もする。
[PR]
by tnomura9 | 2011-06-19 17:37 | ボーカロイド | Comments(0)

探索 その3

グラフの探索のプログラムの仕組みがどうしても気になるので、テストプログラムを作って試してみた。

gr = [(1,2),(1,3),(1,4),(2,5),(3,5),(3,6),(4,7),(5,1),(6,7),(6,8),(7,9),(8,4)]

find_next gr k = map snd $ filter (\n -> fst n == k) gr

search gr p0 p1 path
  | p0 == p1 = [reverse (p0:path)]
  | otherwise = concat $ map (\p -> search gr p p1 (p0:path)) [ x | x <- find_next gr p0, not (x `elem` path)]

実行例

Main> search gr 1 4 []
[[1,3,6,8,4],[1,4]]

これを手作業でトレースしてみる。find_next gr 1 => [2, 3, 4] だから、
search gr 1 4 [] => concat [search gr 2 4 [1], search 3 4 [1], search 4 4 [1]]

find_next gr 2 => [5] だから、
search gr 2 4 [1] => concat [search gr 5 4 [2, 1]]

find_next gr 5 => [1] だから、ノード1は path = [2,1] に含まれてしまうので、
search gr 5 4 [2,1] => []

したがって、
search gr 2 4 [1] => concat [search gr 5 4 [2,1]] => []
search gr 1 4 [] => concat [[], search 3 4 [1], search 4 4 [1]]
=> concat [search 3 4 [1], search 4 4 [1]]

と、探索がバックトラックするのが分かる。トレースをもう少し続けてみよう。
search 3 4 [1] => concat [search gr 5 4 [3,1], search gr 6 4 [3,1]]
search gr 5 4 [3,1] => concat [search gr 1 4 [3,1]] => []
search gr 6 4 [3,1] = >concat [search gr 7 4 [6, 3, 1], search gr 8 4 [6,3,1]]

だから、結局
search 3 4 [1] => concat [[], [search gr 7 4 [6,3,1], search gr 8 4 [6,3,1]]
=> concatMap [search gr 7 4 [6,3,1], search gr 8 4 [6,3,1]]

のようになり、探索の失敗した枝が次々に抜け落ちてバックトラックされるのがわかる。探索の失敗したルートを省略するようにして探索を続けると、
search gr 7 4 [6,3,1] => concat [search gr 9 4 [7,6,3,1]]
=> concat [concat [[]]] => []
search gr 8 4 [6,3,1] => concat [search gr 4 4 [8,6,3,1]]
concat [[[1,3,4,6,8]]] => [[1,3,4,6,8]]

したがって、
search 3 4 [1] => concat [[1,3,4,6,8], search gr 6 4 [3,1]]

search gr 6 4 [3,1]の探索がすべて失敗すると、serach gr 6 4 [3,1] => [] だから、結局

search 3 4 [1] は [[1,3,4,6,8]] を返す。したがって、 最初の検索式は次のように展開される。

search gr 1 4 [] => concat [[[1,3,4,6,8]], search 4 4 [1]]

search 4 4 [1] について同じように展開して、search 4 4 [1] => [[1,4]]

となるから、結局
search gr 1 4 [] => concat [[[1,3,4,6,8]], [[1,4]]] => [[1,3,4,6,8], [1,4]]

という結果が得られる。プログラムをトレースすると次々に探索の失敗した経路が脱落していく様子が分かるが、どうしてそうなるかを理解する鍵は次の再帰式だ。言い換えると、次の式を理解することが、探索プログラムの動作を理解する鍵になるということだ。

search gr p0 p1 path = concat $ map (\p -> search gr p p1 (p0:path)) [ x | x <- find_next, not (x `elem` path)]

前回の記事とも重なるが、ノード a から探索可能なノードのうち path に含まれない物を [b, c, d] であると仮定してみる。そうすると上の式は次のように展開できる。

search gr a p1 path = concat [search gr b p1 (a:path), search gr a p1 (a:path), search gr d p1 (a:path)]

このとき search gr a p1 path がどういう値を返すのだろうか。

まず、上の例の search gr b p1 (a:path) について考えてみる。b == p1 のとき、つまり、目的のノードが見つかったとき、search gr b p1(a:path) => [reverse(p1:b:path)] が戻される。また、ノード b に連絡するノードが見つからなかったとき、search gr b p1 (a:path) は、[] になる。したがって、concat [ search .. ] の引数のリストが皆確定的な値、たとえば、[[], [path1], [path2]] のとき、

search gr a p1 path => concat [[], [path1], [path2]] => [path1, path2]

となる。search gr b p1 (a:path) がすぐには確定しない場合、次々に関数の展開が起きるが、最後には、[] か [path(n)] のリストの値となって戻値が帰ってくる。したがって、search gr a p1 path は、その下層の関数の値のうち、探索できたパス全てからなるリストを戻値として返すことになる。ノード a の戻値は、ノードa の上層のノードの concat [ .. ] のリストのメンバーとなるから、ノード a の上層のノードはノード a 以下のノードの全ての情報を引き継ぐことになる。

このように search 関数の戻値が確定するまで、出発点のノードから次々にグラフの経路の検索が行われ、全ての経路を検索した結果がリストとして戻されることになる。

上の説明がうまく説明になっているか自信がないが、とにかく、これだけの複雑な操作を2,3行でプログラムできてしまうのがうれしい。
[PR]
by tnomura9 | 2011-06-18 08:14 | Haskell | Comments(0)

探索 その2

Haskell のお勉強 - 探索のサンプルコードの深さ優先探索のプログラム [code 1] の骨格は3つの部分からなっている。

1. グラフの定義 : g0
2. グラフ g0 の k 番目のノードの先にあるノードを取り出す関数 : find_next k gr
3. グラフ gr の p0 番のノードから p1 番のノードに至る経路を検索する関数 : dfs gr po p1

どの部分も非常に簡潔に記述されているので、全体の構成がよく見通せる。

それでは1番のグラフの定義からコードを追ってみよう。グラフはまずグラフ型の宣言から始まっているが、新しい型を定義するわけではなく、次のようなリストの構造に type 宣言で別名をつけているだけだ。グラフは次のようなタプルで構成されている。

g0 = ( [(1,2,3,4,5,6,7,8,9)],
     [(1,2),(1,3),(1,4),(2,5),(3,5),(3,6),(4,7),(5,1),(6,7),(6,8),(7,9),(8,4)] )

つまり、go = ( ノードのタプルのリスト, ノード間の矢印を表すタプルのリスト) だ。数字はノードを表し、数字のペア (1,2) はノード1からノード2への矢印があることを示している。このように、ノードと矢印のペアのタプルを作れば、グラフをプログラムで扱えるように記述できる。非常に簡単だ。

2番目の関数 find_next k gr はグラフ gr の k 番目のノードの次のノードを全て検索する関数。これも、たった1行でできる。

find_next k gr = map snd $ filter ((==k) . fst) (snd gr)

冒頭から読んでいくと、map snd (List) だから、リストの要素であるタプルの2番目の要素を取り出して、そのリストを作っている。つまり、矢印のリスト[(1,2), (1,3)] などが与えられたらそれから [2, 3] のように、矢印の先にあるノードの番号のリストを作る。

$ filter ((==k). fst) (snd gr) は snd gr つまり矢印のリスト [(1,2),(1,3), .. ] から ((==K) . fst)) つまり、タプル (1,2) の1番目の要素が k であるものを filter で抜き出している。たとえば、filter ((==1).fst) (snd gr) => [(1,2), (1,3), (1,4)] だから、

find_next 1 gr => map snd [(1,2),(1,3),(1,4)] => [2,3,4]

だ。

3番目の関数 dfs gr p0 p1 がグラフ gr のノード p0 から p1 までの経路を探索するプログラムだ。

dfs gr p0 p1 = dfs_aux gr p0 p1 [] なので、dfs は dfs_aux の第4引数を隠蔽したシンタックスシュガーである。したがって、経路探索の本体は dfs_aux gr p0 p1 path ということになる。dfs_aux の定義は次のようになっている。

dfs_aux gr p0 p1 path =
  | p0 == p1 = return (reverse (p0:path))
  | otherwise = msum $ map (\p -> dfs_aux gr p p1 (p0:path)) [ x | x <- find_next p0 gr, not (x `elem` path)]

上のコードには、return と msum という見慣れないキーワードがある。これには、モナドを利用したあっと驚くような仕掛けがあるのだが、それは原典を読んでもらうとして、探索のメカニズムに集中するために上のコードを次のように変えてみる。

dfs_aux gr p0 p1 path =
  | p0 == p1 = [ reverse (p0:path) ]
  | otherwise = concatMap (\p -> dfs_aux gr p p1 (p0:path)) [ x | x <- find_next p0 gr, not (x `elem` path)]

コード部分はたったの2行しかない。上のコードで最初に気になるのは path という余分な引数がなぜ必要なのかということだ。gr はグラフのデータだし、p0 は出発点のノードで、p1 は到達点のノードだが、path は一体何なのだろうか。実は、この余分な引数はこの関数が末尾再帰型の関数であることを示している。

再帰型の関数は、次の階乗の計算に見られるように自分自身を呼び出す。

fact n = if n == 0 then 1 else n * fact (n-1)

しかし、これは途中の計算を保持しておくのにスタックを使わなければならない。階乗の計算を末尾再帰で記述すると次のようになる。

fact n result = if n == 0 then result else fact (n-1) (n * result)

実際、このプログラムがきちんと働くのは確かめることができる。

Hugs> fact 5 1 where fact n result = if n == 0 then result else fact (n-1) (n * result)
120

これだと、中間の結果を引数 result に引き継いでいくことができる。Haskell のような関数型言語では変数への代入をすることができない。これは、状態を保持しなければならないようなプログラムでは非常に不便だ。しかし、末尾再帰を利用することで、計算の途中経過を引数の値として保持することができる。

グラフの経路の探索では、探索が失敗したとき元のノードに戻るバックトラックを行わないといけない。しかし、バックトラックを行うためにはもどるためのノードの情報が残っていなければならないが、変数への代入ができないと難しい。そこで、末尾再帰型関数の引数のなかに探索中の経路の状態を保持させるようにするのだ。

dfs_aux に話を戻すが、ガードの条件が p0 == p1 のとき、つまり探索が成功したときは、それまでの経路の記録が path 変数に保持されているのでそれを戻値として返す。ノードの情報を保持するときにリストの頭から付け加えているので、reverse 関数で順序を逆にしておかなければならない。

p0 == p1 でない場合には、p0 から移動可能なノードを次の内包的定義で検索する。

[ x | x <- find_next p0 gr]

ただし、同じノードに戻ったりしてらループを永遠にたどることになるので、path に含まれているノードは除外しないといけない。したがって、上の内包的定義は次のようになる。

[ x | x <- find_next p0 pr, not (x `elem` path)]

述語 x `elem` path はリスト path の要素として x が含まれていれば真となる。その否定だから、x は path に含まれないものだけを選び出すことになる。

いま仮にそのようなノードのリスト[a, b c] が得られたとしよう。そのとき、

concatMap (\p -> dfs_aux gr p p1) [ a, b, c ]

では、concat [ dfs_aux gr a p1, dfs_aux gr b p1, dfs_aux gr c p1]

が実行される。この例でノード a で次に移動するノードがないときは、def_aux gr a p1 は [] リストを返す。なぜなら、Haskellでは、(\p -> dfs_aux gr p p1) [] は戻値 [] を返すようになっているからだ。dfs_aux gr b p1 の戻値もやはり [] で、dfs_aux gr c p1 がパスの値 [[d, e, f]] を返したとするすると、

concatMap (\p -> dfs_aux gr p p1) [a, b, c] => concat [[], [], [[d,e,f]]] => [[d,e,f]]

という結果になる。

dfs_aux の動作を正確に理解するには、この関数の展開を順に追っていく必要があるが、上に述べたことでもなんとなくその動作が感覚的に分かるだろう。あとは、動かしてみて結果オーライなら多分動いているのだ。

経路探索のプログラムを正確に理解するのは難しくはないが、面倒くさい。上のプログラムの雛形を動かしてみて動作が飲み込めたら、色々なグラフに使って応用することができる。そうすれば、Haskell を使えば探索問題のようなものは非常に簡潔にプログラムできるのがわかってうれしくなるだろう。
[PR]
by tnomura9 | 2011-06-16 07:24 | Haskell | Comments(0)

探索

Haskell を勉強して、高階関数便利だなと思っても、実際何に使えるのかと考えるとなかなか思いつかない。そのひとつの答えが、Haskell のお勉強というページにあるような気がする。

このWebサイトの探索という記事をみると。グラフの探索が、Haskell では非常に簡単に記述できることがわかる。

グラフとは何かと言うと、要するに丸印と丸印を線で繋いだものだ。例えば、建築の工程をパート図で表したもののように、ひとつの工程が丸印で表され、次の工程に矢印で結ばれているような図形のことだ。丸印と丸印が単なる線で結ばれているのではなく、矢印で方向づけられているものを有向グラフという。

この有向グラフのある丸印(ノード)から別の丸印(ノード)までの経路を検索するのが、探索だ。前回の川渡り問題もやはり、探索の問題の一種だ。また、パート図からある工程からある工程までの最短時間を調べるのも、探索のアルゴリズムが使われる。

このように、探索というアルゴリズムは、応用範囲が広い。Haskell でそれが簡単に記述できるとしたら便利だろう。

Haskell のお勉強の探索のページには、この探索のアルゴリズムが Haskell で非常に簡潔に記述されている。簡潔すなわち理解しやすいというわけではないが、一旦理解してしまうと、あれにもこれにも応用したくなってくる。

気の早い人は、このページを読んで理解してしまうとよいが、管理人自身、紹介してあるコードを読んでも最初は何のことか良く分からなかった。

Haskell で探索のアルゴリズムをさくさくかけるようになれば、いろいろな使い道がありそうなので、次回の記事からは、このページのコードを攻略してみたい。
[PR]
by tnomura9 | 2011-06-15 18:38 | Haskell | Comments(0)

川渡りパズル

川渡りパズルを Haskell で解いてみた。川渡りパズルというのは、次のような問題だ。

川岸に狐とガチョウと豆の袋を持った農夫がいる。農夫が目を離すと、狐はガチョウを食べてしまうし、ガチョウは豆をついばんでしまう。ところで、川を渡るのに一艘の小舟があるがこれは、農夫と荷物をひとつしか運べない。狐がガチョウを食べたり、ガチョウが豆を食べたりしないように、これらを川の向こう岸に船で運ぶにはどうするかというパズルだ。

ネットを方々検索して作ったのが次のプログラムだ。

import List

data Member = Fox | Goose | Beans
  deriving (Show, Eq, Ord)

data Farmer = LeftSide | RightSide
  deriving (Show, Eq)

data State = State {left :: [Member], right :: [Member], farmer :: Farmer}
  deriving (Show, Eq)

beginState = State {left = [Fox, Goose, Beans], right = [], farmer = LeftSide}

goal s = length (left s) == 0

forbidden xs = (elem Fox xs && elem Goose xs) || (elem Goose xs && elem Beans xs)

available s = (farmer s == LeftSide && (not (forbidden (right s)))) || (farmer s == RightSide && (not (forbidden (left s))))

updateLeft s = filter available ([State {left = delete x (left s), right = sort (x : right s ), farmer = RightSide} | x <- left s] ++ [State {left = left s, right = right s, farmer = RightSide}])

updateRight s = filter available ([State {right = delete x (right s), left = sort (x : left s), farmer = LeftSide} | x <- right s] ++ [State {left = left s, right = right s, farmer = LeftSide}])

findNext s
  | farmer s == LeftSide = updateLeft s
  | otherwise = updateRight s

search s path
  | goal s = [reverse (s:path)]
  | otherwise = concatMap (\x -> search x (s:path)) [x | x <- findNext s, not (elem x path)]

きちんと説明できるほど理解しているわけではないので、とりあえず実行例。

Main> mapM putStrLn $ map show $ head $ search beginState []
State {left = [Fox,Goose,Beans], right = [], farmer = LeftSide}
State {left = [Fox,Beans], right = [Goose], farmer = RightSide}
State {left = [Fox,Beans], right = [Goose], farmer = LeftSide}
State {left = [Beans], right = [Fox,Goose], farmer = RightSide}
State {left = [Goose,Beans], right = [Fox], farmer = LeftSide}
State {left = [Goose], right = [Fox,Beans], farmer = RightSide}
State {left = [Goose], right = [Fox,Beans], farmer = LeftSide}
State {left = [], right = [Fox,Goose,Beans], farmer = RightSide}

パソコンを使わないで答えを出す時間より、プログラムを作る時間のほうが何倍もかかってしまった。実際、人間の頭脳がなんとなくこなしてしまう仕事を、プログラム化するのにずいぶんいろいろな条件を考えなくてはいけなかった。普段何気なくやっている推論が実はいろいろな条件を上手に使いこなしていたのだと、いまさらながら脳の推理能力の優秀さに気がついた。
[PR]
by tnomura9 | 2011-06-13 23:44 | Haskell | Comments(0)