AND/OR木における証明数・反証数を用いた階層的挟み撃ち探索

• Item type: Trans(1)
• 公開日: 2004-10-15
• タイトル: AND/OR木における証明数・反証数を用いた階層的挟み撃ち探索
• タイトル / 言語: en
• タイトル: Hierarchical Pincers Attack Search Using Proof Numbers and Disproof Numbers for AND/OR Tree
• 言語: 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
• 著者所属(英): Ryomo Systems Co., Ltd.
• 著者所属(英): 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; Atsushi, Sekine; Hiroshi, Sata; Yoshitaka, Maekawa; Kazuaki, Rokusawa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本論文では階層的挟み撃ち探索を用いたAND/OR木の並列探索手法について提案する．証明数の小さい節点は解である可能性が高い．そのため，証明数を用いるAND/OR木の並列探索の多くは証明数の小さい節点から探索する．しかし証明数の大きい節点が解である場合は，解を見つけるのに多くの時間を必要とする．そこで，証明数の小さい節点と証明数の大きい節点の探索を並列に行い，さらに証明数の小さい節点に多くのプロセッサを割り当てる並列探索手法を提案する．このように複数プロセッサで探索することにより，従来の探索法では解を見つけるまでに時間がかかる証明数の大きい節点が解である場合にも，探索時間を短縮することができる．提案手法を共有メモリ型並列計算機に実装して評価した．評価の結果，逐次探索では時間のかかる問題に対し，スーパリニアスピードアップが確認された．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This paper proposes a parallel AND/OR tree search algorithm using the hierarchical pincers attack search. Parallel processing algorithms of AND/OR tree search are proposed. Many of them search a tree from a node having a small proof number. When a solution is a node having a large proof number, they need a long computation time. Therefore, the proposed algorithm uses the hierarchical pincers attack search. It is able to search from a node having a small proof number and a node having a large proof number simultaneously. Additionally, many processors search some nodes having a small proof number, and a few processors search some nodes having a large proof number. The proposed algorithm is implemented on a shared memory multiprocessor and evaluated. The result shows super linear speedup by parallel processing when sequential search needs a long computation time.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11833852
• 書誌情報: 情報処理学会論文誌コンピューティングシステム（ACS）; 巻 45, 号 SIG11(ACS7), p. 280-289, 発行日 2004-10-15
• ISSN / 収録物識別子タイプ: ISSN
• ISSN / 収録物識別子: 1882-7829
• 出版者 / 言語: ja
• 出版者: 情報処理学会