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

kinabaさんのd.y.dのランダム生成記事

連結グラフを欲しいときに、

たとえば 「連結グラフとその上の頂点が1つ指定されたときに、そこからグラフ上で一番遠い地点を計算せよ」という問題を作ったとすると、ランダムデータとして、ランダムに "連結な" グラフを生成しないといけません。
点1個のグラフから始めて、それまでに入れた点のどれかとは必ず繋がるように次々点を加えて行けばOK。
いやこれだと確率分布は偏りますが、考えるのが面倒になったのでこれでいいことにします(適当)。「必ず連結なグラフしか作らない」し、「連結なグラフは必ずこれで作られうる」ので。

このアルゴリズムを用いると、普通の連結グラフが出来ます。あんまり普通じゃないグラフは登場頻度が少なくなります。生成されると想定しているグラフの中にちょっと普通じゃないやつがあると、試したら出てきてなくて困ったりします。出てきてないのに作った人が気づかないともっと困った事態になります。

以前ACM-ICPC OB/OGの会の模擬国内予選 Fにてこの方法でデータを作り、ちょっと困ったことになりました。このときの問題は頂点数100のグラフから最短距離のようなものを求めさせる感じでした。そして、上の方法でランダムデータを作ったところ、それらからは最短距離が10を超える答えがほとんど出ませんでした。 たとえば、100個の頂点の多くが一列につながったようなグラフは生成確率が低かったようなのです。距離50あたりすらほとんどありません。

これではテストには不完全だということで、別のアルゴリズムを用いたデータを加えました。それは、「答えの距離がnになるグラフ」です。作り方は簡単で、n+1個の頂点を直線状につなげて、残りの頂点やら辺やらを迂回路になるようにつけるだけです。想定される答えを先に作っておいて、あとから冗長な部分を付け加えたのです。

スポンサーサイト
コメント
この記事へのコメント
そう、普通のグラフの方が圧倒的に数が多いので、"辺のon/offがほぼ均等"になるような乱数の使いかただと明らかにそっちに偏るんですよね。

こういうノウハウどっかにたまってないかしらん。
2006/10/21(土) 04:05 | URL | k.inaba #-[ 編集]
コメントを投稿する
URL:
Comment:
Pass:
秘密: 管理者にだけ表示を許可する
 
トラックバック
この記事のトラックバックURL
http://gusmachine.blog49.fc2.com/tb.php/84-0baa7ad3
この記事にトラックバックする(FC2ブログユーザー)
この記事へのトラックバック
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。