湊慎一『超高速グラフ列挙アルゴリズム』

湊慎一『超高速グラフ列挙アルゴリズム－〈フカシギの数え方〉が拓く，組合せ問題への新アプローチ－』

フカシギの数え方のこの動画。

この動画で一躍有名になった列挙の問題を高速に解く「最新のアルゴリズム」ことZDDの解説書がこの本なんだけど、これは良い本でした。

ZDDの基本的なアイディアはこういうもの。「フカシギの数え方」ではグリッドの左上から右下への全経路を調べるわけだけれど、これの問題をまず「経路に使われたエッジの集合」の数え上げと定式化する。で、「辺1を使う・使わない」という選択肢によって分岐し、次に「辺2を使う・使わない」で分岐し……とやっていくと、高さが辺の数に相当する巨大な二分木ができる。ここから有効なもの（使うエッジの集合が実際にスタートからゴールまでをつなぐ一本の経路になってるもの）だけを使うような制約条件をかければ数え上げられるのだが、もちろんこのままだと巨大な二分木なんでどうしようもない。ただ制約条件の下では木を非常に簡潔なかたちに縮約できますよ、というのがZDD。もちろん、最初に巨大な木を作ってから縮約していくのでは意味がないので、初めからZDDを作っていく。

この本ではまず前半でこうした問題の概略を説明し、コアとなるデータ構造であるZDDと、その構成方法が説明される。さらに作者の作ったGraphillionというライブラリの簡単なサンプルコードもついている。このデータ構造は知らなかったので、ここがまず面白かった（ZDDやBDDはTAOCPの4Aでも触れられているらしい）。

本の後半は、パズル（ナンバーリンクやスリザーリンクなど）、電力図、路線図などの経路問題への応用の説明。こちらもGraphillionを使ったサンプルコードつき。いじわるな見方をすれば解法に応じた問題設定とも見えなくもないけれど（路線図の問題など）、全体的になかなか応用できる場面がいろいろありそうな雰囲気を醸し出している。

最後のアドバンストな話になると、一般的なZDDからフカシギの数え上げ方に向けての（定数倍の）最適化手法の説明や、頻出アイテムマイニングや文字集合の表現方法などのトピックにも触れられている。文字集合はトライ木をベースにしたDAWG (directed acyclic word graph)と本質的には同じになるらしい。でもZDDベースだと木の演算（合成や差分）が自然に表現できるから良いんだとか。うーんこれは本当なのかな（つまり、合成や差分はこの分野でできると嬉しいことなのか、DAWGでは難しいのだろうか）。まあこの辺はあまり追えてません。

良い本だなと思ったのは、まず（自分は）知らないデータ構造・アルゴリズムに関する話を解説していて、応用事例も含めて説明があるので、なかなか学びの多いから。ただ今んとこ自分は表面的に書いてあることを眺めただけなので、より細かい話は参考文献を読んだりサンプルコードを動かしてみたりといったことが必要かな、という感じですかね。

アベンジャーズ：エイジ・オブ・ウルトロン

→公式サイト
見たよ。

総評としては……そんなでもないかなぁ。アベンジャーズ第二期は全般的に低調という気がした。まあ単独映画で少しずつクロスオーバーが明らかになっていって集結という第一期の盛り上がりにはさすがにかなわない。あと今回の敵であるウルトロンが、またこういう感じか、ってなってしまう。

とはいえアクション映画としてはやっぱり見応えはあって、とくにソウルでのバトルはトリッキーな構成で面白かったかな。ブラックウィドウの活躍や、キャップの盾を使ったアクションが面白い。新キャラ二人もキーとなって活躍するし。新キャラ二人はアベンジャーズキャラではあるけれど、もとはX-MENなんですね。でもX-MENとマーベル・シネマティック・ユニバースは交わらないので、二人はX-MEN設定はなし。

ラストバトルは例によってわらわら出てくるロボット軍団との戦いだけど、一作目との違いは一般市民を避難誘導に優先順位を置いているところ。これでストーリー展開もアクション映画としての展開も幅が出ている。しかもウォー・マシンが参戦！　これは燃える。逆になぜファルコンは来ないのか納得がいかない。これ絶対ファルコンが活躍する場面ですよ。パーティには来てたのに……。あとこういうロボ軍団と戦うとなるとブラックウィドウはちょっと無理があるような。他の活躍シーンを作れば良かったのに。

全体的にブラックウィドウまわりのストーリーは今ひとつというか、そういうのはこの映画で望んでいるものなのだろうかという疑問がわく。ハルクの暴走もアクションとしてはすごいんだけど、ちょっと白けるんだよな……。アフリカあたりの展開は個人的にはちょっと今ひとつ。あれを大胆に削って2時間ぐらいにまとめたほうが良いような……。

なお今回のホークアイさんの見どころは矢を掴んで直接敵にぶっ刺すところ。射てよ！

