著者

鷹野 芙美代 関根 敦史 佐田 宏史 前川 仁孝 六沢 一昭

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌. コンピューティングシステム (ISSN:03875806)

巻号頁・発行日

vol.45, no.11, pp.280-289, 2004-10-15

参考文献数

17

被引用文献数

2

---

本論文では階層的挟み撃ち探索を用いたAND/OR木の並列探索手法について提案する.証明数の小さい節点は解である可能性が高い.そのため,証明数を用いるAND/OR木の並列探索の多くは証明数の小さい節点から探索する.しかし証明数の大きい節点が解である場合は,解を見つけるのに多くの時間を必要とする.そこで,証明数の小さい節点と証明数の大きい節点の探索を並列に行い,さらに証明数の小さい節点に多くのプロセッサを割り当てる並列探索手法を提案する.このように複数プロセッサで探索することにより,従来の探索法では解を見つけるまでに時間がかかる証明数の大きい節点が解である場合にも,探索時間を短縮することができる.提案手法を共有メモリ型並列計算機に実装して評価した.評価の結果,逐次探索では時間のかかる問題に対し,スーパリニアスピードアップが確認された.