Entries

パズル「目盛りの消えた定規」について Part2

 ……前回3時間とか書きましたが、アルゴリズムが違えば所要時間も当然違います。例えば、tamura70さんのサイトでの記事(http://d.hatena.ne.jp/tamura70/20100112/ruler)に載っているソースコードは、本人曰く

どの答えが最初に求まるかは,プログラムで行っている探索方法によると思います.
上のプログラムでは,mark[i] が i cm目の位置に目盛があるか
どうかを表しています.まず1cm目には必ず目盛があるとします
(mark[1] = YES).次に r-2 cm, r-3 cm, ..., 2cm の順に
その長さが測れるように目盛を追加しています.あらゆる場合を
試すために再帰的なプログラムになっています.
solve(k, m) がそれに相当し, k が次に測れるようにしたい
長さで, m は追加できる目盛の残りの個数です.

らしいです(無修正)。そして計算時間も、"68(13)=1+1+3+5+5+11+11+11+6+6+6+1+1"と表示されるまでに3.3分です(前回と同環境にて測定)。……私の努力は何だったのか。
(もっとも、アルゴリズムが違う=表示される数値も違う、ということになります。暇があったら見比べてみてね)


 この計算の面倒なところは、ソースを見れば薄々分かると思いますが、並列化が難しいというところにあります。もちろん私の書いたコードでは、同時に複数回シフトして、判定を並列化すれば速くはなりますがたかが知れていますし(68(13)で計算時間の差が50倍以上ある時点で焼け石に水)、tamura70さんのコードは再帰&グローバル変数を使い倒しているせいで並列化 or メモ化できませんし。シングルコアでのクロック数の限界はすぐ見えていますので、このままだと大した時間短縮が望めないのです。悩ましいことです。


 実はこの問題、別にパズル好きの道楽というわけではありません。海外では「Sparse ruler」(まばらな定規)としてよく知られた問題なのです。Perfect and Optimal Rulersによると、183(22)まで計算は完了している模様です。うーん、やっぱりアルゴリズムの差かな。


 最後に、私がこの問題を最初に知った本と、
数学パズルで遊ぼう数学パズルで遊ぼう
(1997/09)
木村 良夫

商品詳細を見る


とある大学で課題に出された例を紹介します。
情報知能工学演習VI: Prolog 課題問題(第2回)


 ひとまずこの話は終わり。

2013/05/04追記:
紹介した本を間違えていたので修正。木村良夫さんには悪いことをしました。
関連記事
スポンサーサイト
この記事にトラックバックする(FC2ブログユーザー)
http://ysrken.blog.fc2.com/tb.php/40-826a8887

トラックバック

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

Appendix

プロフィール

YSR

Author:YSR
「YSR」「YSRKEN」「◆YSRKENkO6Y(~2013/08/25)」「◆YSRKEN.ceVZZ(2013/08/26~)」として活動しています。
プログラミングと艦これが趣味です。
プロフ画像はCrystalDiskInfoの水晶雫ちゃんです。
主な創作物についてはhttp://ysrken.blog.fc2.com/blog-entry-76.htmlをご覧ください。

カレンダー(月別)

10 ≪│2017/11│≫ 12
- - - 1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 - -

全記事表示リンク

全ての記事を表示する

QRコード

QR

総アクセス数

アクセス数

現在の閲覧者数: