hirax.net::Keywords::「計算量」のブログ



2011-04-11[n年前へ]

交差点の位置を調べる「計算量」を京都の町で考える!? 

 京都の町では、多くの道が南北もしくは東西の方向に走っています。その結果、ほとんどの交差点は「直交する2つの道」により生まれ、そして、そんな交差点には「直交する2つの通りの名前を足された」名前が付けられるのです。

 だから、「南北という方向軸(=道は東西に走る)」をX軸として、「東西という方向軸(=道は南北に走る)」をY軸とすれば、すべての交差点はXY座標で示すことができることになります。だから、京都の交差点は「四条河原町(X=四条,Y=河原町)」とか「四条烏丸(X=四条,Y=烏丸)」とか「烏丸御池(X=御池,Y=烏丸)という具合に直行する2軸の座標値、すなわち通りの名前で表すことができ、その通りの名前を聞けば、どの場所に位置する交差点であるかが簡単にわかる、というわけです。XY座標で示される京都市街は、まさに「理系の散歩道」のために作られたような街、なのです。

京都の街で「非ユークリッド幾何学」を体感しよう!?
 そんな町で便利なことは、「記憶力に乏しい人でも交差点の場所がすぐわかる」ということです。

 もしもN本の東西の道と南北の道があるとしたら、交差点の総数はN^2ということになります。ということは、交差点の名称から場所を調べるための計算量は、O-記法で示すならO(N^2)もある、ということになります。これは、記憶力に問題がある私たちにはとても多すぎる量…です。

 ところが、いわゆる京都の街のような命名法を使っている場合には、つまり、「交差点の名称は、直交するふたつの通りの名称を結合することで作る」というルールにもとづくのであれば、東西・南北それぞれN本の通りの場所さえ覚えておけば、交差点名称から場所を調べるための計算量はたかだかO(2×N)≒O(N)にまで小さくなるのです。

 そんな計算量の削減・単純化ができるのは、「すべての道は直交する」という法則が、(「三条御池」というような特異点が生じることがない)京都中心街辺りではあるからです。

 交差点の信号機の下に掲げられた交差点の名称を長め、交差点の名称から場所を導き出すために必要な記憶量や計算量…そんなことを考え・楽しむことができるのが、「理系の散歩道」です。

 京都の街で、あなたの住む町で、「交差点の名称から場所を調べるための計算量」を考えてみることも楽しい」と思います。たとえば、あなたが知恵を絞れば、O(N^2)の計算が必要そうに思えるところをO(N log N)の計算量で済むようにすることができる…かもしれません。



■Powered by yagm.net