1 0 0 0 OA マルコフ連鎖モンテカルロ法を用いた迷路のランダム生成
- 著者
- 三原 勇治 来嶋 秀治 山下 雅史
- 出版者
- 電気・情報関係学会九州支部連合大会委員会
- 雑誌
- 電気関係学会九州支部連合大会講演論文集 平成22年度電気関係学会九州支部連合大会(第63回連合大会)講演論文集
- 巻号頁・発行日
- pp.22-24, 2010 (Released:2012-02-24)
本研究では,マルコフ連鎖モンテカルロ法を用いて迷路をランダム生成することを試みた.ここで扱う迷路は一般的な正方形型迷路であり,ループはない.各マスを一つの頂点とみなすと,迷路は正方格子グラフの全域木に対応する.したがって,迷路のランダム生成は格子グラフ上の全域木のランダム生成に対応する.格子グラフ上の全域木全体を状態空間とし,定常分布が一様分布となるマルコフ連鎖を構築することで,全域木を一様ランダム生成する.また,マルコフ連鎖の収束時間について,計算機実験の結果を示し,考察を与える.
1 0 0 0 OA 劣モジュラ的構造に基づく離散最適化基礎理論の展開と高速アルゴリズム開発
大規模離散最適化問題の有する劣モジュラ的な離散構造に注目し, 効率的なアルゴリズムの構築のために有効な離散構造を研究した.個別には,ネットワーク・フロー, マッチング,多品種フロー, 施設配置問題, 資源配分問題, グラフ連結度,通信網設計,待ち行列ネットワークに関わる離散構造,双対貪欲アルゴリズムに関わる離散構造(双対貪欲多面体, ゾノトープ) ,ホーン論理関数や安定マッチングの離散凸構造,などであり,個別の劣モジュラ的な離散構造の解明に基づき,それらの知見を横断的に総合する基礎理論の構築と高速アルゴリズムの開発を行った.