対称解の特性を用いたN-Queens問題の求解とGPUによる高速化

• Item type: SIG Technical Reports(1)
• 公開日: 2012-02-24
• タイトル: 対称解の特性を用いたN-Queens問題の求解とGPUによる高速化
• タイトル / 言語: en
• タイトル: Solving the N-Queens Problem with properties among Symmetric Solutions and its GPU Acceleration
• 言語: jpn
• 資源タイプ / 資源タイプ識別子: http://purl.org/coar/resource_type/c_18gh
• 資源タイプ: technical report
• 著者所属: 大阪府立大学大学院理学系研究科情報数理科学専攻
• 著者所属: 大阪府立大学大学院理学系研究科情報数理科学専攻
• 著者所属(英): en
• 著者所属(英): en
• 著者所属(英): Department of Mathematics and Information Sciences, Graduate School of Science, Osaka Prefecture University
• 著者所属(英): en
• 著者所属(英): Department of Mathematics and Information Sciences, Graduate School of Science, Osaka Prefecture University
• 著者名: 萩野谷, 一二; 田中, 慶悟; 藤本, 典幸
• 著者名(英): Kazuji, Haginoya; Keigo, Tanaka; Noriyuki, Fujimoto
• 論文抄録 / 内容記述タイプ: Other
• 論文抄録 / 内容記述: 最近，N-Queens 問題への新しい取組が行われている．1 つは，田中らの GPU を用いた高速化の提案であり，もう 1 つは，萩野谷の新しい解法アルゴリズム 「部分解合成法」 の提案である．本論文では，田中らの提案手法をベースに，部分解合成法における 「代表解の選択条件」 の取り込みを行った．NVIDIA GeForce GTX580 と Intel Core i7 2600 3.4GHz CPU を使用した評価実験では，N=23 の問題の求解時間は，12 時間 43 分 39 秒と N=24 の世界記録を 2003 年に樹立した電通大の PC クラスタ（Intel Pentium4 Xeon 2.8GHz CPU x 68） の約 4.5 倍高速であった．
• 論文抄録(英) / 内容記述タイプ: Other
• 論文抄録(英) / 内容記述: Recently, research on the N-Queens problem has evolved in two directions. One is using a GPU proposed by Tanaka et al., and the other is a novel sequential algorithm, named 'subsolution composition method', proposed by Haginoya. This paper presents a new GPU algorithm that adopts 'selection of representative solutions' from the subsolution composition method. The experiments on NVIDIA GeForce GTX580 GPU and Intel Core i7 2600 3.4GHz CPU show that the proposed algorithm solves 23-queens problem for 12 hours, 43 minutes, and 39 seconds. The time is about 4.5 times faster than the PC cluster (Intel Pentium4 Xeon 2.8GHz CPU x 68) at the university of electro-communications, which established the world record for 24-queens problem in 2003.
• 書誌レコードID / 収録物識別子タイプ: NCID
• 書誌レコードID / 収録物識別子: AA11362144
• 書誌情報: 研究報告ゲーム情報学（GI）; 巻 2012-GI-27, 号 7, p. 1-8, 発行日 2012-02-24
• Notice: SIG Technical Reports are nonrefereed and hence may later appear in any journals, conferences, symposia, etc.
• 出版者 / 言語: ja
• 出版者: 情報処理学会