二分決定グラフによる制約充足問題の解法
スポンサーリンク
概要
- 論文の詳細を見る
BDD(二分決定グラフ) はブール関数のコンパクトな表現方法である.我々は,BDDを使用して組合せ問題の複数の解を同時に表現したり,ATMSといった多重文脈型真偽維持システムの機能拡張をする方法を検討してきた.与えられた問題記述あるいは制約条件からBDDを構築する過程は制約充足問題の解法とみなすことができる.本稿では,2種類のBDD,算術論理式が使用できる通常のBDDと組合せ集合が使用できるZBDD (Zero-Suppressed BDD) を取り上げ,それらを用いた制約充足問題の解放を検討する.制約充足問題のデータと制約条件のコーディング方法を提案し,N-Queens問題や魔方陣の問題などの具体的な問題を取り上げ,2種類のBDDによる解法を評価する.さらに,BDDによる解法を,制約充足問題での一貫性アルゴリズムやATMSと比較し,評価を行う.BDDでは,一旦適用された制約条件が以降ずっと成立するという単調一貫性維持が成立する.一方,ZBDDでは,組合せ集合演算の性質から,制約条件が適用する対象によって制限される.しかし,この結果ZBDDでは段階的解法が容易となる.
- 一般社団法人情報処理学会の論文
- 1995-08-15
著者
-
奥乃 博
Ntt基礎研究所
-
湊 真一
Ntt Lsi研究所
-
湊 真一
北海道大学大学院情報科学研究科・科学技術振興機構erato湊離散構造処理系プロジェクト・ /科学技術振興機構erato湊離散構造処理系プロジェクト・北海道大学大学院情報科学研究科
-
湊 真一
Ntt Lsi 研究所
関連論文
- 複数の言語モデルと言語理解モデルによる音声理解の高精度化(音声認識・理解,情報爆発論文)
- 第6回全米人工知能会議に出席して(Sixth National Conference on Artificial Intelligence, AAAI-87)
- 二分決定グラフによる効率的な三面図理解システムTOVINの実装
- ゼロサプレス型BDDを用いた系列長制限つき正規表現処理方法
- 発話行為レベルの情報を活用した音声対話システムの研究
- 背景音楽つき音声に対する音響ストリームの分離
- 背景音楽つき音声に対する音響ストリームの分離
- 多重奏中の歌声の基本周波数と有声音素の同時推定手法
- テルミンの音高・音量特性のモデルに基づくテルミン演奏ロボットの開発
- RNNを備えた2体のロボット間における身体性に基づいた動的コミュニケーションの創発
- Query-by-Conducting:テンポ類似性に基づく同一楽曲における多様な解釈の検索インタフェース
- 多重奏音響信号中の演奏をユーザー指定の旋律に差し替えるフレーズ置換システム
- バージイン許容音声対話システムにおけるユーザ発話の分析と指示対象同定への応用
- SpeakBySinging: 歌声を話声に変換する話声合成システム
- バージイン許容音声対話システムにおけるユーザ発話の分析と指示対象同定への応用
- 音オントロジーに基づいた音環境理解システムの統合 (「オントロジーの基礎と応用」)
- 音響ストリーム分離の音声認識からの評価
- 音響ストリーム分離の音声認識からの評価
- 音環境理解のためのマルチエージェントによる調波構造ストリームの分離
- マルチエージェントシステムによる音響ストリーム分離 : ストリーム分離の排他性の向上
- マルチエージェントシステムによる音響ストリーム分離のダイナミクス
- 創発的計算モデルによる音環境理解 : 音響ストリーム分離エージェントの構築と評価
- AIマップについて
- ロボット聴覚--高雑音下でのハンズフリー音声認識 (音声)
- 3U-2 複数の言語モデルと言語理解モデルによる音声理解手法のラピッドプロトタイピングへの適用(音声認識・理解,学生セッション,人工知能と認知科学,情報処理学会創立50周年記念)
- 二分モーメントグラフを用いた大規模多項式の操作手法
- 全米人工知能会議AAAI-94報告
- 6J-6 楽器音イコライザによる楽曲音響特徴変動と類似楽曲検索への応用(情報爆発時代における対話ロボティクス,一般セッション,「情報爆発」時代に向けた新IT基盤技術,情報処理学会創立50周年記念(第72回)全国大会)
- 5V-6 RNNを用いた行為予測による人間とロボットの協調物体配置(人工知能一般(4),学生セッション,人工知能と認知科学,情報処理学会創立50周年記念)
- 6U-1 F0・振幅・音韻長の制御により歌声を話声に変換する話声合成システムSpeakBySinging(音声・歌声合成,学生セッション,人工知能と認知科学,情報処理学会創立50周年記念)
- AI-1-3 ロボット聴覚オープンソースソフトウエアHARK(AI-1.マルチモーダル信号処理とその応用,依頼シンポジウム,ソサイエティ企画)
- 6J-8 実環境音声認識のためのロボット聴覚システム開発とパラメータチューニング(情報爆発時代における対話ロボティクス,一般セッション,「情報爆発」時代に向けた新IT基盤技術,情報処理学会創立50周年記念(第72回)全国大会)
- 6J-7 ロボット音声対話におけるSemi-blind ICAを用いた自己発話キャンセル(情報爆発時代における対話ロボティクス,一般セッション,「情報爆発」時代に向けた新IT基盤技術,情報処理学会創立50周年記念(第72回)全国大会)
- 2ZN-2 バージイン許容音声対話におけるLSMによる許容発話範囲の拡張(情報爆発時代における対話インタラクション,学生セッション,「情報爆発」時代に向けた新IT基盤技術,情報処理学会創立50周年記念(第72回)全国大会)
- 6W-8 MTRNNを用いた単語と文法の階層的自己組織化による文の認識・生成(構文解析・生成・学習,学生セッション,人工知能と認知科学,情報処理学会創立50周年記念)
- 5U-9 ユーザの文法知識を状態に加えたPOMDPに基づく音声対話システム(音声インタフェース・システム,学生セッション,人工知能と認知科学,情報処理学会創立50周年記念)
- マルチエージェントによるマルチメディア通信サービスの適合的プラニング
- 二分決定グラフ(BDD)による多重文脈型真偽維持システムBMTMS
- 二分決定グラフ(BDD)による真偽維持システムの実現
- 3U-9 環境音から擬音語への自動変換における特徴量抽出法の検討(音声認識・理解,学生セッション,人工知能と認知科学,情報処理学会創立50周年記念)
- 3U-7 スペクトル推定を用いたマイク数以上の同時発話に対する音声認識(音声認識・理解,学生セッション,人工知能と認知科学,情報処理学会創立50周年記念)
- 二分決定グラフの適用による三面図の効率的理解
- BDDの制約順序の効率化による制約充足問題の解法
- 二分決定グラフを用いた三面図理解システム
- 二分決定グラフによる三面図理解システムの機能拡張
- 二分決定グラフを用いた三面図の効率的理解
- 全米人工知能会議 AAAI-96 報告
- Zero-suppressed-BDDによる制約充足問題解法の性質 : 組合せ集合演算による非単調性の解明
- 残差駆動型アーキテクチャの提案と音響ストリーム分離への応用
- マルチメディア時代における情報通信サービスのプラニング機構の検討
- マルチメディア時代における情報通信サービスのプラニング機構の検討
- マルチメディア時代における情報通信サービスのプラニング機構の検討
- マルチメディア通信サービスの適合的実時間プランニング機構の検討
- マルチメディア通信サービスの適合的実時間プランニング機構の検討
- ゼロサプレスBDDによるペトリネットのCTL記号モデル検査
- ベース音高と和音特徴の統合に基づく和音系列認識
- 多数の人の声を一度に聞き分ける聴覚技術 : —聖徳太子ロボットを目指して—
- ロボット聴覚用オープンソースソフトウェアHARKの展開 (特集 世界に飛び出す日本のソフトウェア)
- 二分決定グラフ(BDD)による命題論理プログラミング
- MAHL:演奏者間のインタラクション分析のためのスコアアライメント手法の提案
- 歌詞と音響特徴量を用いた楽曲印象軌跡推定法の設計と評価
- ドメイン外発話が扱え拡張性が高い対話ドメイン選択フレームワーク
- ドメイン外発話が扱え拡張性が高い対話ドメイン選択フレームワーク
- コラム「計算機科学とインターネット」の開設にあたって
- 一人工知能研究者のインターネット活用法 (「人工知能研究者のためのインターネット活用術」)
- 小特集「人工知能研究者のためのインターネット活用術」にあたって
- Soarアーキテクチャ (「Soarプロジェクト」)
- ATMSの高速化技法とその応用 (「推論の高速化技術」)
- 三面図の暖昧性除去における二分決定グラフの利用
- ぺた語義:京大における Lisp を使ったプログラミング教育
- 視聴覚統合ビートトラッキングを用いた音楽ロボットとギターとの合奏システム
- ロボットを対象とした二階層視聴覚統合音声認識システム
- アルゴリズム記述からのBDD生成
- 組合せ回路検証の技術
- 二分決定グラフによる制約充足問題の解法
- ゼロサプレス型BDDを用いた非明示的積和形表現の高速因数分解法
- 2. 計算機上での BDD の処理技法 (<特集> BDD (二分決定グラフ))
- 「わくわく」 - 技術革新のキーワード -
- 共有二分決定グラフの「幅」に着目した変数順序づけ手法
- 多数の人の声を一度に聞き分ける聴覚技術 : 聖徳太子ロボットを目指して
- ロボット聴覚 : 高雑音下でのハンズフリー音声認識(オーガナイズドセッション,一般,オーガナイズドセッション(雑音を消せ!騒音下で有効な音声信号処理とは))
- 論理関数の共有二分決定グラフによる表現とその効率的処理手法
- 音楽共演ロボット:開始・終了キューの画像認識による人間のフルート奏者との実時間同期
- 音声対話システムにおける 簡略表現認識のための自動語彙拡張
- フレーズ置換のための調波非調波GMM・NMFに基づく音源分離・演奏合成
- 発語行為レベルの情報をユーザ発話の解釈に用いる音声対話システム
- 調波構造と方向同定に基づく音響ストリーム分離
- マルチエージェントによる音響ストリーム分離
- 共有二分決定図を用いた論理関数の処理手法について
- 真理値表表現を用いた記号シミュレータ
- AI-1-5 大規模な離散構造データを扱うためのGPU利用法の検討(AI-1.GPUを用いた高速化技術とそのVLSI設計への応用,依頼シンポジウム,ソサイエティ企画)
- BS-1-2 順列集合を操作する効率的なデータ構造とアルゴリズムの研究について(BS-1. 学生による研究室交流会,シンポジウムセッション)
- TAO における論理型プログラミングとその処理方式
- NueLindaモデルと自己記述による実装
- ベイジアン非負値調波因子分解と多重基本周波数推定への応用
- 押弦制約と運指制約を用いたタブ譜自動生成システム
- 2-2 混合音を聞き分けるセンシング技術(2.人間をセンシングする技術,人間を理解するためのICT技術-人間を対象としたセンシング・情報処理からその応用まで-)
- ロボット聴覚用オープンソースソフトウェア HARKの展開
- ROS(Robot Operating System)を用いた音楽合奏ロボットシステムの構築(ビッグデータで変わる環境知能とロボット,及びその他一般)
- 方言対訳コーパスを用いた日本語方言音声認識システム(言語モデル・音声対話)