神様なんて信じない僕らのために

■[misc]「最短経路の本 レナのふしぎな数学の旅」を読みました

きしださんの日記で紹介されていたので、つい買ってみました。

2010-06-18 - きしだのはてな

きむら(K)さんに

「今まで読んでなかったんかい」

Twitter / 超電磁ねこきっく: @isoparametric 「今まで読んでなかった ...

と突っ込まれるくらい必読本でした。がはっ。

ということで、感想。

要するにグラフ理論の初歩を学ぶための本なのですが、

一般のプログラマ／エンジニアからしたらグラフ理論って、何か意味あるの？

って感じかもしれないです。

でも、

「最短経路を見つける」というアルゴリズムを書くことは結構あるんじゃないでしょうか？

最短経路を求める方法として、ダイクストラ法なんかが有名ですが、

ゲームなんかだとA*(AStar)アルゴリズムがよく使われます。

でも、これはアルゴリズムだけ知っていれば使えたりするので

実際に最短経路を求めるためにどのようなことをしているか？

というのは意外と知られていないのかなーとか。

あと俺は、プログラムを憶えたてのときは再帰で、経路探索を書いて、スタックオーバーフローしたりしてました。

……で、この本はその適切なアルゴリズムを提示するだけではなく、

「なぜ」というところを明らかにしており、

そもそもダイクストラ法がどういったアイディアから最短経路を求めているのか、

ということをきちんと段階を経て解説しています。

最短経路についてここまでしっかり書かれた本って他にないんじゃないかなー。

アルゴリズムって知っていて使えるだけじゃなくて、

理解するとさらに楽しいので

なんとうか、普通にお勧めです。

最短経路の本

• 作者: R.ブランデンベルク,P.グリッツマン,石田基広
• 出版社/メーカー: シュプリンガー・ジャパン株式会社
• 発売日: 2007/12/13
• メディア: 単行本
• 購入: 25人 クリック: 306回
• この商品を含むブログ (40件) を見る

Permalink | コメント(0) | トラックバック(1) | 15:21