演繹データベースにおける直積問題クラスとそのアルゴリズム
スポンサーリンク
概要
- 論文の詳細を見る
演繹データベースの新しい問題クラスである直積問題クラスを定義する.直積問題クラスは右線形問題や同世代問題を包む、datalog問題クラスの部分クラスである.このクラスを効率的に解くために直積法を提案する.従来の方法が中間データとして基礎アトムを生成するのに対し, 直積法は基礎アトムの集合を直積を利用して簡潔に表す式を生成する.これにより, 直積法は生成する中間データの数を減らして, 問題を効率的に解こうとする.直積問題クラス全体に適用できる従来の方法の中ではマジック集合法が最も効率的であると思われる.そこで, 直積法とマジック集合法の効率を比較するために, 直積問題の例として同世代問題の再帰ルールを複雑にした問題および非線形にした問題を使って, 計算機実験を行った.実験の結果, ファクトをランダムに生成した場合, どちらの問題に対しても問題がファクトを密に含むとき, 直積法がマジック集合法より効率的であることが分かった。
- 一般社団法人情報処理学会の論文
- 2001-01-15
著者
関連論文
- A Set Covering Approach for the Pickup and Delivery Problem with Additional Constraints (Numerical Optimization methods, theory and applications)
- 多制約配送計画問題に対する集合被覆アプローチ
- 2-A-3 MAX-2-SATに対する分枝限定法の改良(離散最適化(3))
- MAX-2-SATに対する分枝限定法(組合せ最適化(4))
- 勤務スケジューリング問題に対する局所探索法(医療・福祉・スケジューリング(2))
- 凸型時間ずれコストをもつ資源制約スケジューリング問題(統合オペレーション)
- TD-1-5 汎用スケジューラー : RCPSPによるアプローチ
- 分離可能凸型コスト関数をもつプロジェクトスケジューリング問題(スケジューリング)
- 汎用スケジューラー : RCPSPによるアプローチ (アルゴリズム工学)
- 資源制約付きスケジューリング問題の定式化と近似解法 (新しいパラダイムとしてのアルゴリズム工学)
- 汎用アルゴリズムとしてのCSP(制約充足問題)に対するタブー探索アプローチ(離散数理と連続数理における最適化理論)
- 「問題解決エンジン」への道
- 工学としてのアルゴリズム
- 集合被覆問題に対する3反転近傍を明いた局所探索法
- D-1-5 Horn CNF とその二分決定グラフ表現間の変換の計算複雑さ
- Deduction and Abduction with Ordered Binary Decision Diagrams (Foundations of Computer Science)
- 二分決定グラフ上での知識表現および正/ホーン関数の認識問題
- 数理計画 : 問題解決への広き門(ユーザのための数理計画入門)
- 木状の方策をもつ組合せ最適化問題の有限状態表現
- 演繹データベースにおける直積問題クラスとそのアルゴリズム
- 多次元直方体被覆問題および充足可能性問題を解くアルゴリズム
- 緩和法による演繹データベースの問合せ評価
- 多変数同世代問題に対する問い合わせ評価法
- 多変数同世代問題に対する問合せ評価法
- 緩和法による演繹データベースの問い合わせ評価
- 多変数線形再帰型演繹データベースに対する逆数え上げ評価法
- 仮説を利用した推論方式
- Short Time DFTの開発とその情報通信への応用研究
- D-1-6 家系図に基づいた統計情報の効率的な計算方法
- MAX-2-SATに対する分枝限定法
- ルール生成に必要なデータ量に関するランダム性に基づいた解析
- 1-D-1 ルール生成に必要なデータ量に関するランダム性に基づいた解析(マーケティング(1))
- オプションプライシングと凸計画問題の関係について(金融工学(3))
- 長方形詰込み問題に対する可変近傍探索法(組合せ最適化(4))
- 移動時間コスト関数を考慮した時間枠つき配送計画問題に対する局所探索法 (数理最適化から見た「凸性の深み,非凸性の魅惑」)
- Local Search Algorithms for the Two-Dimensional Cutting Stock Problem with a Given Number of Different Patterns (Captivation of Convexity : Fascination of Nonconvexity)
- 移動時間コスト関数を考慮した時間枠つき配送計画問題に対する局所探索法(組合せ(1))
- 段取り替え制約付きカッティングストック問題に対する列生成法を用いた局所探索法の提案(組合せ(1))
- D-1-5 家系図を利用した遺伝子型の計算方法
- 計算クラスタ上で文字列の類似度を計算するための並列アルゴリズム(経営情報科学部:情報科学科 コンピュータシステム専攻)
- 配置コストをもつ長方形詰込み問題に対する局所探索法の高速化 (最適化の数理とアルゴリズム)
- 配置コストをもつ長方形詰込み問題に対する局所探索法の高速化
- 配置コストをもつ長方形詰込み問題に対する局所探索法の高速化(組合せ最適化(2))
- 配置コストをもつ長方形詰込み問題に対する局所探索法について(統合オペレーション(4))
- TD-1-6 組合せ最適化問題に対する局所探索アルゴリズムの開発について
- 配置コストをもつ二次元配置問題に対する局所探索について(組合せ最適化)
- ATMスイッチにおけるタイマ・チャネル割付けについて
- 藤重, 岩田先生Fulkerson賞受賞のニュース(情報の窓)
- Support Vector Machineにおけるルールの利用(線形計画)
- カッティングストック問題に対する線形計画法に基づく局所探索法の提案 (最適化の数理とアルゴリズム)
- 閾グラフの最小辺ランキング全域木について
- 「高度応用のための情報ベースモデルとその実現技術」を目指して (メディア統合および環境統合のための高機能データベースシステム、および一般)
- 総論 (特集 アルゴリズムの新展開--理論から工学へ)
- アルゴリズムの道具箱・基礎編(最終回)巡回セールスマン問題
- 内点法
- D-1-8 多次元直方体の和の大きさを計算するアルゴリズム(D-1. コンピュテーション, 情報・システム1)
- メジアンフィルタを用いた正弦波の周波数推定
- モーメントを用いた連続音声のピッチ周波数分布に関する研究
- データ分類におけるノイズ量の評価について(数理計画(1))
- データからの知識獲得における常識ルールと例外ルールについて(数理計画(2))
- 最小辺ランキング全域木問題について
- A polynomial time approximation scheme for the minimum maximal matching problem in planar graphs (New Developments of Theory of Computation and Algorithms)
- 平面グラフにおける最小極大マッチング問題に対する多項式時間近似スキーム
- 公平分割とその手順
- TD-1-7 Webブラウザで見せるアルゴリズム
- タブー探索による直交ラテン方陣の構成(連続と離散の最適化数理)
- タブー探索による直交ラテン方陣の構成(組合せ最適化(2))
- 機械式立体駐車場入出庫スケジューリング
- カッティングストック問題に対する線形計画法に基づく局所探索法の提案(組合せ最適化(2))
- カッティングストック問題におけるパターン生成法について(組み合わせ最適化(2))
- 段取り替え数最小化を考慮したカッティングストック問題の定式化と近似解法 (最適化のための連続と離散数理)
- 組合せ最適化問題に対するメタ戦略について(情報基礎理論ワークショップ(LAシンポジウム)論文小特集)
- メタ戦略のロバスト性について
- 遺伝アルゴリズムと局所探索法のロバスト性について
- 一般化2次割当問題に対する大規模近傍探索法の適用について(数理計画(1))
- メタヒューリスティクスの枠組
- メタ戦略とラグランジュ緩和(「スケジューリング技術の新たな展開特集号」)
- 一般化時間枠制約付き配送計画問題に対する局所探索法の適用とその応用(組合せ最適化)
- 多資源一般化割当問題に対する大規模近傍探索法の適用について(組合せ最適化)
- 集合被覆問題に対する局所探索法について (最適化のための連続と離散数理)
- Greedy Splitting : A Unified Approach for Approximating Some Partition Problems (Mathematical Optimization Theory and its Algorithm)
- A Primal-Dual Approximation Algorithm for the Survivable Network Design Problem in Hypergraphs (New Developments of Theory of Computation and Algorithms)
- ホーン理論とq-ホーン理論の極小関数従属性の推定について
- データの論理的解析におけるルール集合の生成について(数理計画(1))
- 論理的データ解析における階層的分解構造について
- データマイニングプロセスにおける属性の生成と選択について(マーケッティング)
- 特集にあたって (アルゴリズム工学)