多次元直方体被覆問題および充足可能性問題を解くアルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
一つのd次元直方体(全領域と呼ぶ)が複数のd次元直方体の和により被覆されているか否かを判定する問題(多次元直方体被覆問題と呼ぶ)を考える. この問題は充足可能性問題の変形であり, 充足可能性問題の代表的解法であるDavis-Putnum法と局所探索法を素直に拡張して, この問題を解くことができる. 本論文では, 直方体群の幾何学的性質を利用してDavis-Putnum法を拡張することにより新しい解法を提案し, 提案した解法と従来の解法の効率を計算機実験により比較する. 実験の結果, 多次元直方体被覆問題および充足可能性問題のどちらにおいても, 全領域の全体または全領域のほとんどの部分が被覆されていて, かつ, 直方体の重複の度合が低い問題例では, 提案した解法がDavis-Putnum法および局所探索法より効率的であることがわかった.
- 社団法人電子情報通信学会の論文
- 1997-07-25
著者
関連論文
- 給油施設操業スケジューリング (企業事例)
- 特集にあたって (ユーザのための数理計画応用)
- 木状の方策をもつ組合せ最適化問題の有限状態表現
- 演繹データベースにおける直積問題クラスとそのアルゴリズム
- 多次元直方体被覆問題および充足可能性問題を解くアルゴリズム
- 緩和法による演繹データベースの問合せ評価
- 多変数同世代問題に対する問い合わせ評価法
- 多変数同世代問題に対する問合せ評価法
- 緩和法による演繹データベースの問い合わせ評価
- 多変数線形再帰型演繹データベースに対する逆数え上げ評価法
- 仮説を利用した推論方式
- Short Time DFTの開発とその情報通信への応用研究
- 自己双対正論理関数の分解について
- D-1-6 家系図に基づいた統計情報の効率的な計算方法
- D-1-5 家系図を利用した遺伝子型の計算方法
- 計算クラスタ上で文字列の類似度を計算するための並列アルゴリズム(経営情報科学部:情報科学科 コンピュータシステム専攻)
- Serializable Classesの構造について(計算機構に関する数学的基礎理論とその応用)
- 先読みスケジューラによる分散型データベースシステムの並行処理制御(計算アルゴリズムと計算量の基礎理論)
- 版数制限をもつ先読みスケジュ-ラ
- グラフパッキング問題の計算複雑度(計算機科学の基礎理論とその応用)
- 内点法
- D-1-8 多次元直方体の和の大きさを計算するアルゴリズム(D-1. コンピュテーション, 情報・システム1)
- メジアンフィルタを用いた正弦波の周波数推定
- モーメントを用いた連続音声のピッチ周波数分布に関する研究
- ランダム有向グラフにおける到達可能性と推移閉包の大きさについて
- 関係の推移閉包の大きさの近似的推定法
- 演えきデータベースにおける質問処理コストの近似的評価法
- Complexity of the Optimum Join Order Problem in Deductive Databases
- 辺連結度増加関数をO^^〜(mn)時間で計算するアルゴリズム
- フローゲームの凸性について(ゲーム理論(2))
- マトロイド上の最小基ゲーム
- 多次元コスト関数をもつ有限オートマトンについて (情報科学の数学的基礎理論と応用)
- ある種の平面有向ネットワークの多品種流問題について(計算アルゴリズムと計算量の基礎理論)
- タブー探索による直交ラテン方陣の構成(連続と離散の最適化数理)
- 中間経由節点をもつKサーバー問題(計算機構とアルゴリズム)
- 最小容量カットアルゴリズムのプログラムによる効率の良い実現法
- 多重グラフにおける(λ+1)-カット
- 領域制約の下でのゲーム木探索(計算アルゴリズムと計算量の基礎理論)
- ゲーム木探索法SSSの非劣性について(計算アルゴリズムの基礎理論)
- 無向グラフ上の辺分離問題を解く簡単なO(mn)時間アルゴリズム
- 高信頼性ユニットからなる並-直列システムの漸近的に最適な保全政策(信頼性)
- 経済状態を考慮したアメリカンオプションの最適行使問題(ポートフォリオ)
- 33. 線形計画問題の高速解法 (アルゴリズムの最近の動向)
- Learning Algorithms for 2 × 2 Stochastic Games with Incomplete Information
- グラフ上の搬送スケジューリング問題の計算の複雑さについて(スケジューリング(2))
- グラフ上の搬送スケジューリング問題の計算の複雑さについて
- 遺伝アルゴリズムにおける交叉法に対する一考察(計算量理論)
- 1機械スケジューリング問題に対するSSDP法(動的計画法)
- 部分定義論理関数の正論理関数とHorn関数における関数分解について
- サブツアー交換交叉に対する二つのコメント
- サブツアー交換交叉に対する2つのコメント
- 不完全例題に対するプール的解析
- 鎖パッキング問題について(アルゴリズムの数学的基礎理論とその応用)
- 最小カット問題の簡潔かつ構成的な証明
- Primal-Dual Proximal Point Algorithm for Multicommodity Network Flow Problems(MATHEMATICAL OPTIMIZATION AND ITS APPLICATIONS)
- 非線形最小費用流問題に対する双対ニュートン法(決定理論とその周辺)
- 年齢に依存した費用を持つ小修理・取替え問題についてII(信頼性)
- 年齢に依存した費用を持つ小修理・取替え問題について(信頼性)
- 平均費用規範最適小修理・取替え問題について(最適化理論とその関連分野)
- ある信頼性システムに対する修理限界取替え政策の最適性について(マルコフ解析)
- 平均費用規範最適小修理・取替え問題について(マルコフ解析)
- 多項過程モデルによるルックバックオプションの価格の上・下界評価(数理計画モデルにおける最適化理論)
- 多項過程モデルによるルックバックオプションの価格の上・下界評価(金融)
- 組合せ最適化ゲーム
- 資産の収益率の相関がある構造を持つポートフォリオ選択問題について(資金・資本の流れ)
- ポートフォリオ選択問題における投資家の危険回避性と初期の富の影響(ポートフォリオ)
- ポートフォリオ選択問題における資産の収益率の確立順序(最適化の数理とその応用)
- 多期間ポートフォリオ選択問題における分離定理(計画数学とその関連分野)
- リーダー選出問題における時間最小アルゴリズムについて(計算アルゴリズムと計算量の基礎理論)
- データの論理的解析とブール関数
- データの論理的解析とブール関数
- 部分定義論理関数の内核関数と外核関数
- 2-単調正論理関数の同定問題に対する単純な高速アルゴリズム
- 論理関数の内包関数と外包関数について
- 不完全に定義された正論理関数の最大潜伏度について
- 正論理関数の最大潜伏度について(計算機構とアルゴリズム)
- 大規模非線形計画問題に対する逐次2次計画分解法