プログラミングパズルに関心のある人は雑談しましょう!
Nクイーンのアルゴリズム読みました。 ビット演算がなかなか渋い処理ですね。 無駄のないビット演算に少ししびれました。 サイト掲載の方法だと手作業を効率化していますよね。 行列とか高度な数学を使ってもっと効率よく求めたりとかないものですか? ルールの線形性や隣の列の制約の伝播の単純さを考えた時何か賢い方法とかありそうに思えます。 私この分野素人なのですが、やはりこの手の高速化はNP困難問題とかがあって無理とかでしょうか?
http://1c-job.net このサイトにはプログラマーとして必要だと思うことが載っています。 これをとっかかりにしてプログラムに興味が出てくること間違いないです。
高橋さん、こんばんは。deepgreenです。 GPUのプログラミングは、deepgreenも今回が初めてです。keiさんに教えていただいて 基本的な処理はできるようになりました。GPUプログラミングも初歩的なものは難しくありません。 (keiさんのように誰か相談できる人がいるとより簡単に入れるでしょう) nq_symGもカーネル関数は簡単です。PC側はスレッド制御が入っているのでちょっと面倒ですけど。 (これはGPUの知識ではないので必須ではありません)QJHに較べれば、易しいとおもいます。 価格面でいうと、GPUボード1枚は数万円(GTX580)ですので、これをPCIexpressバスに接続して、 ドライバとCUDAのSDKをインストールすればできます。ただし、deepgreenはハードが全くダメなので、 Built-inのゲームパソコンを買いました。それでも、十数万円です。一昔前のPCの値段というところでしょう。 それだけの準備(投資)で、うまくすれば1ケタ性能が上がりますから、おいしい選択枝と考えています。 そもそもの発端は、2010年の7月にkeiさんからQJHのソース公開の依頼から始まりました。 keiさんはGPUを使った並列処理の研究をしていて、その題材にQJHを選んだのです。 しかし、QJHはメモリシステムの負荷が高く、簡単にGPUに乗せることは困難なようです。 (実は、deepgreenは今この問題で悩んでいます。なんとかしたいのですが。。。) 昨年の6月末にGI-26の発表に行く途中でkeiさんとお会いして、Somers(GPU)版にQJHの(I,J)フィルタ を取り込めば、今より3〜4倍高速になるかもしれませんねという話をしました。その後、keiさんと その実装を行い、今回のような予想以上の成果となりました。 QJHをどう変えたらGPU向けの構造にできるのかが目下の課題です。
deepgreenさん、こんちには。 N=23を約12時間で処理したとは、ただただ唖然とするのみです。 概要はなんとなく理解しましたが、ソースコードは全く理解不能です。 GPUをソルバーに利用するという新しい試みには大いに興味が沸いたのですが、 GPUを理解するのに時間とお金がかかりそう、という高い敷居も感じます。 とはいうものの、新しい風を感じます。今はチンプンカンプンですが。
こんばんは。 deepgreenです。 2012年3月2日に行われた第27回ゲーム情報学研究会(GI-27)に、GPU(グラフィックアクセラレータ) を使ったNQueens問題の高速Solverについて発表しました。 主な成果は、以下のとおりです。 測定環境:ゲームパソコン1台 ( Intel CORE i7 2600 3.4GHz CPU と NVIDIA GeForce GTX580) ・N=23の問題の求解時間 12H 09M 43S --> 電通大のPCクラスタの約4.7倍高速 ・Somers版(オリジナル版)の約166〜196倍高速 その時の論文とソースを下記のdeepgreenのHPで公開します。 http://deepgreen.game.coocan.jp/
こんにちは。deepgreenです。 今年の始めに、GPCCの最小公倍図形の問題に挑戦すると書いてしまったので、 その結果をお知らせします。 今回の探索の結果、Tペントミノ68個の解があることをみつけました。結果は、 下記のdeepgreenのHPにUpしましたので、お時間がありましたらどうぞ。 http://deepgreen.game.coocan.jp/
・・・・・・・・・・・・・・・・・・・・・・・・・・・・・ ◎・・・・・・・・・・・・・・・・★・・・・・・・・・・∩ ※・・・・・・・・・・・・・・・・□・・・・・・・・・・∪ ・・・・・・・・・・・・・・∩・・・・・・・・・・・・・□ ・・・・・・・・□・・☆・・∪・・・・・・・□・・□・・・ □・・・・・・・・・・☆・・□・・・・・・・・・・・・・□ ・・・□・・・・・・☆★・・◎・・□・・・・・・・・・・・ □・・・・・・・・・※※・・※・・・・・・・・・★★・・□ ・・・・・・★・・・・・・・・・・・・・・・・・※※・・・ ・・・・・・※・・・・・・・・・・・・・★・・・・・・・□ ・・・・・・・・・・・・・・・・・・・・※・・・・・回田・ ・・・・・・・・・・・・・・・・・・・・・・・・・・田田□ ・☆・・・・・・・・・・☆・☆・☆・・・・・・・・・田田・ ※※≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡≡※※※※
★⊂⊃⊂⊃★☆⊂⊃⊂⊃★⊂⊃☆⊂⊃☆⊂⊃☆★☆⊂⊃☆⊂⊃★ ☆☆・★・⊂⊃・★★・⊂⊃☆☆・★⊂⊃⊂⊃⊂⊃・⊂⊃・⊂⊃ ⊂⊃⊂⊃★・★☆⊂⊃☆☆・⊂⊃☆⊂⊃☆・★☆・☆★・☆☆・ ・★・★⊂⊃⊂⊃・★⊂⊃・★⊂⊃・★⊂⊃⊂⊃⊂⊃⊂⊃⊂⊃☆ ◎⊂⊃⊂⊃☆★・・⊂⊃★⊂⊃★⊂⊃⊂⊃★・☆★・・☆★・☆ ☆・★・☆⊂⊃⊂⊃・★※★⊂⊃★⊂⊃★⊂⊃⊂⊃⊂⊃⊂⊃⊂⊃ ☆・⊂⊃※★・・★・⊂⊃※★・※・★⊂⊃☆★・・☆・☆☆・ ☆・・★⊂⊃★⊂⊃☆・★⊂⊃⊂⊃⊂⊃☆★⊂⊃⊂⊃⊂⊃⊂⊃☆ ☆・・⊂⊃⊂⊃☆⊂⊃☆⊂⊃☆・☆★・☆⊂⊃・☆☆☆★・★☆ ☆・・・☆・⊂⊃☆⊂⊃・★⊂⊃⊂⊃⊂⊃・☆⊂⊃⊂⊃⊂⊃⊂⊃ ☆回田・※・☆・※・☆・※★・・☆・★・※☆・★・・☆・★ ☆田田●・⊂⊃・●・⊂⊃・●・⊂⊃・●・⊂⊃・●・⊂⊃・★ ☆田田※≡≡≡≡※≡≡≡≡※≡≡≡≡※≡≡≡≡※≡≡≡≡≡ ≡※※※※※※※※※※※※※※※※※※※※※※※※※※※※
・・・・・・・・・・・・・・・・・・・・・・・・・・・●・ ・・・・・・・・・・・・・・・・・・・・・・・・・・・□□ ・・・・・・・・・・・・・・・・・・・・・・回田・・・□□ ・◎・◎・・・●・・・・・・・・・・・・∩∩田田・・・□□ ・□・□・・□□・・・・・・・・・・・・∪∪田田・・・□□ ・□・□・・・・・・・・・・・・・・・□□□□□□・・□□ ・・・・・・・・・・・・・・∩・・・・□□□□□□・・・□ ・・・・・・・・・・・・・・∪・・・・□・・・・・・・・□ ・・・・・・・・・・・・□□□□□□□□・・・・・・・・□ ・・・・・・・・・・・・・・・・・・・・・・・・・・・・□ ・・・・・・・・・・・・・・・・・・・・・・・・※・・・・ ・・・・・・・・・・・・・・・・・・・・・・・・・・・・・ ・・・・・・・・・・・※※※・・・・・・・・・・※∩・・・ ≡≡≡≡≡≡≡≡≡≡≡※※※・・・・・・・・・◎※∪●・・
・・・・・・・・・・☆・・・・・・・・◎・・・・・・・◎・ ∩・・・・・・・・・※・・・・・・・・※・・・・・・・●・ ∪・・・・・・・・・・・・・・◎・・・・・・・・・・・□・ □・・・・・・・・・・・・・・□・・・・・・・□・・・□・ ・・・□・・□・・・・・・・・・・・・・・・・・・・・・◎ ・・・・・・・・・・□・・・□・・・・・・□・・□・・・□ ・・・・・・・・・・・・・・・・・・・●・・・・・・・・・ ☆・・・・・・・・・・・□・・・・・・※・・・・・・・・・ ※※※・・・・・・・・・□・・・・※・・・・・・※・・・・ ※・・□□・・□・・・・□・・□・・・・・・・・・□・・・ ※※※・・・・・・・・・・回田・・・・・・・・・・・・・・ ※・・・∩・・∩・・・・・田田・・・・・・・・・・・・・・ ※・☆・∪・・∪※・※・・田田・・・・・・※・・・・・・※ ≡≡≡≡≡≡※※※≡※※※※※※※≡≡≡≡≡≡≡※※≡≡≡