AND節点の並列探索を加えたAND/OR木階層的挟み撃ち探索

• Item type: Trans(1)
• 公開日: 2005-08-15
• タイトル: AND節点の並列探索を加えたAND/OR木階層的挟み撃ち探索
• タイトル / 言語: en
• タイトル: Adding Parallel AND Node Search to AND/OR Tree Hierarchical Pincers Attack Search
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: アルゴリズム
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_6501
• 資源タイプ: journal article
• 著者所属: 千葉工業大学情報科学部情報工学科
• 著者所属: 千葉工業大学情報科学部情報工学科
• 著者所属: 千葉工業大学情報科学部情報工学科
• 著者所属: 千葉工業大学情報科学部情報工学科
• 著者所属: 千葉工業大学情報科学部情報工学科
• 著者所属(英): en
• 著者所属(英): Department of Computer Science Faculty of Information and Computer Science Chiba Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Computer Science Faculty of Information and Computer Science Chiba Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Computer Science Faculty of Information and Computer Science Chiba Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Computer Science Faculty of Information and Computer Science Chiba Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Computer Science Faculty of Information and Computer Science Chiba Institute of Technology
• 著者名: 鷹野, 芙美代; 佐田, 宏史; 前川, 仁孝; 六沢, 一昭; 宮崎, 収兄
• 著者名(英): Fumiyo, Takano; Hiroshi, Sata; Yoshitaka, Maekawa; Kazuaki, Rokusawa; Nobuyoshi, Miyazaki
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では，AND/OR 木の並列探索手法であるAND/OR 木階層的挟み撃ち探索において，プロセッサを割り当てる節点を増やすことで，さらに多くのプロセッサを有効活用する並列探索手法を提案する．AND/OR 木階層的挟み撃ち探索は，評価の高いOR 節点に多くのプロセッサを割り当て，評価の低い節点も並列に探索する．これにより，逐次探索では解の発見に時間のかかる評価の低い節点が解である場合，探索時間を大きく短縮することができる．AND/OR 木階層的挟み撃ち探索におけるOR 節点のみの並列探索は，並列探索可能な節点が少ないとすべてのプロセッサを使用できない場合もある．そこで，AND/OR 木階層的挟み撃ち探索で使用されないプロセッサを用いてAND 節点も並列に探索することで，より多くのプロセッサを有効利用する．これにより，AND/OR 木階層的挟み撃ち探索で多くのプロセッサを利用することができない問題に対し，より高速に解が求まる．最後に，提案手法を共有メモリ型並列計算機上で評価した結果，AND/OR 木階層的挟み撃ち探索よりも最高16.8 倍，相乗平均1.5 倍高速化されることが確認できた．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This paper proposes a parallel search algorithm making more efficient use of processors by increasing parallel searchable nodes in AND/OR tree hierarchical pincers attack search (AOHPAS). AOHPAS searches nodes with high evaluation value and low evaluation value simultaneously. Also, AOHPAS allocates many processors to OR nodes with high evaluation value. Thus, when the node with low evaluation value is a solution and sequential searches need long computation time, it is able to reduce computation time greatly. In parallel search of only OR nodes, some processors are not able to be used because there are a few parallel searchable nodes. Therefore, in the proposed algorithm, processors not used by AOHPAS can be used to search AND nodes in parallel. Consequently, the proposed algorithm is able to make more efficient use of processors and to solve problems faster that AOHPAS is not able to use many processors. Finally, the proposed algorithm is implemented on a shared memory multiprocessor and evaluated. It results up to 16.8 times speedup and 1.5 times speedup on the geometric average compared with AOHPAS.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11833852
• 書誌情報: 情報処理学会論文誌コンピューティングシステム（ACS）; 巻 46, 号 SIG12(ACS11), p. 319-329, 発行日 2005-08-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7829
• 出版者 / 言語: ja
• 出版者: 情報処理学会