Upgrade to Pro
— share decks privately, control downloads, hide ads and more …
Speaker Deck
Features
Speaker Deck
PRO
Sign in
Sign up for free
Search
Search
動的計画モデル
Search
Masafumi Abeta
September 23, 2022
Science
0
130
動的計画モデル
「オペレーションズ・リサーチ」輪講会の発表資料です。
Masafumi Abeta
September 23, 2022
Tweet
Share
More Decks by Masafumi Abeta
See All by Masafumi Abeta
Pythonのパッケージマネージャー「uv」
abeta
0
41
GPTモデルでキャラクター設定する際の課題
abeta
0
210
GPTをLINEで使えるようにして布教した
abeta
0
120
【Nishika】プリント基板の電子部品検出
abeta
0
210
初心者向けChatGPT入門
abeta
0
180
GPT Short Talk
abeta
0
99
拡散モデルについて少しだけ
abeta
0
27
物体追跡
abeta
0
250
特徴量記述
abeta
0
160
Other Decks in Science
See All in Science
深層学習を利用して 大豆の外部欠陥を判別した研究事例の紹介
kentaitakura
0
230
拡散モデルの原理紹介
brainpadpr
3
4.8k
作業領域内の障害物を回避可能なバイナリマニピュレータの設計 / Design of binary manipulator avoiding obstacles in workspace
konakalab
0
160
教師なしテンソル分解に基づく、有糸分裂後の転写再活性化におけるヒストン修飾ブックマークとしての転写因子候補の抽出法
tagtag
0
120
位相的データ解析とその応用例
brainpadpr
1
620
Factorized Diffusion: Perceptual Illusions by Noise Decomposition
tomoaki0705
0
220
科学で迫る勝敗の法則(名城大学公開講座.2024年10月) / The principle of victory discovered by science (Open lecture in Meijo Univ. 2024)
konakalab
0
200
ultraArmをモニター提供してもらった話
miura55
0
190
ベイズ最適化をゼロから
brainpadpr
2
810
General Parasitology
uni_of_nomi
0
120
How were Quaternion discovered
kinakomoti321
2
1.1k
【人工衛星】座標変換についての説明
02hattori11sat03
0
110
Featured
See All Featured
Git: the NoSQL Database
bkeepers
PRO
427
64k
The Art of Programming - Codeland 2020
erikaheidi
52
13k
Visualizing Your Data: Incorporating Mongo into Loggly Infrastructure
mongodb
42
9.2k
Making Projects Easy
brettharned
115
5.9k
Product Roadmaps are Hard
iamctodd
PRO
49
11k
Why You Should Never Use an ORM
jnunemaker
PRO
54
9.1k
Documentation Writing (for coders)
carmenintech
65
4.4k
ピンチをチャンスに:未来をつくるプロダクトロードマップ #pmconf2020
aki_iinuma
109
49k
Statistics for Hackers
jakevdp
796
220k
Building a Scalable Design System with Sketch
lauravandoore
459
33k
The Success of Rails: Ensuring Growth for the Next 100 Years
eileencodes
44
6.8k
Building Adaptive Systems
keathley
38
2.3k
Transcript
XX University 9章 動的計画モデル 2022.07.03 Abeta
2 切符購⼊問題 スタート地点からゴール地点までの切符を買うとき、最も安くなる購⼊組み合わせを知りたい。 三島ー掛川=23940 三島ー静岡、静岡ー掛川=10680+9420=20100 ← 安い! 駅名 掛川 静岡
9420 静岡 新富⼠ 16020 7500 新富⼠ 三島 23940 10680 7500 三島 熱海 25140 14940 10620 6240 熱海 ⼩⽥原 27060 17220 13920 10080 6840 ⼩⽥原 新横浜 37740 27060 23940 17220 14940 10680 新横浜
3 動的計画法 ゴール地点から考える。 0をスタート、0からi-1までの最⼩費⽤が分かっているとし、 𝑝! , … , 𝑝"#$ と書く。
𝑗から𝑖への切符費⽤を𝑐%" と書く。 0 1 j i-1 i i+1 𝑝"#$ 𝑝% 𝑝$ 𝑝! 𝑐%" 再帰的な式が得られる。 𝑝" = ( 0 min %∈ !,$,…,"#$ (𝑝% + 𝑐%" ) 𝑖 = 0 𝑖 > 0 𝑐%" は三⾓表で与えられている。スタートとゴールが同⼀駅の場合は0として、再帰式を計算できる。
4 最適性の原理 最適性の原理・・・決定の全系列にわたって最適化を⾏うためには、初期の状態と最初の決定がどんなもので あっても、残りの決定は最初の決定から⽣じた状態に関して最適な⽅策を構成していなければならない。 → 𝑗 < 𝑖に対し、 𝑝" を最適化するための問題で解いた𝑝%
は、 𝑝% を最適化するための問題においても最適解と なっている。 0 1 j i-1 i i+1 𝑝"#$ 𝑝% 𝑝$ 𝑝! 𝑐%" 𝑝"#$ を求める 問題の最適解 𝑝% を求める問 題の最適解 𝑝$ を求める問 題の最適解 𝑝! を求める問 題の最適解
5 計算量 • すべての分割を総当り 2 )*! + + C) =
2+ = 𝜊(𝑘+) 2 )*! + 𝑘 = 𝑛(𝑛 + 1) 2 = 𝜊(𝑛,) • 動的計画法
6 アミノ酸配列のアラインメント 問題としては⽂字列の類似さを⽐較する問題。 例)DELTAとDATAを⽐較する。 D_ATA DELTA DELTA DA_TA ⼀致は加点 不⼀致は減点
⽋損は減点 ⚠点数は⽂字に依存 • D-D=8点 • A-A=5点 • A-E=-1点 • A-L=-2点 • E-_=-8点 等 どこにギャップ( _ )を⼊れればスコアを最⼤化できるか? 9点 8点
7 𝑥 𝑦 アライン済 アライン済 ⽂字列𝑥と𝑦のアラインメントを考える。 具体例として、例えば𝑥 =RESEARCH、 𝑦 =DESIREとする。
最後のアラインメントは次のようになる。 E H アライン済 アライン済 E _ アライン済 アライン済 _ H ⽂字の選び⽅は3通りある。
8 2次元の動的計画法 𝑥の𝑖⽂字⽬と𝑦の 𝑗⽂字⽬までアラインメントが済んでいるとき、そのときの最適スコアを𝑠[𝑖, 𝑗] とする。 𝑠[𝑖, 𝑗]に辿り着く道は3通りある。その3通りのう ちスコアが最⼤になる状態を採⽤する。 𝑠[𝑖,
𝑗] = max { 𝑠 𝑖 − 1, 𝑗 − 1 + 𝑏 𝑥" , 𝑦% , 𝑠 𝑖 − 1, 𝑗 − 8, 𝑠 𝑖, 𝑗 − 1 − 8 } −8𝑗 −8𝑗 0 𝑖 = 0, 𝑗 > 0 𝑖 > 0, 𝑗 = 0 𝑖 = 𝑗 = 0 𝑖 > 0, 𝑗 > 0
9 ⾏列積の計算 𝑝! ×𝑝$ ⾏列と𝑝$ ×𝑝, ⾏列の積を計算するとき、掛け算の回数は𝑝! 𝑝$ 𝑝, となる。
3つの⾏列𝐴$ ×𝐴, ×𝐴- の⼤きさが10×100, 100×5, 5×50のとき、 (𝐴$ ×𝐴, )×𝐴- → 10×100×5 + 10×5×50 = 7500 𝐴$ ×(𝐴, ×𝐴- )→ 10×100×50 + 100×5×50 = 75000 となり、積の順序で掛け算回数が変わる。掛け算回数を最⼩にしたい。
10 分割の動的計画法 ⾏列𝐴$ 𝐴, ⋯ 𝐴+ の最後の分割を(𝐴$ ⋯ 𝐴" )(𝐴".$
⋯ 𝐴+ )に決定する次に(𝐴$ ⋯ 𝐴" )と(𝐴".$ ⋯ 𝐴+ )を分割して、、、と 繰り返すことで動的計画法を適⽤できる。 𝐴" 𝐴".$ ⋯ 𝐴% の掛け算量を𝑚[𝑖, 𝑗]とする。分割の位置を (𝐴" ⋯ 𝐴) )(𝐴).$ ⋯ 𝐴% )のように探索すれば、次の再帰式を 得る。 𝑚[𝑖, 𝑗] = ( 0 min "/)/%#$ {𝑚 𝑖, 𝑘 + 𝑚[𝑘 + 1, 𝑗] + 𝑝"#$ 𝑝) 𝑝% } 求めたいものは𝑚[1, 𝑛]である。 𝑗 − 𝑖 = 𝑘のとき、 𝑗0 − 𝑖0 = 𝑘 − 1となる𝑚[𝑖′, 𝑗′]が 全てわかっていれば再帰式を計算できる。 𝑖 = 𝑗 𝑖 < 𝑗
11 最短路問題 有効グラフの最短経路を考える。 𝑑(𝑣) = ( 0 min 1∈23(5) (𝑑
𝑢 + 𝑤15 ) 𝑣 = 𝑠 𝑣 ≠ 𝑠 スタート𝑠から頂点𝑣までの最適経路⻑を𝑑(𝑣)とする。 再帰計算をどこから始めればよいか⾃然な順序はない。
12 ダイクストラ法 • 全てのエッジのコストが 0 以上であること。 • 負のコストがある場合はベルマン・フォード法。 • ナイーブな計算量は𝜊(𝑉,)。
• ヒープ法で𝜊(𝐸 + 𝑉log 𝑉)になる。 • 順序的に解くので並列化不可能。
13 最適化問題でない動的計画法 道の数え上げ 𝐹" = W 1 𝐹"#$ + 𝐹"#,
𝑖 = 1,2 𝑖 ≥ 3 1から6に⾄る道の本数を知りたい。
14 最適化問題でない動的計画法 Banzhaf指数 例)A,B,Cの3つの政党がある。議席数はそれぞれ10,10,1とする。過半数11で議案を通すことが出来るとき、 議案を通せる提携(党の連⽴の組み合わせ)は{A,B,C},{A,B},{B,C},{C,A}である。この集合の意味で、A,B,Cは 対等になっている。 ⼀般化して𝑛個の政党があるとする。政党の集合を𝑁と表す。空集合も提携と呼ぶ。政党𝑖の議席数を𝑤" とする。 投票が𝑞以上のとき議案を通せるとする。 Banzhaf指数は政党𝑖を含まない敗北提携のうち、政党𝑖を加えると勝利提携になるものの数を2+#$
で割った値。 𝛽" = | 𝑆 ⊆ 𝑁 ∖ 𝑖 2 %∈7 𝑤% < 𝑞 ≤ 𝑤" + 2 %∈7 𝑤% }|/2+#$
15 例 𝑛 = 7, 𝑤$ , 𝑤, , 𝑤-
, 𝑤8 , 𝑤9 , 𝑤: , 𝑤; = 1,1,2,1,3,1,1,3 , 𝑞 = 8の例。 𝛽; を求める。 8未満かつ3加えたら 8以上になるもの。
16 動的計画法まとめ • 最適原理に基づく⽅法。 • 現在では多種多様の⽅法に発展して動的計画法という名前が指すものの実態がよく分からなくなった。 • 動的計画法は、実際の時間順と逆順に問題を捉え、時間順にどのような情報を積み上げておけばよいか⾒ つけることで、算法を得られる。 •
図を描け。