スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

アルゴリズム勉強記③~ライフ・ゲーム&ナップザック編~

事典で'ラ'ディックスソートをひくと、その1個前にライフ・ゲームという項目がありました。
出ている図にはペントミノの絵があり、「おっ?」と思って読んでみるとどうやらセル・オートマトンらしい。
以前どう書く.orgでラングトンのアリをコマンドライン上に描写するプログラムを作った時、セル・オートマトンについて調べたのですが、そういえばあったような気もする。
とにかく、気になったらまずは書いてみっか! って感じのノリでライフ・ゲームに着手しました。

といっても結局「誕生」と「死滅」を条件でにょろにょろするだけなので、1時間弱で終了。
「最初の生命の数」「それぞれの座標値」を入力として、それを初期状態として1000世代分の動きを描写するようにしました。
とりあえずwikipediaに載ってたグライダーとかブリンカーとかを試してみる。うんちゃんと動く。おもすれー。終わり。

……結局何を学んだんだ……?
→とりあえずセル・オートマトンというジャンルを経験したということで。(でもラングトンのアリで経験はしてるんだよなあ……)



JOIとかについて書かれた記事とか見ると、やたらDPという単語が多い。中には「この問題はDP」で説明を片付けているものまで。なんだよDPって! ということで調べると、「動的計画法=Dynamic Programming」というものらしいです。
要するに、大きい問題を小さい問題に分割してから解いていく、ということでいい……んだよね?
で、事典で調べると、例題として「ナップザックの問題」というものが。コイツはメチャやらないわけにはいかないよなああ~~~

はい。やりました。
正直事典は何やってるのかよくわからなかったので、ネットで調べたところこちらの記事に非常にわかりやすい説明があったのでそれを頼りに。
なるほど、確かにまず「小さいナップザック」の最大値を出して、それに追従する形で「大きいナップザック」の最大値を出すという、小→大というのがなんとなくわかったようなそうでないような。
一応、ソース貼っときます。それぞれの式の解釈を(書かないと時間経ったら忘れそうなので)書いてみましたが、あってる……よな?

knapsack.txt

それにしても、重さ1~Wのナップザックに分けるというのはすごいなあと思いました。
私だったら有無を言わさず力任せ法に頼っていたことでしょうw こういう風に考えられるようになりたいです。

同じようにDPを使う問題で、Cleaning Robotという巡回セールスマン問題があったので、次回はそれをやってみたいと思います。この問題、前にやってみたことがあって、力任せで解いたら案の定タイムオーバーでしたので、リベンジするぞー!

それでは本日はここまでで。
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

コメント

Secret

プロフィール

PON4416

Author:PON4416
職業: 高校生

プログラミング歴: 2年弱

絵描き歴: '09年11月ごろから

趣味: プログラミング(C, C++)、お絵かき、漫画、アニメ、ゲーム

好きなもの: ジョジョ(2=3>1=4=7>5=6)、東方、うみねこ、ガンダム00、イカ娘

妖夢
嫁です(キリッ


Wilesの趣味的な人格。
最近PHPを始めたらしい。→やめたらしい

メール: yoshihiro[dot]hozumi[at]gmail[dot]com
skype: wiles4416

主にpixivで活動しています。
マイピクとか常に大募集してますw
プロフィールはこちらから



にほんブログ村 イラストブログ イラスト練習へ

最新記事
ひとりごと
最新コメント
月別アーカイブ
カテゴリ
ブロとも一覧

Weak's Smaller
割れ厨撲滅
検索フォーム
リンク
ブロとも申請フォーム

この人とブロともになる

QRコード
QRコード
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。