検索サイトの設計

グラフの理論とウエブ
　　　オペレーションズ・リサーチで最短経路問題とか巡回セールスマン問題など有名なテーマがあるが、これらは線形計画問題の中でネットワーク問題といわれている。分かりやすい例として配送計画を見てみよう。小売店やコンビニなどの店舗への商品の配送は、配送センターから定期的に小型トラックなどで、小口商品の輸送を行う。各店舗の需要量は配送車の積載量に比べて少量であるために、配送車はまとめていくつかの店舗を順番に回り、商品を配送してセンターに戻るというサイクルである。

　　　どの配送車がどの店舗をどのような順番で回るのか、配送車の積載容量と各店舗の商品の種類と量を勘案して決める。組み合わせ方によっては配送距離や配送費用が変わるので、費用を最小にする場合とか、配送時間を最小にする場合とか、その時の状況に応じて最適な計画を設定しなければならない。この問題は、各配送車が積載容量の範囲内でどの店舗を担当すればよいかという問題と、割り与えられた店舗をどのような経路で配送すればよいかという二つの問題に整理される。与えられた制約条件内で、費用や時間を最小にするという線形計画問題に帰せられるから、最後は多元連立一次方程式を解く問題になる。変数が１０程度だとエクセルをうまく使うことで簡単に答えを出すことができる。

　　　店舗やセンターをノード(node)と呼び、ノードを結ぶ線をリンク(link)と呼ぶと、これらを繋ぐ線で表される図形をグラフ(graph)と呼ぶ。商品や情報のような流れを扱うグラフをネットワーク(network)という。このネットワークを扱う理論を数学ではグラフの理論という。ところでインターネットで使われているWWW(World Wide Web)もまさにこの配送計画のネットワークを大規模にした延長上にあることが直感的に理解される。１９９５年の夏にスタンフォード大学で出会った二人の学生が１９７３年生まれのラリー・ペイジとセルゲイ・ブリンで、ともに数学者を父にもつせいか、数学的興味はずば抜けていたという。

　　　ミシガン大学からきたラリーはこのWWWこそ地球上にある最大のグラフ構造であることを理解していた。小売店やコンビニなどの店舗への商品の配送は、配送センターから定期的に小型トラックなどで、小口商品の輸送を行う。各店舗の需要量は配送車の積載量に比べて少量であるために、配送車はまとめていくつかの店舗を順番に回り、商品を配送してセンターに戻るというサイクルである。さまざまな検索サイトはすべてこのような理論を使っている。
ツイッター
https://twitter.com/#!/goroh