ぽんこつでばいす


	FC2カウンター


	最近の記事アルゴリズムデザイン (08/23) また一月 (07/02) SSAOモドキ (06/02) シンプレックス法 (05/13) 線形計画法 (04/27)


	最近のコメントあるけ:GDC2008 グラフィック (04/27) とおりすがり:GDC2008 グラフィック (04/20) あるけ:GDC 2008 (03/12) あるけ:GDC2008 グラフィック (03/12) じゅん:GDC2008 グラフィック (03/09) 修行中のPG:GDC 2008 (03/09) あるけ:GJK アルゴリズム説明 (02/19)


	最近のトラックバック一語で検索:安倍総理 (08/26) ◆走食見聞録《ブログ》◆:ソウ２＠SAW２ (11/05) えいが　どっと　ねっと:「コープス・ブライド」を観た！ (10/24) 映画に学ぶ:｢ティム・バートンのコープス・ブライド｣ (10/23)


	カテゴリーヒビ (26) ぷろぐらむ (48) いんふぉめーしょん (5) セイジ (5) いんてりあ (5) カブ (7) 未分類 (0) ぷろぐらむ - GJK (6) ぷろぐらむ - Math (2) ぷろぐらむ - 色彩工学 (3) ぷろぐらむ - 線形・非線形計画法 (2)


	ブロとも申請フォームこの人とブロともになる


	ブログ内検索


	RSSフィード最新記事のRSS 最新コメントのRSS 最新トラックバックのRSS


	リンク管理者ページこのブログをリンクに追加する


	ＱＲコード

08
↑

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

↓
10

ぽんこつでばいす日々のこととかプログラムのこととかインテリアのことなんかを不定期に更新する日記

