(広辞苑より)2011年10月14日金曜日オフィスビル内の最短経路Tweet現在のオフィスでは、エントランスからどの通路を通るのが最も近いのか、未だに話題になることがある。エントランスからオフィスにつながるエレベータまでの道が二通りあり、どちらも似たような距離なので同じオフィスに行く人達なのにそこで別々になってしまうこともしばしば。左の図が問題のフロアなんだけど、エントランスから青丸で示したエレベータまで行く必要がある。コンピュータに解かせてしまえばいいじゃない、ということでプログラムを作って最短経路と正確な距離を調べてみた。定規で測ったほうが早いという意見は聞こえません。画像で与えられた迷路に対し2点間の最短経路を求めるというブログ記事で、画像から直接最短距離を求めるプログラムを書いたことがあるので、まずはそれを使って調べてみた。図面の邪魔な文字だけ消して、あとはスタート地点とゴール地点の座標を引数で指定するだけだから簡単なんだけど、これだと問題があることに気がついた。連結成分ラベリング)で移動できる領域を調べて、それをA*で解いているのだけど、隣接するノード(ピクセル)を上下左右斜めの8方向のみで調べているから正しい距離を出すことができないのだ。実際に作成した図は以下のようにギザギザになってしまい最短ルートを通らない。通り道の分岐や方向が変化する箇所をノードにしてそれをA*で求めることにした。全部で10個のノード(画像のピクセル座標で指定)を作って調べたところ、以下のような結果になった。左側を通る通路の距離が324.53、右側を通る通路の距離が322.51となり僅かに右側の通路のほうが近かった。右側の方は途中でフロア案内と少し重なるし、6つあるエレベータのどれを使うかによっても結果が変わってしまうぐらいなので、実質的には同じ距離といってしまっても差し支えないと思う。結局、それぞれの距離にはほとんど差がないので、結論としては「好きな方を使え」ということになるだろう。自分は広い通路の方が好みなので右側の通路を利用している。最後にソースコードとその使い方を示しておく。隣接ノード番号リスト"としてノード数の分だけ記述する。ノード番号は0から始まり、先頭行と最終行のノードはそれぞれスタート地点、ゴール地点を表している。フロアの図面画像をinput.pngとして渡すと、最短距離のルートが書きこまれた画像をoutput.pngとして出力する。ソースコードが間違っていたので修正。今回の結果には影響なし。Engineメッセージボード*当ブログに関する意見や要望などにお使いください。Googleアカウントでログインすることで書き込みができます。Twitterへの送信を同時に行うこともできます。ストリートビューで散歩*Googleマップのストリートビューを利用して散歩をするWebアプリです。ストリートビューとマップを分割してマーカーを視界タイプに変更することで使いやすくしてあります。APIを利用したグラフ・チャート作成ウェブアプリです。クリック一つで簡単にグラフを作成できます。ブログ記事への貼り付けなどにどうぞ。OpenIDテスト*OpenIDによるログインのテストを行います。mixiであればクリック一つで、他のOpenIDアカウントであればそのURLを入力することでテストできます。一言コメント表示機能付きです。HTML文字変換*テキストで使われているHTML特殊文字をウェブで表示できるようにするための文字変換ウェブアプリです。プログラムのソースコードなどをブログ記事に貼り付けるときなどに便利です。短縮URLチェッカー*フィッシングサイト判別機能付き短縮URLチェッカーです。テキストボックスに変換したいURLを入力すればbit.lyの短縮URLが表示され、bit.lyの短縮URLを入力すればもとのURLが表示されます。展開されたURLがリンク付きで表示されますが、もしフィッシングサイトの疑いがある場合は警告が表示されます。Trendsの急上昇ワードをランキング順に表示します。Googleでのキーワード・画像検索やWikipediaによる用語の説明もあります。※GoogleがAPIの提供を終了したため、現在停止中です。自己紹介noxゲームを楽しむだけの余裕と感性は失いたくないnoxです。