階層的挟み撃ち探索における探索の重複領域の削減手法

• Item type: SIG Technical Reports(1)
• 公開日: 2010-07-27
• タイトル: 階層的挟み撃ち探索における探索の重複領域の削減手法
• タイトル / 言語: en
• タイトル: A Search Space Reduction Method of Overlapping Search Space for Hierarchical Pincers Attack Search
• 言語: jpn
• キーワード / 主題Scheme: Other
• キーワード / 主題: 並列木探索と負荷分散
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 千葉工業大学情報工学科
• 著者所属: 千葉工業大学情報工学科
• 著者所属: 千葉工業大学情報工学科
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Chiba Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Chiba Institute of Technology
• 著者所属(英): en
• 著者所属(英): Department of Computer Science, Chiba Institute of Technology
• 著者名: 中村, あすか; 富永, 浩文; 前川, 仁孝
• 著者名(英): Asuka, Nakamura; Hirobumi, Tominaga; Yoshitaka, Maekawa
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 本稿は，分枝限定法に有効な並列探索手法のひとつである階層的挟み撃ち探索において，探索の重複によって複数のプロセッサが探索する領域を削減する手法を提案する．分枝限定法における階層的挟み撃ち探索では，複数のプロセッサが左右から挟み撃つように探索するため，複数のプロセッサで探索する領域が生じる．スレーブプロセッサの割当領域に対する探索の重複領域の割合は，各ノードの分枝数が少ない探索木ほど大きくなる．そこで，本稿では，すでに探索済みの領域をスレーブプロセッサに割当てないために，スレーブプロセッサだけでなくリーダプロセッサも探索の重複を検出する．本手法の有効性を示すために評価を行い，各ノードの分枝数が少ない探索木において提案手法の有効性を確認した．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: This paper proposes a reduction method of search space assigned some slave processors for the hierarchical pincers attack search which is one of the efficient parallel algorithm for branch and bound method. The hierarchical pincers attack search searches from right and left side of each subtree in a whole tree by a plurality of processors. Hence, some of processors search the same search space. A search tree consisting of a node connecting a few branches has higher ratio of overlapping search space of a whole tree. Therefore, the proposed method detects mutually overlapping search space by slave processors and a leader processor to prevent allocating already searched subtree to another slave processor. As a results of evaluation, we confirmed our proposed method has enough performance.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AN10463942
• 書誌情報: 研究報告ハイパフォーマンスコンピューティング（HPC）; 巻 2010-HPC-126, 号 28, p. 1-7, 発行日 2010-07-27
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会