高校生がアルゴリズムとスパコンの力で、京都の碁盤目状道路を13.9%効率化した話 - Qiita
2. 本研究で解く問題 「いざ研究しよう！」と思っても、条件や設定を決めないと何も始まりません。 まずは研究を分かりやすくするために、「一つの問題」に落とし込むことにしました。 問題設定 縦 $N$ 行・横 $N$ 列の大きさの碁盤の目があります。隣り合う交差点間の距離は 1 です。つまり、交差点が合計で $N^2$ 個あり、それぞれ座標 $(1, 1), (1, 2), ..., (1, N),$ $(2, 1), (2, 2), ..., (N, N-1), (N, N)$ に位置すると考えることもできます。 下の図は、$N = 4$ の場合の交差点の位置です。 あなたは、碁盤の目の交差点の位置は変えずに、道路の並びのみを変えることができます。上手く道路の並びを変えることで、できるだけ「便利」な道路網を建設してください。 「便利な道路網」って何？ 私は、以下の 2 つの条件を満たす道路
5次魔方陣を一般的なコンピュータで10分で実行したという記事に対しての考察 : mswinvksの忘備録
[急いで打ったので文がぐちゃぐちゃですし強調等もないです。すみません。] [定期的に記事の一番下にこっそりと僕のコメントを追加しています。一応ご確認ください] このような記事を発見しました。 スパコンで約2時間36分かかったという、5×5の魔方陣の全解列挙を、パソコンで試す（C++） 魔方陣の総数を求める、ということを、僕はスーパーコンピュータT2K-Tsukubaで約2時間30分で計算しましたが、この記事では一般的なコンピュータで10分で計算した、というものです。挑発的ですね。 僕のプログラムを1コア上で実行すると約200時間かかりました。(2012年ごろのAMD Opteron) (TODO:スパコンでの実行時間から1コア上での実行時間を割り出すと、200時間からかけ離れてるけどなんでだろう?) そして、この記事での実行環境は12コアなので、1コア換算すると実行時間は10分*12コア=
スパコンで約2時間36分かかったという、5×5の魔方陣の全解列挙を、パソコンで試す（C ） | 配電盤
魔方陣の解の列挙は並列化しやすそうな問題ですが、ここでの方針では、探索効率を上げるためには条件分岐が不可欠なので、（「数」を求めるだけだとしても）GPGPUでうまくやる方法がわかりません。そこで、CPUに載っているコアのみで並列化します（Xeon Phiなら簡単なのでしょうか→追記参照）。 一番外側の、0から(1<<25)-1まで変化する変数iのループをOpenMPで並列化します（schedule(guided)では遅くなります。schedule(auto)はVisual C++でサポートされたら試します）。変数iは上の図の緑の部分（カンで5個にしました）を各数5ビットで表現し、つなげたものです。マスに入りうる数は1から25までなので、5ビットというのはちょっと冗長ですが、とりあえずはよしとしましょう。 出力はバイナリ形式で、1つの解に25バイト使います（1つのマスに入る数を1バイトで表現
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