あとどうでも良いツッコミですが、ウルトロン、しゃべるときに口がぐねぐね動くのが謎。お前ロボットだろ！　とツッコむのもまあ野暮なことですが……ロボがしゃべるときに目がチカチカ光るという映像表現を発明したサンライズは偉大だなと思いました。

アマゾンにKindle Singlesが来てる

なんかいつのまにやらKindle Singlesが日本にも来てるみたいですね。キンドルで短編〜中編程度の長さのものが読める。99〜399円くらいぽい。

4本ほど読んでみた。

パイオニア・アノマリーは、宇宙機パイオニアの軌道データを調べていた科学者が説明のつかない加速を観測し……という事件を追ったノンフィクション。
オチはちょっとガッカリだったけど、科学ノンフィクションとしてはなかなか面白かった。ノイズの多い大量の生データから、いかにして必要な情報を取り出して意味を見出すか、という統計処理的な話は、よくある科学のおはなしでは無視されがちだけれどけっこう大事な話なんだよなあ、というあたりもなかなか良いかな。

リスを実装する、は円城塔の短編小説。ヴァーチャル世界に生きるリスを実装する男の話。円城塔としては普通の話という気がする。まあまあ。短いのですぐ読めます。
私はヒゲ女は、自身の体毛の濃さにコンプレックスを感じている女性記者の人が女性の剃毛についていろいろ書いたエッセイみたいな話。ちょっと自分の体験談が長くて、うーんどうなんだろう……と思ったが女性だったらそこが読みどころなのかな。もう少し歴史的な話や異文化の話も盛り込んだほうが個人的には好みだったかと思う。訳は良いけど、個人的にはあんまり好きではないタイプ。でもオチはちょっと良かった。表紙がちょっと強烈です。
この街からは本谷有希子の短編。まあ普通に文学。こういうのに対する感度がないからかわからんが、可もなく不可もなく。

といったラインナップ。ラノベもあるし、エンタメもあるし、ノンフィクションもある。そこそこ良いような気がする。

ところで、いったいこのラインナップはどこから来ているのだろうか。少なくとも初期ラインナップで頼まなくても作家が書くということはないだろうから依頼して書いて（提供して）もらったのだろうけれど、誰が選んでるのか。校正みたいな編集業務は誰がやってるんだろう。

あとノンフィクションについては何故か日本の書き手はいまのところおらず、すべてアメリカからの翻訳のようだ。日本の作家については最悪作家から提供されたデータをそのまま流し込めば作れるのかもしれないけれど、翻訳の場合は、誰かが翻訳権を取得や作品選定、翻訳者のコーディネートのような仕事をしないといけないはず。アマゾン社内か委託の編プロでそういうのやってるのかな。そっちの仕組みのほうが興味深いな……。

GOTHAM シーズン1完結

→公式サイト, Google Play, amazon

『バットマン』世界の前日譚を描いたテレビシリーズ "GOTHAM" シーズン1が完結。全22話。いやー面白かった。

バットマン世界のことをよく知っているとマニアックな楽しみがあるんでしょうが、そうでなくてもちゃんと面白い。悪徳の支配するゴッサム・シティを舞台にしたギャングものとして話が成立している。

とにかくペンギンがいい。当初ギャング世界の下っ端っていうところから、殺されそうになってゴッサム・シティを追い出されながらも、なんとか舞い戻って知略と謀略でうまく立ち回りながらだんだん出世していくという展開。しかも当人は体を傷めつけられてちゃんと歩けないほどなので、ギャングの世界でも自分自身は強くなく、むしろ弱々しい感じであなどられている。そのわりに妙な愛嬌のあるキャラもいい味だしているし、演じているロビン・ロード・テイラーも良いなあ。ほとんどこいつ主人公じゃん、といった感じであった。

ほんとの主人公のはずの駆け出し刑事のジム・ゴードンも、まあ良いのですが、ペンギンのストーリーラインと比べると大きな筋立てがあまりなくて弱いかなあという感じ。ガールフレンドのバーバラの話とか、いろいろあるんですが……。

序盤はあんまり活躍しない、まだ子供のブルース・ウェイン（のちのバットマンね）も、シリーズ後半に行くにしたがって活躍の場が増えてくる。いかにもお坊っちゃんといった雰囲気があるのが良いところ。軍隊上がりで謹厳実直、ブルースを Master B と呼ぶアルフレッドもかっこよくてうまいコンビになっている。ただあんまりメインのストーリーとの絡みが薄いあたりは難点かな。

そういえばメインのストーリーには関わりが薄いけれどもバットマン世界では実はこいつは、みたいなのはけっこうあり、特にエドワード・ニグマ（のちのリドラー）などはちょくちょく話が出てくるわりにはいっこうにメインに絡まないので、見ていてもなんなんだろうなあという人はまあいるやもしれず。ぐぐればだいたいわかりますが。

まあ面白かった。おすすめです。