週に一回は書きますよ 月に4つ記事を書けばノルマは満たされます。
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

迷路のことを考えていたのは、迷路を利用してグラフを生成できないかと思ったからでした(突っ込み所だけど後にとっておいて。) 考えていたのは次のようなアルゴリズムです。

  • 空間に粗いグリッドを引いて、それに沿って迷路を作る。
  • 空間上にランダムに点を撒く。
  • 点と点とをつなぐ線分のうち、迷路の壁にぶつからないものだけを辺として採用する。

このアルゴリズムに到った経緯です。最短経路を求めさせる問題で、どんなグラフが適切か考えていました。 頂点と辺の数を決めてランダムに辺を渡すという方法が一番素直です。私はこの方法では満足できません。この生成方法だと始点と終点が近くなりがちなのです。もっと一般的なグラフ、もっと現実の問題に近いグラフ、それからもっと病的なグラフがほしいのです。

まず想定していたのは空間に点を撒いて近い点をつなげるアルゴリズムでした。これは適度にランダムなグラフができ、しかもスタートからゴールまで適度に距離があります。 しかしこれでは、場合によっては最短距離を求めるのがえらく簡単になります。たとえばゴールの方向がわかっている場合、大体その方向になるように向かうだけでほぼ最短距離になります。A*法が効きすぎます。

そこで迷路です。直進で最短距離に行けないのは迷路に決まっています。迷路に沿う形でグラフを作れば、スタートからゴールまで距離のある、しかも難しいグラフができるはずです。空間をどのくらいに区切って迷路を作るか、その中にどのくらいの頂点を撒くかはあまり考えていないものの、迷路はそれほど細かくないほうがいいような気がします。

ところで迷路もグラフじゃないかと突っ込んだ人はいませんか。今日はそれに気づきました。と言うことはつまり粗いグラフの中に密なグラフ構造を埋め込むといったことをしているわけですね。循環を持たない迷路はグラフで言うとツリーです。一般化すると上のアルゴリズムは次のような感じになります。

  • 適当なグラフを作る。
  • グラフから適当に枝を取り除いて木を作る。
  • 木に沿う形で頂点、辺を配置してグラフを作る。

一般化して何ができるかはまだよくわかりません。上に書いた生成方法では実はくだらないグラフしかできないと言うことが証明されるかも知れません><

スポンサーサイト
コメント
この記事へのコメント
> 粗いグラフの中に密なグラフ構造を埋め込む
スケールフリーとかスモールワールドとかのグラフ・ネットワーク研究の人がいろいろ考えてそうですね。
2008/05/30(金) 11:41 | URL | 桜庭 #-[ 編集]
それだー。http://en.wikipedia.org/wiki/Complex_network
だー。統計力学だスケーリング則だ小形先生勉強適当ですみませんでした。
2008/05/30(金) 23:31 | URL | Gus #-[ 編集]
コメントを投稿する
URL:
Comment:
Pass:
秘密: 管理者にだけ表示を許可する
 
トラックバック
この記事のトラックバックURL
http://gusmachine.blog49.fc2.com/tb.php/355-8f7cbec9
この記事にトラックバックする(FC2ブログユーザー)
この記事へのトラックバック
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。