2008/08/23(土) 01:20	アルゴリズムデザイン	いんふぉめーしょん
面白そうな本があったから紹介。アルゴリズムデザイン値段は高いけど、内容は濃そう。相変わらず激務です・・・。家着くの２時で会社出社が８時４５分とか。やりたいことあるけど、何もできーんヽ( `Д´)ﾉｳﾜｧｧｧｧﾝ残念ながら CEDEC もいけそうにないし・・・。（´・ω・`）もう少しなんでがんばります・・・。
コメント：0 　トラックバック：0

2008/07/02(水) 01:04	また一月	ヒビ
空いちゃってます('A`) なんか変な広告出ちゃったし・・・。今、本業が忙しくてなかなか更新できてません。。一応、レムケ法のサンプル実装をまとめたものがあるので、ネタがないわけじゃないんだけど・・・。ただ、説明文書いてないんだよね。しかも実装わかりにくいし。。。とりあえず、もうすこしかかりそうです。
コメント：0 　トラックバック：0

2008/06/02(月) 23:50	SSAOモドキ	ぷろぐらむ
Screen Space Ambient Occlusion モドキを実装してみました。あくまでモドキです。実際のSSAOとは似たような処理をしてるけど、結構違います。法線方向の Occlusion とか実装してないし。それにしても、この考え方は結構面白いなぁ。他でも何かに使えるかも。ちなみに参考にした文献を挙げます。 nVidia の Developer ページのGDC 2008 関連のところにあるReal-Time Ambient Occlusion ってPDFです。近いうちにちゃんとしたヤツを実装してみます。
コメント：0 　トラックバック：0

2008/05/13(火) 01:07	シンプレックス法	ぷろぐらむ - 線形・非線形計画法
前回は線形相補性問題に入る前に理解を深めるため、線形計画問題の具体的な例を挙げてみました。今回はどうやって解いたか？を説明します。そういうわけなので、前回の例をそのまま使ってみます。前回の例で挙げられた目的関数は　3020 + (5 * x1) + (8 * x2) + (6 * x3) + (4 * x4) + (5 * x5) + (2 * x6) -> min です。定数項は（当たり前ですが）変化しないので問題に関係していません。ですので、カットしちゃいます。よって、目的関数の本質は　(5 * x1) + (8 * x2) + (6 * x3) + (4 * x4) + (5 * x5) + (2 * x6) -> min 　になります。次に制約条件は以下になります。　k1 >= 0 + ( 40 - x1) 　k2 >= k1 + (150 - x2) 　k3 >= k1 + (200 - x3) 　k4 >= k1 + (100 - x4) 　k5 >= k2 + ( 50 - x5) 　k5 >= k3 + ( 50 - x5) 　k6 >= k4 + (100 - x6) 　k6 >= k5 + (100 - x6) 　k6 <= 240 　　x1 <= 10 　x2 <= 50 　x3 <=150 　x4 <= 50 　x5 <= 40 　x6 <= 60 　　x1 >=　0 　x2 >=　0 　x3 >=　0 　x4 >=　0 　x5 >=　0 　x6 >=　0 　左辺式と右辺式を分離しています。以上が数式です。数式を挙げて措きながらなんですが、もう一度問題を見直して見ましょう。この問題の制約条件は、関連性　企画-+-> プログラム -+-> レベル調整 -+->デバッグ　　　　 +-> デザイン　　-+　　　　　　　　　　\| 　　　　 +-> サウンド ------------------+ と、作業日数・減らせる作業日数から成り立っています。ならば、一番効率よく減らすにはボトルネックになっている部分を減らすべきでしょう。まずはじめに、予定日数どおりに（予算を余分にかけずに）プロジェクトを遂行した場合、何日掛かるか調べてみます。予定日数は　企画　　　：　 40 　プログラム：　150 　デザイン　：　200 　サウンド　：　100 　レベル調整：　 50 　デバッグ　：　100 　　なのと、関連性を加味すると、　40 -+-> 150 -+-> 50 -+-> 100 　　　　+-> 200 -+　　　　　\| 　　　　+-> 100 --------+ になります。上記のルートで（制約になる関連性を無視して）最大日数になるのはデザインのルートっぽいですよね。ですので、そこの予定日数を出してみると、　40 + 200 + 50 + 100 = 390 　になりました。制約は 240 日以内ですので、150 日ぐらい減らせば良さそうです。ちなみに、プログラムのルートでは　40 + 150 + 50 + 100 = 340 　同じくサウンドのルートでは、　40 + 100 + 100 = 240 　になります。制約になる関連性を無視すれば、サウンドは既に240日以内ですね。なので、以降は簡略化のために省きます。以上、日数を上げてみて気付いたと思うのですが、企画とデバッグの作業日数を短縮できれば全体の作業日数をストレートに減らせそうです。ですが、どちらを先に減らせばいいのでしょうか？この問題の目的は費用の最小化を図るためなので、「作業日数を減らすために掛かる費用が少ない方」に対して優先的に予算を割り振ればいいと考えれます。そこで、作業日数にかかる費用を挙げてみます。これは目的関数に組み込まれていますね。　企画　　　 : 5 * x1 　プログラム : 8 * x2 　デザイン　 : 6 * x3 　サウンド　 : 4 * x4 　レベル調整 : 5 * x5 　デバッグ　 : 3 * x6 先ほど言ったように、定数項は問題の本質とは関係ないので除去しています。さて、デバッグと企画のどちらが掛かる費用が少ないか？は上記を見ればわかります。企画が 5 でデバッグの方が 3 なので、企画の方が高いです。ですから、デバッグの方に優先的に費用を割り振ります。最大限減らせる日数は決まっていますから、最大限まで振っちゃいましょう。すると 60 日まで減らせます。すると、それぞれの作業日数の予定は以下のようになります。　デザイン　：40 + 200 + 50 + (100 - 60) = 330 　プログラム：40 + 150 + 50 + (100 - 60) = 280 まだ作業日数が 240 日以内ではないので、今度は企画を減らします。企画は 10 日減らせますので、こっちも最大限減らします。すると、、、　デザイン　：(40 - 10) + 200 + 50 + (100 - 60) = 320 　プログラム：(40 - 10) + 150 + 50 + (100 - 60) = 270 になりました。まだまだ足りません。次に、デザインルートとプログラムルートで共通な工程のレベル調整を減らして見ましょう。ここをある程度減らせば、プログラムルートの方は 240 日以内に収まりそうです。しかし、デザインルートの方は 240 日以内に収まりません。では、レベル調整の作業日数を何日減らせばいいでしょうか？ここでも費用の式を見比べます。デザインルートで今まで減らした工程とこれから選択するレベル調整の工程以外に残った工程はデザインの工程のみです。ですから、デザインの工程とレベル調整の工程を費用式を見比べて見ましょう。　デザイン　 : 6 * x3 　レベル調整 : 5 * x5 デザインの方が係数が大きいですよね。ですから、レベル調整の工程を目いっぱい減らした方が費用が安いとなります。もしここで、デザインの工程の方が安い場合は、レベル調整をプログラムルートが240日以内に収まるように減らした後でデザインの工程を減らした方がいいとなります。ではレベル調整の工程を最大限まで減らしてみましょう。最大限減らせる日数は 30 日ですので、、、　デザイン　：(40 - 10) + 200 + (50 - 40) + (100 - 60) = 280 　プログラム：(40 - 10) + 150 + (50 - 40) + (100 - 60) = 230 この時点でプログラムルートは間に合いそうですので、デザインルートだけ考えることにします。デザインルートで残りの工程はデザインの工程になります。もう減らせる工程はここしかないので、ここを期間内で終わらせれるように減らしてみましょう。残りの超過分は 280 - 240 = 40 ですので、40 日減らせば間に合うとなります。ですので、　デザイン　：(40 - 10) + (200 - 40) + (50 - 40) + (100 - 60) = 240 　となり、全てのルートで期日内で終わることが保障されました。最終的に減らした日数を表にすると　企画　　　：10 　プログラム： 0 　デザイン　：40 　サウンド　： 0 　レベル調整：40 　デバッグ　：60 となり、費用は、　企画　　　 : 5 * 10 = 50 　プログラム : 8 * 0 = 　0 　デザイン　 : 6 * 40 = 240 　サウンド　 : 4 * 0 = 　0 　レベル調整 : 5 * 40 = 200 　デバッグ　 : 3 * 60 = 180 と出て、余分に掛かる費用の総和は　50 + 0 + 240 + 0 + 200 + 180 = 670 　となりました。以上の手順はやってることも単純な比較と式の代入ですし、なんとなく機械的に処理できそうです。そういうわけで、アルゴリズムとしてまとめたものが「シンプレックス法」となります。シンプレックス法の概念は説明した手順に若干手を加えたものになります。目的関数が最大化を目指す場合と最小化を目指す場合で違うのでは？と考えるかもしれませんが、同じアルゴリズムで扱えちゃえます。というのも、目的関数・制約条件両方にマイナスの値を掛けてやれば、最小化問題を最大化問題として、最大化問題を最小化問題として扱えるからです。例えば、a -> max にする問題と -a -> min にする問題で a の答えは変わりませんよね？そんなわけで、最大化する問題のシンプレックス法として以降の説明を書きます。まずアルゴリズムの簡単な流れは　①：制約式の不等号が等式になるような変数（スラック変数といいます）を導入し、等式に直す。　　　またこのとき、スラック変数は非負となるようにする。　　　　例えば、　　　　　a < b → a = b - λ → a + λ = b 　　　　　a > b → a = b + λ → a - λ = b 　　　　になる。　②：スラック変数を基底に置き、スラック変数の関係式と見る。　③：各制約式を同時に満たしながら基底以外の変数がどれだけ最大限まで増やせるのか？を調べる　④：最大限まで増やした結果、目的関数がどれぐらい増加するか調べる。　⑤：目的関数の増加が一番大きい変数を最大限まで増やしてみる。　⑥：⑤の結果、どこかの制約式で必ず基底 = 0 となるので、今度はその変数を基底と置く。　⑦：⑥で基底に置いた変数を各制約式と目的関数に代入し、⑥の基底変数を制約式と目的関数から消去する。　⑧：目的関数で変数の符号が + のものがある→増加する余地があるので、 + の符号の変数がなくなるまで ③ に戻る。　となります。まぁ、分かり難いですよねｗそんなわけで、前回のゲームプロジェクトとは別の（数式だけの）例を挙げてやってみます。　制約条件　　2x + 6y < 90 　　5x + 4y < 90 　　　目的関数　　25x + 22y -> max 　　ステップ : ① 　2x + 6y + λ(1) = 90 　5x + 3y + λ(2) = 90 ステップ : ② 　λ(1) = 90 - 2x - 6y 　λ(2) = 90 - 5x - 3y 　ステップ : ③ 　目的関数のうち、x も y もどちらも、増加したときに目的関数が増加するので、どちらがより多く増やせるか調べる。　y を無視して考えると x は λ(1) = 90 - 2x より 45、λ(2) = 90 - 5x より 18 よって 18、　x を無視して考えると y は λ(1) = 90 - 6y より 15、λ(2) = 90 - 3y より 30 よって 15 　ステップ : ④ - 1 　それぞれの目的関数の増加数は x : 25 * 18 = 450, y : 22 * 15 = 330。　よって、x を増やしたほうが目的関数が増える。　ステップ : ⑤ 　④の結果、λ(2) = 90 - 5x - 3y が λ(2) = 0 になる。　ステップ : ⑥ 　今度は x を基底にする　　5x　= 90 - 3y - λ(2) 　　x　 = 18 - 0.6y - 0.2λ(2) 　　ステップ : ⑦ 　各制約式と目的関数から x を削除する。　　λ(1) = 90 - 2(18 - 0.6y - 0.2λ(2)) - 6y 　　 = 54 - 4.8y - 0.4λ(2) 　　　　　25(18 - 0.6y - 0.2λ(2)) + 22y 　　= 450 + 7y - 5λ(2) ステップ : ⑧ 　⑦の結果、目的関数の中でまだ y が + なので、③に戻る　ステップ : ③ 　目的関数のうち、y が増加したときのみ目的関数が増加するので y が取り得る最大値を求める。　x = 18 - 0.6y - 0.2λ(2) より 30、λ(1) = 54 - 4.8y - 0.4λ(2) より 11.25 　ステップ : ④ - 2 　11.25 が y の取り得る最大値。　ステップ : ⑤ 　③、④の結果、λ(1) = 54 - 4.8y - 0.4λ(2) = 0 になる。ステップ : ⑥ 　今度は y を基底にする　4.8y = 54 - λ(1) - 0.4λ(2) 　y　　= 11.25 - 0.2083λ(1) - 0.0833λ(2) 　ステップ : ⑦ 　各制約式と目的関数から y を削除する　450 + 7(11.25 - 0.2083λ(1) - 0.0833λ(2)) - 5λ(2) 　528.75 - 1.4583λ(1) - 5.5833λ(2) 　ステップ : ⑧ 　目的関数の変数の符号に + が含まれなくなったので終了。　ということで、シンプレックス法が終了しました。結果、最大値は 528.75 と出ました。また、このときの x、y の値は ④-1・④-2より　x = 18 　y = 11.25 　になります。
コメント：0 　トラックバック：0

2008/04/27(日) 23:51	線形計画法	ぷろぐらむ - 線形・非線形計画法
久々に更新！ってことで、LCP関連のことをやります。本当はLCP(線形相補性問題)について書きたかったんですけど、前提条件ナシじゃ読めないのでその前の線形計画問題についてから入ります。いきなりですが、線形計画法の具体的な例を出してみたいと思います。身近なら話でも結構使われているんですよ。実は。そんなわけで、ゲーム開発を例にしましょうｗ今、ある会社が新作ゲームを作ろうとしています。問題を単純にするためにゲームの開発には６つの工程があるとします。その工程は、企画・プログラム・デザイン・サウンド・デバッグ・レベル調整としておきます。・・・かなり大雑把にしているので、突っ込まないでくださいｗそれぞれの工程には関連性があります。企画がないとプログラムは作れませんよね。同じようにプログラムがないとデバッグも出来ません。また、ゲーム開発に良くあることですが、始まる前からプロジェクトの終了期限は決まっています。ついでに、この会社には凄腕のディレクターがいるので、それぞれの作業に必要な日数はおおむね算出できていて、さらに余分に費用を掛ければある一定量までなら作業日数を減らせることもわかっています。（なんという超人的なディレクターｗ）もちろん、費用は掛からなければ掛からないほどいいので、費用は最小限に納めたいところです。どのように人員配置を行えば作業が期限までに終了し尚且つ費用も抑えれるでしょうか？こういう問題を解くのが線形計画問題といいます。では、上記の問題を数字を適当にでっち上げて実際に解いて見ましょう。まず、それぞれの作業日数と費用を表にしてみます。（この数字は現実のプロジェクトとはかなり差異があると思いますが気にしないでください）　　　　　　　　作業日数　　固定費　　余分に掛けられる費用の最大値　減らせる作業日数　企画　　　　　：　 40　　　　300万　　　　　　　50万　　　　　　　　　　　　　　　　 10 　プログラム　：　150　　　 1200万　　　　　　400万　　　　　　　　　　　　　　　　50 　デザイン　　　：　200　　　 1200万　　　　　　900万　　　　　　　　　　　　　　　150 　サウンド　　　：　100　　　　200万　　　　　　200万　　　　　　　　　　　　　　　　50 　レベル調整　：　 50　　　　100万　　　　　　200万　　　　　　　　　　　　　　　　 40 　デバッグ　　：　100　　　　 20万　　　　　　180万　　　　　　　　　　　　　　　　 60 　またそれぞれの工程には以下の関連性があるとします。　企画-+-> プログラム -+-> レベル調整 -+->デバッグ　　　　 +-> デザイン　　-+　　　　　　　　　　\| 　　　　 +-> サウンド ------------------+ 　　　プログラムとデザインが終わらないとレベル調整が出来ない・・・とかですね。現実では企画が完全に出来ないとプログラムが組めないとかではないので、この限りじゃありませんｗ飽く迄、単純に問題化した場合ですので、突っ込まないでくださいｗまた、このプロジェクトは 240 日以内という期限があるとします。以上を踏まえ、これを数式化します。まず、費用を掛けてどの程度作業日数を減らすか？は、まだ解らないのでそれぞれ x1, x2, x3, x4, x5, x6 とします。例えば、x1 が企画で減らした作業日数です。この変数を使って企画に掛かる費用を算出してみると、、、　企画： 300 + 50 / 10 * x1 同様にして、それぞれの費用を算出します。　企画　　　： 300 + 50 / 10 * x1 　プログラム：1200 + 400 / 50 * x2 　デザイン　：1200 + 900 / 150 * x3 　サウンド　： 200 + 200 / 50 * x4 　レベル調整： 100 + 200 / 30 * x5 　デバッグ　： 20 + 180 / 60 * x6 　次に作業日数の方の問題を数式化します。それぞれの作業が終わる日を k1, k2, k3, k4, k5, k6 とすると、、、　k1 >= 0 + ( 40 - x1) 　k2 >= k1 + (150 - x2) 　k3 >= k1 + (200 - x3) 　k4 >= k1 + (100 - x4) 　k5 >= k2 + ( 50 - x5) 　k5 >= k3 + ( 50 - x5) 　k6 >= k4 + (100 - x6) 　k6 >= k5 + (100 - x6) 　k6 <= 240 　また、最大限減らせる作業日数も決まっているので、以下の制約も加わります。　0 <= x1 <= 10 　0 <= x2 <= 50 　0 <= x3 <= 150 　0 <= x4 <= 50 　0 <= x5 <= 40 　0 <= x6 <= 60 これで全て数式化できました。問題としては、作業日数の制約を満たしながら費用の総和を最小化するということになります。費用の総和を最小化するように人員配置を決めたいので、目的関数は費用の総和ということになります。ということで、費用の式を直しましょう。　 300 + 5 * x1 : 企画　1200 + 8 * x2 : プログラム　1200 + 6 * x3 : デザイン　 200 + 4 * x4 : サウンド　 100 + 5 * x5 : レベル調整　 20 + 3 * x6 : デバッグよって、総和は　3020 + (5 * x1) + (8 * x2) + (6 * x3) + (4 * x4) + (5 * x5) + (2 * x6) -> min になります。ここまでで全てが数式化できました。プロジェクト運営が数学の問題になってしまうのが面白いと思いませんか？要するに、制約条件と目的関数さえ数式化できれば、どんな問題でも数学の問題として扱えてしまうわけです。（解ける・解けないは別にして）こういう日程計画問題で有名なものにアメリカがミサイル開発の時に作った PERT というものがあります。アポロ計画などにも利用されたようです。他にはロジスティクスの分野で運送費用を最小限にするためにはどのように倉庫を配置すべきか？という問題も単純なモデル化を施せば線形計画問題になります。閑話休題。では、以上のことを踏まえてこの問題を解いてみると、、、　x1 = 10 　x2 = 0 　x3 = 40 　x4 = 0 　x5 = 40 　x6 = 60 　　k1 = 30 　k2 = 180 　k3 = 120 　k4 = 200 　k5 = 200 　k6 = 240 となり、このときの余分な費用の総和は「670万」、全体の費用としては「3690万」と出ました。費用についての最適解が得られたわけです。もちろん、日数に余裕を持たせたいなら x6 <= 240 の左辺を減らせば費用は増えますが日数は減ります。工程が一つ増えたり、プログラムの作業期間を限定したいなら、そのように制約条件を増やせば解を求めることが出来ます。まとめると、線形計画問題とは　１：目的関数が１次式　２：制約条件も１次式（不等号・等式、どちらでも可）の上で、制約条件を満たしつつ目的関数の最適解（最大値や最小値）を求める問題になります。さて、次回はどんなアルゴリズムでこの問題を解いたか？を説明したいと思います。・・・これぐらいの関係式ならわざわざプログラムで組む必要もなさそうなもんだけどねｗ
コメント：0 　トラックバック：0

Home　 NextPage

	copyright © 2005 ぽんこつでばいす all rights reserved. Powered by FC2ブログ template designed by わにわにちゃん
無料ホームページアフィリエイトレンタルサーバー FC2ブログ一戸建て