パスワードを忘れた? アカウント作成
9022 story

電通大がN-Queens問題の最高記録を更新 59

ストーリー by Oliver
女王バトル 部門より

teltel曰く、"電気通信大学のニュースリリース によれば、同大並列処理学講座は古典的な数学問題のN-Queens 問題の世界最高記録を更新した。
N-Queens 問題は、NxN のチェス板にN個のQueenをお互いに攻撃できないように配置するならば配置のしかたがいくつあるか、という問題で、よくプログラミングの課題になったりする。この問題はN が増えると配置方法も急激に増え、N=23 の解までしか計算されていなかった。電通大のグループはN=24 の解を世界で初めて解いた。
同グループのN-Queens 問題のページ によれば、計算に用いたのはXeon 2.4GHz を搭載した68 ノードのクラスタ。N=24 の解を解くのに22 日かかったという。また上記ページでは、N-Queens 問題を解くプログラムも公開されている。MPI を用いた並列版と1 CPU版が同時にダウンロードできる。タレコみ人が試しに1CPU 版をVine Linux 2.6 上でコンパイルしたところ問題無かった。簡単なベンチマークとしても使えて、N=18 を解くのに1697.538sec かかった。この分だと、N=24 を解くには2000000000sec = 60 年位はかかりそうだ。"

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
typodupeerror

※ただしPHPを除く -- あるAdmin

読み込み中...