マルコフ連鎖モンテカルロ法を用いた迷路のランダム生成

• 三原 勇治

  九大

• 来嶋 秀治

  九大

• 山下 雅史

  九大

書誌事項

タイトル別名

• Generating a Random Maze by Markov Chain Monte Carlo Methods

抄録

本研究では，マルコフ連鎖モンテカルロ法を用いて迷路をランダム生成することを試みた．ここで扱う迷路は一般的な正方形型迷路であり，ループはない．各マスを一つの頂点とみなすと，迷路は正方格子グラフの全域木に対応する．したがって，迷路のランダム生成は格子グラフ上の全域木のランダム生成に対応する．格子グラフ上の全域木全体を状態空間とし，定常分布が一様分布となるマルコフ連鎖を構築することで，全域木を一様ランダム生成する．また，マルコフ連鎖の収束時間について，計算機実験の結果を示し，考察を与える．

収録刊行物

• 電気関係学会九州支部連合大会講演論文集

  電気関係学会九州支部連合大会講演論文集 2010 (0), 22-24, 2010

  電気・情報関係学会九州支部連合大会委員会

キーワード

• 情報基礎論

詳細情報

• CRID: 1390001205663239552
• NII論文ID: 130005033533
• DOI: 10.11527/jceeek.2010.0.22.0
• データソース種別:
  • JaLC
  • CiNii Articles
• 抄録ライセンスフラグ: 使用不可