AND/OR木における証明数・反証数を用いた階層的挟み撃ち探索(アルゴリズム・数値計算)
スポンサーリンク
概要
- 論文の詳細を見る
本論文では階層的挟み撃ち探索を用いたAND/OR木の並列探索手法について提案する.証明数の小さい節点は解である可能性が高い.そのため,証明数を用いるAND/OR木の並列探索の多くは証明数の小さい節点から探索する.しかし証明数の大きい節点が解である場合は,解を見つけるのに多くの時間を必要とする.そこで,証明数の小さい節点と証明数の大きい節点の探索を並列に行い,さらに証明数の小さい節点に多くのプロセッサを割り当てる並列探索手法を提案する.このように複数プロセッサで探索することにより,従来の探索法では解を見つけるまでに時間がかかる証明数の大きい節点が解である場合にも,探索時間を短縮することができる.提案手法を共有メモリ型並列計算機に実装して評価した.評価の結果,逐次探索では時間のかかる問題に対し,スーパリニアスピードアップが確認された.
- 一般社団法人情報処理学会の論文
- 2004-10-15
著者
-
前川 仁孝
千葉工業大学情報工学科
-
佐田 宏史
千葉工業大学情報科学部情報工学科
-
六沢 一昭
千葉工業大学情報科学部情報工学科
-
鷹野 芙美代
早稲田大学コンピュータ・ネットワーク工学科:日本学術振興会
-
前川 仁孝
千葉工業大学
-
鷹野 芙美代
千葉工業大学情報科学部情報工学科
-
関根 敦史
株式会社両毛システムズ
-
六沢 一昭
千葉工大 情報科学
-
佐田 宏史
千葉工業大学 情報工学科
-
六沢 一昭
千葉工業大学 情報工学科
-
鷹野 芙美代
千葉工業大学 情報工学科
関連論文
- 並列度・タスク実行時間の偏りを考慮した標準タスクグラフセットSTG Ver3を用いたスケジューリングアルゴリズムの評価(並列/分散アーキテクチャ,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2009))
- 並列度・タスク実行時間の偏りを考慮した標準タスクグラフセットSTG Ver3を用いたスケジューリングアルゴリズムの評価(並列/分散アーキテクチャ,「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2009))
- 階層的挟み撃ち探索における探索の重複領域の削減手法
- ニュートン補間法によるベクトル予測を用いた動きベクトル検出処理の高速化手法(一般セッション(4))
- ニュートン補間法によるベクトル予測を用いた動きベクトル検出処理の高速化手法
- スタティックスケジューリングを用いた電子回路シミュレーションの粗粒度/近細粒度階層型並列処理手法
- 電力系統過渡安定度計算の階層的並列処理手法
- 電子回路シミュレーションの階層的並列処理手法
- 電子回路シミュレーションの階層的並列処理手法
- 電子回路シミュレーションの粗粒度/近細粒度階層的並列手法
- 4Y-2 初心者のための気象情報システムの構築(情報システムの構築(1),一般講演,コンピュータと人間社会)
- 5X-9 コンピュータ用語による英語学習システム(教育支援システム,一般講演,コンピュータと人間社会)
- 2X-6 WWWを利用したドイツ語入門講座
- 2S-7 気象情報システムの構築 : wwwを用いた初心者向け気象学習支援
- 3K-4 電力過渡安定度計算の効率的な処理方法に関する研究
- 英単語発音学習システムの構築
- インタラクティブWebアンケートシステム
- 気象情報システムの構築
- G-5 事例ベース推論を用いた負荷分散方式(人工知能(実装),G.人工知能)
- D-3-9 先読みを考慮したヒューリスティックスケジューリングアルゴリズム
- 5W-2 VRMLによる環境学の研究(情報システムのフロンティア,一般講演,コンピュータと人間社会)
- 3G-3 電力過渡安定度計算の並列同時解放における系統分割の適用
- B-028 ストリーミングSIMD拡張命令を用いた電子回路シミュレータSPICE3の高速化(B分野:ソフトウェア,一般論文)
- 電磁界解析のための有限要素・境界要素併用法の並列処理
- 有限要素法と境界要素法を利用した電磁界解析の並列処理
- RF-003 将棋における評価関数自動生成の高速化(F分野:人工知能・ゲーム,査読付き論文)
- 編集にあたって(マルチコアにおけるソフトウェア)
- F-039 缶蹴りゲームにおける鬼の戦略学習(F分野:人工知能・ゲーム)
- 2S-1 データベース型電子掲示板
- 3J-2 WWWを利用した点字学習者支援環境
- 5H-4 火災シミュレータにおける評価支援システム
- 1Q-10 FTPを用いたマルチメディアメールシステムの構築
- WWWを利用した日本語点字学習者のための支援環境の構築
- 点字学習者支援システムの構築
- データベース型電子掲示板の試作
- Javaによる火災シミュレータの構築
- マルチメディアメールシステム
- B-025 評価関数の精度による階層的挟み撃ち探索の性能評価(B分野:ソフトウェア,一般論文)
- 証明数・反証数を用いた反復深化法における複数経路並行探索の並列化(HPC-6 : 並列アプリケーション)
- ベクトル量子化における画像信号に一般化調和解析を用いた画像符号化
- AND節点の並列探索を加えたAND/OR木階層的挟み撃ち探索(アルゴリズム)
- 一般化調和解析を併用したベクトル量子化による画像符号化
- 証明数・反証数を閾値とした反復深化法の複数経路同時探索による高速化(数値計算アルゴリズム(2), 「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2005))
- AND/OR木における証明数・反証数を用いた階層的挟み撃ち探索(アルゴリズム・数値計算)
- MATLABからC言語への変換における変数の動的解析削減手法(HPC-12 : 最適化と性能評価)(2004年並列/分散/協調処理に関する『青森』サマー・ワークショップ(SWoPP青森2004) : 研究会・連続同時開催)
- 命令キャッシュを考慮したコード生成法による方程式求解の高速化手法(ARC-4 : 実行スケジューリング)(2004年並列/分散/協調処理に関する『青森』サマー・ワークショップ(SWoPP青森2004) : 研究会・連続同時開催)
- AND/OR木におけるAND節点に対する並列探索の評価(CPSY-3 性能評価)(2004年並列/分散/協調処理に関する「青森」サマーワークショップ(SWoPP青森2004))
- 一般化調和解析とベクトル量子化の併用による画像圧縮
- D-11-57 一般化調和解析を用いたベクトル量子化による画像圧縮の改善
- D-14-17 一般化調和解析の処理効率の向上に関する研究
- E-024 サッカー試合の状況を表すアニメーション作成(E.自然言語・文書・ゲーム)
- A-8-4 ビリヤード習得のための学習システムの構築
- D-11-160 共有メモリ型並列コンピュータ上のステレオマッチングの並列処理手法
- A-8-3 携帯電話を用いたネットワーク投票システムの試作
- A-8-1 ビリヤード支援システムの構築
- J-19 小領域分割法によるステレオマッチングのプロセッサ割り当て手法(画像処理2-1,J.グラフィクス・画像)
- キャッシュヒット率を考慮したステレオマッチングの並列処理
- G-27 局面評価値による重み付けを利用した反復深化法の並列処理手法(人工知能(一般),G.人工知能)
- D-8-20 共有メモリ型並列計算機における詰将棋プログラムの階層型挟み撃ち探索
- D-3-10 クラウト法を用いた電力系統過渡安定度計算の粗粒度並列処理手法
- 一般化調和解析とベクトル量子化の併用による画像圧縮
- 配列間接アクセスを用いないコード生成法による電子回路シミュレーションの高速化とその並列処理
- 配列間接アクセスを用いないコード生成法による電子回路シミュレーションの高速化とその並列処理
- 電磁界解析における有限要素・境界要素併用法の並列処理手法
- 電磁界解析における有限要素・境界要素併用法の並列処理手法
- マルチプロセッサシステム上でのCFDの並列処理に関する研究
- 並列処理の導入による有限要素・境界要素併用解析法の高速化
- リカレントニューラルネットワークにおける学習の並列処理
- OSCARアプリケーション専用目的コンパイラにおける超階層マクロデータフロー処理手法
- マルチプロセッサシステム上での回路シミュレーションの並列処理手法
- OSCAR上でのスパース行列直接解法の並列処理
- OSCAR上での直接法を用いた回路シミュレーションの並列処理
- 専用目的コンパイラ開発用並列化中間言語とその処理系
- B-020 変数の可視化と検査機能を持つプログラミングシステム(B分野:ソフトウェア)
- B_024 鉄道路線モデルに基づくプログラムの動作の可視化(B分野:ソフトウェア)
- B_009 CP/MISFにおけるタスク優先順位の決定と評価(B分野:ソフトウェア)
- B-5 KL1プログラムの実行状況の視覚化(ソフトウェア開発支援ツール,B.ソフトウェア)
- 非同期分散環境における大域状態決定方法(並列処理)
- K_011 e-Learningにおける学習支援システム(K分野:ヒューマンコミュニケーション&インタラクション)
- K-031 古本屋支援システム(K分野:ヒューマンコミュニケーション&インタラクション)
- Webを利用したフィッシングエリア情報サービス
- 証明数・反証数を閾値とした反復深化法の複数経路同時探索による高速化(数値計算アルゴリズム(2), 「ハイパフォーマンスコンピューティングとアーキテクチャの評価」に関する北海道ワークショップ(HOKKE-2005))
- Web 3DによるMind Storms実験支援システム
- D-6-10 分散メモリ型計算機による有限要素・境界要素併用法の高速化(D-6. コンピュータシステム)
- D-17-4 モンテカルロ法を用いたデリバティブ・プライジングの並列処理手法
- D-3-1 コード生成法によるループフリーコードの計算手法
- A-8-3 XVLによるロボット実験支援システム
- A-8-2 Javaによる環境学習支援システムの試作
- 時間依存性のない線形素子による定数伝播を用いた電子回路シミュレータSPICE3の高速化
- 時間依存性のない線形素子による定数伝播を用いた電子回路シミュレータSPICE3の高速化
- 時間依存性のない線形素子による定数伝播を用いた電子回路シミュレータSPICE3の高速化
- 時間依存性のない線形素子による定数伝播を用いた電子回路シミュレータSPICE3の高速化
- D-3-8 相関分析におけるapriorTidアルゴリズムの並列処理手法
- 探索の重複領域削減による階層的挟み撃ち探索の高速化 (コンピューティングシステム Vol.4 No.4)
- B-040 GPUのための回路方程式求解における命令レベル並列度の評価(GPGPU,B分野:ソフトウェア)
- B-056 探索の重複領域を削減した階層的挟み撃ち探索による実行時間最小マルチプロセッサスケジューリング問題の求解(並列分散・仮想化技術,B分野:ソフトウェア)
- タスクスケジューリング問題の厳密解求解における探索ノード数削減アルゴリズム
- CUDAによるランダムスパース方程式求解の命令レベル並列性を用いた高速化手法
- N-022 初学者のためのプログラミング助言支援システムの開発(N分野:教育・人文科学,一般論文)