『Pythonで体験してわかるアルゴリズムとデータ構造』メモその9/クイックソートの早さを知ろう
『Pythonで体験してわかるアルゴリズムとデータ構造』を読みながらアルゴリズムについて勉強する。
- 作者: 西澤弘毅,森田光
- 出版社/メーカー: 近代科学社
- 発売日: 2018/06/30
- メディア: 単行本
- この商品を含むブログを見る
第9章分割統治法によるソートの分類
この章のゴールは
クイックソートとは
1960年にアントニー・ホーアが開発したソートのアルゴリズム。分割統治法の一種。
n個のデータをソートする際の最良計算量および平均計算量はO(n\log n)である。
他のソート法と比べて、一般的に最も高速だといわれているが対象のデータの並びやデータの数によっては必ずしも速いわけではなく、最悪の計算量はO(n^{2})である。また数々の変種がある。 安定ソートではない。
クイックソート - Wikipedia
クイックソートのやり方としては、適当な数（ピボット）を要素からとってきて、そのピボットよりも大きいか小さいかでまず大きく分割する。
分割を行うと、「ピボットよりも小さい値」「ピボット」「ピボットよりも大きい値」の3種類できる。
イメージとしては以下。
クイックソートの平均計算時間は となっている。
今までのソートよりも早いのだが、それはなぜか。
クイックソートは必ず上の3パターンとなる。 それが要素が1になるまで繰り返されるソートになる。
早く要素が1になってしまえば、それだけ比較回数を抑えることができる。
この場合、桁数が7に対して処理回数が3回で交換回数が10回。 普通にバブルソートで交換するよりも断トツで早いのが分かる。
逆に最悪計算時間は
ピボットに対して大きい小さいの種類が片方に寄ってしまっている場合に遭遇する。ソート済みの状態で実施すると大体こうなる。
これを見ると分かるように普通にバブルソートしているのと変わらなくなってしまう。
実装
def sort(A): if len(A) < 2: return A p = A[0] print("ピボットは{}".format(p)) X, Y = divide(p, A[1:]) print() print(X, Y, "をそれぞれ同じようにソート") return sort(X) + [p] + sort(Y) def divide(p, A): if len(A) < 1: return ([],[]) print("0番目の要素を{}を取り出す".format(A[0]),A[1:]) X, Y = divide(p, A[1:]) a = A[0] print("{}より{}が小さいか".format(p, a)) if a < p: print([a] + X, Y) return ([a] + X, Y) else: print(X, [a] + Y) return (X, [a] + Y) sort([4, 2, 3, 5, 1, 3, 2, 1, 7])
ピボットは4 0番目の要素を2を取り出す [3, 5, 1, 3, 2, 1, 7] 0番目の要素を3を取り出す [5, 1, 3, 2, 1, 7] 0番目の要素を5を取り出す [1, 3, 2, 1, 7] 0番目の要素を1を取り出す [3, 2, 1, 7] 0番目の要素を3を取り出す [2, 1, 7] 0番目の要素を2を取り出す [1, 7] 0番目の要素を1を取り出す [7] 0番目の要素を7を取り出す [] 4より7が小さいか [] [7] 4より1が小さいか [1] [7] 4より2が小さいか [2, 1] [7] 4より3が小さいか [3, 2, 1] [7] 4より1が小さいか [1, 3, 2, 1] [7] 4より5が小さいか [1, 3, 2, 1] [5, 7] 4より3が小さいか [3, 1, 3, 2, 1] [5, 7] 4より2が小さいか [2, 3, 1, 3, 2, 1] [5, 7] [2, 3, 1, 3, 2, 1] [5, 7] をそれぞれ同じようにソート ピボットは2 0番目の要素を3を取り出す [1, 3, 2, 1] 0番目の要素を1を取り出す [3, 2, 1] 0番目の要素を3を取り出す [2, 1] 0番目の要素を2を取り出す [1] 0番目の要素を1を取り出す [] 2より1が小さいか [1] [] 2より2が小さいか [1] [2] 2より3が小さいか [1] [3, 2] 2より1が小さいか [1, 1] [3, 2] 2より3が小さいか [1, 1] [3, 3, 2] [1, 1] [3, 3, 2] をそれぞれ同じようにソート ピボットは1 0番目の要素を1を取り出す [] 1より1が小さいか [] [1] [] [1] をそれぞれ同じようにソート ピボットは3 0番目の要素を3を取り出す [2] 0番目の要素を2を取り出す [] 3より2が小さいか [2] [] 3より3が小さいか [2] [3] [2] [3] をそれぞれ同じようにソート ピボットは5 0番目の要素を7を取り出す [] 5より7が小さいか [] [7] [] [7] をそれぞれ同じようにソート [1, 1, 2, 2, 3, 3, 4, 5, 7]
真竜デッキでまだまだ強くなりたい その2 / やぶ蛇の選択肢について
前回の【命削り真竜】デッキから少しデッキのカードを変更したというのと、色々な環境デッキと対戦して学びがあったのでメモしておく。
また今回は「やぶ蛇」から何を出すのかという観点についても書いておこうと思う。
動画
今回も例にもれず作っているので、見てもらえればうれしいです。www.youtube.com
デッキレシピ
前回からの変更点として
メインデッキ変更理由
「真竜機兵ダースメタトロン」を抜いた理由として、出せれば強いが、タイミングが限られている点がある。不利時は大体バックが空になっていることが多いため返すカードとしては弱く、どちらかというと優勢で上から殴っていけるカードとして採用するのがメインかなと。
リリースコスト3体は結構厳しく、だったら「大捕り物」は3枚必須なわけだけど枠的に3枚は厳しいので、安定を取ってデッキから抜くことにした。
「クリスタルウィング・シンクロ・ドラゴン」ついてはそもそも「真竜機兵ダースメタトロン」ありきの採用である点＋「やぶ蛇」から採用するカードとしては優先度が低い。
個人的には「異星の最終戦士」=「ナチュル・エクストリオ」 > 「RR -アルティメット・ファルコン」 > 「クリスタルウィング・シンクロ・ドラゴン」なので、出すタイミングがほとんどないのでは？というところから別のカードを採用したほうが丸いかなと。
代わりに相手の盤面の突破する観点で代わりに「星杯戦士ニンギルス」を投入。
サイドデッキ変更理由
「インスペクト・ボーダー」は先行カードとしてはかなり強いと思うんだけど、後攻に弱いというのと展開されきったあとに挽回する手立てが薄すぎなので、抜いた。代わりに「原始生命態ニビル」を投入。
今までプレイした感じだと、【転生炎獣】や【未界域オルフェゴール】などの展開がメインのデッキに弱く、展開される姿を傍観するしかないみたいな感じが多くて、全然勝てなかったのでそのあたりへの解答として、ニビルを投入。
「スキルドレイン」も同様。
先行で張って展開系デッキの動きを封じるために入れた。
【サンダードラゴン】も止められるので。サンダードラゴン融合の効果は永続なので、「超雷龍－サンダー・ドラゴン」が開幕飛んでくる前に発動しておくのが大事。
スキドレは弱点としてこっちの誘発も止めてしまい展開が止まるという問題もあるので、永続的に使うというよりは「虚無空間」のような使い切りカードとして見切ってしまったほうが安定する。
3枚目の「やぶ蛇」を抜いたのはそもそも2枚メインに入っているので、3枚目が欲しいという状況がなく、2戦目以降相手もバック警戒するだろうし、手札でだぶつくのもなということもあり抜いた。
やぶ蛇の選択肢
メインから2枚やぶ蛇を入れており、2019年10環境が低速環境になったということで、サイドに「砂塵の大嵐」など積んでいて割と発動機会も多い。このカードをメインに入れてから、開幕相手の「ハーピィの羽根帚」で盤面一掃されてどうしようもなくなるみたいなことはなくなった。
ただ相手依存ということもあって、闇雲に強いカード出せばいいんじゃない？みたいなのも解答としてはNGで、その場に即したカードを出さないとならないのが難しいところ。
俺は「やぶ蛇」から出すカードの選択肢として3枚デッキにいれている。
異星の最終戦士
異星の最終戦士/The Last Warrior from Another Planet
融合・効果モンスター
星７/地属性/戦士族/攻2350/守2300
「ダーク・ヒーロー ゾンバイア」＋「魔力吸収球体」
このカードが特殊召喚に成功した時、
このカード以外の自分フィールド上に存在するモンスターを全て破壊する。
このカードがフィールド上に表側表示で存在する限り、
お互いにモンスターを召喚・反転召喚・特殊召喚する事はできない。
展開系デッキへの解答として。
こちらはそもそもそんなに特殊召喚をしないデッキなので、盤面を埋めないので相手の動きを制限させるのが強い。
【転生炎獣】や【未界域オルフェゴール】、【サンダードラゴン】、【オルターガイスト】、【魔術師】の場合、優先して出していく。
よっぽどのことない限りはこいつを出しておけば見たいな感じではある。
ただ、打点2350で誘発で自分フィールドの破壊効果が発動するため、チェーンされて効果無効・破壊などされるし、このカード自体に耐性はなく奪われる可能性も高いので、このカードを出しておけば安全というわけではない。
ナチュル・エクストリオ
ナチュル・エクストリオ/Naturia Exterio
融合・効果モンスター
星１０/地属性/獣族/攻2800/守2400
「ナチュル・ビースト」＋「ナチュル・パルキオン」
このカードの融合召喚は上記のカードでしか行えない。
(1)：魔法・罠カードが発動した時、
自分の墓地のカード１枚を除外し、デッキの一番上のカードを墓地へ送って発動できる。
このカードがフィールドに表側表示で存在する場合、その発動を無効にし破壊する。
魔法罠多用するデッキへの解答として。
【閃刀姫】、【真竜】ミラーなどのデッキに対して序盤で発動すると強く出ることができるのでよい。
【真竜】ミラーでは打点2800を超えるためには「ドラゴニックD」が必要なので、こいつは最優先。
ただしモンスター効果は無効にできずこのカードも自身に耐性があるわけではないため、モンスター効果で無効にされるとただの壁になる。
すでに発動済の魔法罠は防げないので、「閃刀機関－マルチロール」発動されてたら素直にアルティメット・ファルコンで打点解決していったほうが良い。
ＲＲ－アルティメット・ファルコン
ＲＲ－アルティメット・ファルコン/Raidraptor - Ultimate Falcon
エクシーズ・効果モンスター
ランク１０/闇属性/鳥獣族/攻3500/守2000
鳥獣族レベル１０モンスター×３
(1)：このカードは他のカードの効果を受けない。
(2)：このカードのＸ素材を１つ取り除いて発動できる。
このターン、相手フィールドのモンスターの攻撃力は１０００ダウンし、
相手はカードの効果を発動できない。
(3)：このカードが「ＲＲ」モンスターをＸ素材としている場合、以下の効果を得る。
●お互いのエンドフェイズ毎に発動できる。
相手フィールドの全てのモンスターの攻撃力は１０００ダウンする。
相手フィールドに表側表示モンスターが存在しない場合、相手に１０００ダメージを与える。
中盤～終盤での打点として。ライフ持っていく要員。
真竜モンスターは高レベルモンスターで構成されているけど、現状採用されている「真竜拳士ダイナマイトK」が2500、「真竜戦士イグニスＨ」が2400、「真竜導士マジェスティＭ」が2300と高くなく、突破できないなという状況に遭遇することが多い。
それに対してのひとつの解答として上から殴っていけるカードが欲しいので採用。
ただこいつは「効果受けない高打点」だけなので、代わりに相手依存だけどカードのコントロールを奪える「BF－フルアーマード・ウィング」や、破壊効果付きでさらに打点が高い「青眼の究極亜竜」も検討してもよいかなと思う。
店舗対戦でのメモ
ADSではなく、普通に対人でも対戦してきたのでその時の迷った盤面の内容をメモしておく。VS【閃刀姫】
上でも話した通り、「閃刀機関－マルチロール」発動後に「ナチュル・エクストリオ」出したときの写真。
このあと、マルチロールの①効果で閃刀魔法を止められなくなってそのままキル。
この盤面では上から殴れるアルティメット・ファルコンだった。
VS【サンダードラゴン】
経験不足からこの盤面で「常夏のカミナリサマー」破壊せず、そのままサンダードラゴン融合×２にカオスソルジャーが並ばれてキル。
リンクを意図的に出してきた場合は全力で止めたほうが良い。
サイドの交換は、
先：in：スキドレ、大捕り物。out：神の宣告、夢幻泡影
後：in：超融合、精神操作。out：神の宣告
VS【転生炎獣】
閉店間際だったので、写真なし。
サイドの交換は、先：
先：in：魔鍾洞、スキドレ、大捕り物。out：神の宣告、あとなにか
後：in：ニビル、超融合、精神操作。out：神の宣告、あとなにか
さいごに
10月12日に発売された「IGNITION ASSAULT」で「ライトニング・ストーム」が新規カードとして収録。通常魔法
このカード名のカードは１ターンに１枚しか発動できない。
(1)：自分フィールドに表側表示のカードが存在しない場合、
以下の効果から１つを選択して発動できる。
●相手フィールドの攻撃表示モンスターを全て破壊する。
●相手フィールドの魔法・罠カードを全て破壊する。
真竜デッキ的にはかなりつらい戦いを強いられると思われる。
まだ頑張っていくつもり。
真竜デッキでまだまだ強くなりたい
2019年10月新制限で「ドラゴニックD」が禁止カードから制限カードになったので、デッキに1枚入れられるようになった。
ドラゴニックＤ(ダイアグラム)/Dragonic Diagram
フィールド魔法（制限カード）
(1)：フィールドの「真竜」モンスターの攻撃力・守備力は３００アップする。
(2)：このカードがフィールドゾーンに存在する限り、アドバンス召喚した「真竜」モンスターはそれぞれ１ターンに１度だけ戦闘では破壊されない。
(3)：１ターンに１度、自分メインフェイズに発動できる。
このカード以外の自分の手札・フィールドのカード１枚を選んで破壊し、デッキから「真竜」カード１枚を手札に加える。
元々真竜デッキを使っていたため、この改定はかなり嬉しかった。
「ドラゴニックD」自体かなり強いカードで、かつて猛威を振るっていたときは「ドラゴニックD」＋「真竜剣皇マスターＰ」＋「クリスタルウィング・シンクロ・ドラゴン」が並ぶ【WW真竜】が強かったなあというのを思い出しすなあと。
更に「ドラゴニックD」復帰したからか、真竜が再び環境に立つようになって、俺も真竜デッキでまだまだ強くなりたいと思って、マッチ戦するようになったので、思ったことをメモしておく。
動画
動画作っているので、基本はそれを見てもらえればって感じです。www.youtube.com
デッキレシピ
今の真竜のスタンダードは【命削り真竜】になる。
真竜自体はアドバンス召喚しないと効果が発動できないため、特殊召喚をほとんど行わない。
そのため、「命削りの宝札」や「強欲で謙虚な壺」の特殊召喚できないデメリットを無視できるのが強みかなと。
特殊召喚を多用しないので、相手の「増殖するG」を腐らすことができるのも強い点のひとつ。
「真帝王領域」を入れるか否か
現環境は【命削り真竜】の中でも「真帝王領域」を張るタイプと、張らないタイプに分かれているのかなと。
真帝王領域/Domain of the True Monarchs
フィールド魔法
(1)：自分のエクストラデッキにカードが存在せず、自分フィールドにのみアドバンス召喚したモンスターが存在する場合、相手はエクストラデッキからモンスターを特殊召喚できない。
(2)：自分のアドバンス召喚したモンスターの攻撃力は、相手モンスターに攻撃するダメージ計算時のみ８００アップする。
(3)：１ターンに１度、自分メインフェイズにこの効果を発動できる。
自分の手札の攻撃力２８００／守備力１０００のモンスター１体を選び、そのモンスターのレベルをターン終了時まで２つ下げる。
元々真竜と帝を組み合わせた【真竜帝】デッキもあったので、シナジーはあったんだけど、「ドラゴニックD」復帰して、フィールド魔法を「メタバース」や「テラ・フォーミング」でサーチするようになったため着目されているカードになる。
「真帝王領域」の良さは、先行で体制整った状態で張ってしまえばそのまま勝ちに持っていけるところかなと。
エクストラからモンスターを出さないデッキなんてほとんどない。
維持にはアドバンス召喚されたモンスターを場に維持する必要があるけど、真竜の打点を越えてくるモンスターは早々現れないし、場に出てきたとしても「真竜の黙示録」で攻守を半減してしまえば何とかなる。
弱点はそのまま上の書いている内容の反対なんだけど、「真帝王領域」を破壊されると厳しくなるというのと、アドバンス召喚していないと効果発動できない点。
現環境はサイドデッキに「砂塵の大嵐」など魔法罠を破壊するカードが多いため、信頼度は言うほど高くないのが現実。
あとは後攻だと既に展開しきっていると思うので、純粋に効きにくいという点がある。
今回のデッキは「真帝王領域」を使わない型。
代わりに「王家の眠る谷－ネクロバレー」を入れている。
理由は弱点がちょっときついかなっていうのと、エクストラデッキをほとんど使わないためメタカードを潤沢に入れられる点、あとは後述する「やぶ蛇」のためにエクストラデッキを使いたいから。
相手の行動を抑制するようなフタができないので、「無限泡影」などで妨害しつつ展開していく形にしている。
「真竜騎兵ダースメタトロン」の採用
「真竜騎兵ダースメタトロン」を入れている理由としては、高打点モンスターや、守備力が高いモンスターに打点不足で勝てないことが多かったので（ドラゴニックD復帰前は特に）、それの解消のために投入。かなり出しにくいカードではあるんだけど、場に出せればかなり強い。
サーチもできるので一気に打点持っていきたいときや、「大捕り物」で奪ったときなどに使っていく形。
「やぶ蛇」のメイン投入
「やぶ蛇」をメイン投入しているのは、経験上序盤に「ハーピィの羽根帚」を打たれると、場が崩壊して復帰できない問題があったため。
魔法罠をがっつり積むので、相手は展開前に全部破壊してくるため、意外に「やぶ蛇」踏んでくれるなという印象。
出す択としてはこの3択
- 打点で押し切る場合、「RR－アルティメット・ファルコン」
- 相手が魔法罠を多用する場合、「ナチュル・エクストリオ」
- 相手がモンスター効果で展開する場合、「異星の最終戦士」「クリスタルウィング・シンクロ・ドラゴン」
多すぎでは？とぱっと見、見えるけど「ナチュル・エクストリオ」「異星の最終戦士」「クリスタルウィング・シンクロ・ドラゴン」は「真竜騎兵ダースメタトロン」でも出していけるので、多すぎでもないのかなと思う。
回してみての感想
真竜デッキの特性上、序盤に陣地固められないときつい。
一度ヴァレルロード・ドラゴンとか出されると、打点勝負できないので「真竜の黙示録」を引くのをお祈りするしかないのがつらい。
あとは「やぶ蛇」からの何を出していくかという回答が決めきれず失敗するケースが多かったので、【ドラゴンリンク】【転生炎獣】ならモンスター展開パターン、【閃刀姫】なら魔法罠展開パターンでしっかり方針立てが必要だなって思った。
サイドデッキももう少し練ったほうがよさそうな気がした。
「インスペクト・ボーダー」どこで使ったらいいんだ？みたいな感じになってたことが多かった。
あとプレミな。ホントしょーもないプレミで負けているので何とかしろ俺。
トップ20からわかるアイカツ！アイドル総選挙最終結果
『アイカツオンパレード！』開始を記念したアイドル総選挙の最終結果が発表されましたね。
データカードダス アイドル総選挙最終結果発表✨見事、1位に輝いたアイドルは…
— アイカツ！データカードダス公式 (@aikatsu_dcd) September 30, 2019
👑1位 七倉小春ちゃん
です！小春ちゃんの新しいプレミアムレアドレスがアイカツ！カードになるよ💖たくさんの投票ありがとう✨
1〜20位まではHPでチェック！https://t.co/OTwggrRLbI#aikatsu #小春ちゃんおめでとう pic.twitter.com/DdW57DvTfa
1位は七倉小春！
中間では藤堂ユリカ様に次ぐ2位だったが、結果は2,000票差をつけての1位。
1位になったので新しいプレミアムドレスのカードが登場することに。
七倉小春ファンの人おめでとうございます！
物語的にも割と裏方の役が多かった小春ちゃんがプレミアムドレスを着れるというのはファン冥利に尽きると思います。
結果を見ると1位から3位と4位の差が約14,000票差で、かなり開いていたのが驚き。
4位が星宮いちごなので、根強いファン層がいるような気がしていたけど新規ドレスが確定しているから票が入りにくかったというのもあるのかなーと。
最終結果のトップ20の情報から分かること
上のサイトの最終結果に情報を付け加えたリストがこれです。
順位の変動はあるものの、中間結果でランクインされている20人がそのままランクインされた形となった感じ。
10位以下は得票数の公開はされていないが、20位以下はひっくり返すには票差があまりについている状況だったのでは？と推測。
ランクインされているキャラクターの傾向については以前書いたので、そちらを参照ください。
この投票に関する数字
2019/8/19から2019/9/17の29日間の投票期間で、投票総数が309,459だったので、単純に一日平均10,671票が投じられていたと思われる。
投票数が判明しているトップ10の得票総数が185,552票なので、全体の約60パーセントがトップ10のキャラクターで占めらえていることになる。
投票可能キャラクターが56人だったので、46人が残りの40パーセントの中にいることになるんだけど、じゃあその46人がそれぞれどのくらいのパーセンテージだったのかって話。
これはあくまで俺の想像でしかないけど、おそらく20位までは大体1～2パーセント未満くらいで、約3,000～6,000票の範囲であろうと推測される。
20位以下は1パーセント未満～1パーセントくらい、おそらく約3,000票を切っているのではと。
おそらく50位以下は1,000票も獲得していないのではないかと思う。
ただ、これだけは言わなきゃいけないなっていうのは、得票数が少ない＝そのアイドル自体がダメとかいいとかそういう優劣の話ではないよってこと。
自分にとって推しだと思ったアイドルがトップ20に来なくても、俺が推していて俺はできる限り投票した、それでいいじゃないって話。
あんなむちゃくちゃ可愛い双葉アリアがトップ20に来ないのはおかしいじゃん。
各シリーズ単位のランクイン数
各シリーズ単位でのランクイン数も見てみる。
『アイカツ!』が最も多い10人。
『アイカツ!』キャラは根強い人気があるのがここで見て取れる。
逆に『アイカツフレンズ!』キャラは3人と、投票期間時の現行シリーズの割には少ない印象を受ける。
やっぱり個よりはフレンズ（複数）がメインだったから票が入りにくかったのかもしれないなー。
属性別のランクイン数
次に属性単位でのランクイン数を見てみる。
トップはクールで、7人。全体の約35パーセント。
ランクインを見る限り7位から11位までを独占しているような形になっている。
この辺りのクールキャラは氷上スミレ然り、騎咲レイ然り女性人気がかなり高そうなので、上位に入ってきたのかなと。
俺の推しの霧矢あおいも中間から順位を下げたものの、7位でゴール。
ランキング系をウォッチしていると、だいたいトップ10だけど7位とかそういう何とも微妙なところにいるなっていうのは正直ある。
頑張って上にあげてあげたい。
ポップキャラが3人というのがちょっと少なかったかなってという印象。
有栖川おとめがランクインしていないのもかなり意外だったかな。
藤堂ユリカ様vs七倉小春
これは完全に推測の話。
藤堂ユリカ様vs七倉小春の戦いの流れを想像してみる。
2019/9/4の中間発表時点では藤堂ユリカ様が1位。
それから2019/9/13時点でもう一度中間発表があった時点では七倉小春が1位になっているので、11日間の間で追い抜かしていることになる。
また中間発表から投票終了日までの14日間で票差を2,000票つけている。
そこから考えるに七倉小春票は、1日「ユリカ様の投票数と同数＋140票」程度投票されていたと考えられる。
140票差、つまり140プレイで14,000円なので、1日最低でも七倉小春のために14,000円が動いているのでは？？？（あくまで推測）
これを考えると、諭吉を注げば逆転はいつでも可能ということになりますね。
『Pythonで体験してわかるアルゴリズムとデータ構造』メモその8/動的計画法で最短距離を求める
『Pythonで体験してわかるアルゴリズムとデータ構造』を読みながらアルゴリズムについて勉強する。
- 作者: 西澤弘毅,森田光
- 出版社/メーカー: 近代科学社
- 発売日: 2018/06/30
- メディア: 単行本
- この商品を含むブログを見る
第7章 問題に適した設計法とは
前回のハノイの塔問題に引き続き、今回は最短経路の数え上げ問題を考える。
最短経路の数え上げ問題について
高校数学で出てくる問題ひとつ。
格子状の道があったとして、スタートからゴールまでの最短経路は何パターンあるかという問題。
格子状の道の中には通過することができない箇所も存在する。
この問題のイメージ、数学的な解き方については以下動画が詳しい。
動画上では階乗を使用した商を出して最短距離も求めていたが、動的計画法を用いて解いていくのがこの章の考え方なので、 以下サイトの書き込み方式の考え方で解いていく。
ルールとしては、
- 左上にスタート、右下がゴールとして設定
- どのように追加してもよいが、上下作用で移動すること。斜め移動はNG
- 最短距離を目指すので、迂回はしない
- 通過することができないマスが存在する
このような5×6の格子状の道があったとした場合、最短距離で行くのであれば右上から左下にいくという前提があるので、赤字（Ⅰの行と1の列）は1回しか通ることができない。
では、青文字のⅡ-2ところは何回通るかというと、緑の赤字Ⅰ-2とオレンジの赤字Ⅱ-1から通ることになる。
つまりⅡ-2は2通り通る方法があるということになる。
更にここから分かるのは、求めたいマスの上のマスと左のマスの値を合算することで、そのマスを通過するのは何通りか特定することができる。
ルールにある「通過できないマス」についても基本的な考えは変わらない。
通れないマスは、そこに行くパターンはない（通過できないので）ので、行くパターンは0通り。
事前に0埋めしておくことでⅢ-3を計算したいときに 3 + 0 =3 となる。
実装
def counting(a, b, X): # 格子状の道のイメージを表現する。リスト型の制限で不要な0番目が生成される。 A = [[-1 for j in range(b + 1)] for i in range(a+1)] print(A) print() #格子状の道の0番目列は不要なので、0埋めする。 for i in range(a+1): A[i][0] = 0 print(A) print() #格子状の道の0番目行は不要なので、0埋めする。 for j in range(b+1): A[0][j] = 0 print(A) print() # 通過できないところを事前に0で埋めておく for (i,j) in X: A[i][j] = 0 print(A) print() #スタートは必ず通り、1通りなので1をセットしておく A[1][1] = 1 for i in range(1, a+1): for j in range(1, b+1): if A[i][j] == -1: A[i][j] = A[i-1][j] + A[i][j-1] print("{}-{}番目を通過するのは{}+{}で{}通り".format(i, j, A[i-1][j], A[i][j-1], A[i][j])) return A[a][b] counting(5,6,[(2,3),(4,5)])
[[-1, -1, -1, -1, -1, -1, -1], [-1, -1, -1, -1, -1, -1, -1], [-1, -1, -1, -1, -1, -1, -1], [-1, -1, -1, -1, -1, -1, -1], [-1, -1, -1, -1, -1, -1, -1], [-1, -1, -1, -1, -1, -1, -1]] [[0, -1, -1, -1, -1, -1, -1], [0, -1, -1, -1, -1, -1, -1], [0, -1, -1, -1, -1, -1, -1], [0, -1, -1, -1, -1, -1, -1], [0, -1, -1, -1, -1, -1, -1], [0, -1, -1, -1, -1, -1, -1]] [[0, 0, 0, 0, 0, 0, 0], [0, -1, -1, -1, -1, -1, -1], [0, -1, -1, -1, -1, -1, -1], [0, -1, -1, -1, -1, -1, -1], [0, -1, -1, -1, -1, -1, -1], [0, -1, -1, -1, -1, -1, -1]] [[0, 0, 0, 0, 0, 0, 0], [0, -1, -1, -1, -1, -1, -1], [0, -1, -1, 0, -1, -1, -1], [0, -1, -1, -1, -1, -1, -1], [0, -1, -1, -1, -1, 0, -1], [0, -1, -1, -1, -1, -1, -1]] 1-2番目を通過するのは0+1で1通り 1-3番目を通過するのは0+1で1通り 1-4番目を通過するのは0+1で1通り 1-5番目を通過するのは0+1で1通り 1-6番目を通過するのは0+1で1通り 2-1番目を通過するのは1+0で1通り 2-2番目を通過するのは1+1で2通り 2-4番目を通過するのは1+0で1通り 2-5番目を通過するのは1+1で2通り 2-6番目を通過するのは1+2で3通り 3-1番目を通過するのは1+0で1通り 3-2番目を通過するのは2+1で3通り 3-3番目を通過するのは0+3で3通り 3-4番目を通過するのは1+3で4通り 3-5番目を通過するのは2+4で6通り 3-6番目を通過するのは3+6で9通り 4-1番目を通過するのは1+0で1通り 4-2番目を通過するのは3+1で4通り 4-3番目を通過するのは3+4で7通り 4-4番目を通過するのは4+7で11通り 4-6番目を通過するのは9+0で9通り 5-1番目を通過するのは1+0で1通り 5-2番目を通過するのは4+1で5通り 5-3番目を通過するのは7+5で12通り 5-4番目を通過するのは11+12で23通り 5-5番目を通過するのは0+23で23通り 5-6番目を通過するのは9+23で32通り
『Pythonで体験してわかるアルゴリズムとデータ構造』メモその7/ハノイの崇高なる力を経験する
『Pythonで体験してわかるアルゴリズムとデータ構造』を読みながらアルゴリズムについて勉強する。
- 作者: 西澤弘毅,森田光
- 出版社/メーカー: 近代科学社
- 発売日: 2018/06/30
- メディア: 単行本
- この商品を含むブログを見る
第7章 問題に適した設計法とは
この章のゴールは 与えられた問題に、分割統治法と、動的計画法のどちらが向いているかを判断できるようになる
書籍中ではハノイの塔問題、最短経路の数え上げ問題を例にとって説明している。
ハノイの塔について
以下のルールに従ってすべての円盤を右端の杭に移動させられれば完成。
3本の杭と、中央に穴の開いた大きさの異なる複数の円盤から構成される。
最初はすべての円盤が左端の杭に小さいものが上になるように順に積み重ねられている。
円盤を一回に一枚ずつどれかの杭に移動させることができるが、小さな円盤の上に大きな円盤を乗せることはできない。n枚の円盤すべてを移動させるには最低 2n − 1 回の手数がかかる。 解法に再帰的アルゴリズムが有効な問題として有名であり、プログラミングにおける再帰的呼出しの例題としてもよく用いられる。ただし支配数がメルセンヌ数なので、同じく再帰の例題として多用されるフィボナッチ数同様、再帰をストレートに実装するととんでもない事態を生む例でもある。 ハノイの塔 - Wikipedia
パズルのひとつで、動画で見ると分かりやすい。
www.youtube.com
こんな感じで、必ず大-中-小（大-小）の順番で並ばなければならないゲーム。
遊戯王プレイヤーはおそらくこのワードを聞くと
(C)高橋和希 スタジオ・ダイス／集英社・テレビ東京・ＮＡＳ
これを思い出すのかなと。
俺はもうこのイメージしかない。
今回はミラフォの話でも、王宮のお触れの話でもなく、アルゴリズムの話。
何故最低2n -1なのか
以下動画を見るとイメージがつかみやすい。
円盤が3個あるとして、大きく「1と2の固まり」と「3個目」で分割する。
「1と2の固まり」は3回移動することで1個目の下に2個目が来ることが分かっているので、それに加えて3個目として1回移動させてあげればよい。
ただそれだと、1個目の下に2個目、2個目の下に3個目が来ないので、「1と2の固まり」をもう一度移動してあげる必要がある。
3回＋1回＋3回＝7回。7回移動すると1個目の下に2個目、2個目の下に3個目が来ることになる。
漸化式で考えると、
「1と2の固まり」をn、「3個目」をn+1とした場合 [tex:a_{n+1} = 2a_{n+1}] （3個移動したいのであれば、2×3+1） [tex: a_{1} = 1]とした場合に、漸化式を解くと、 [tex: a_{n+1} + 1 = 2( a_{n+1} )] となる。
数列 [tex: a_{n+1} = 1] は、初稿がa1=2、公比が2の等比数列なので、2n - 1になる。
なんだか難しいことを書いていて正直俺もそんなによくわかってないが、重要なのは上の大きく「1と2の固まり」と「3個目」で分けてしまうということ。
実装
ハノイの塔は、再帰の典型的なパターンとのことで、再帰といえば分割統治法。
ということで分割統治法の考え方のトップダウンから考えた場合の処理を書いてみる。
def move(k,start,yobi,end): print("") print("今{}の処理だよ".format(k)) if k >= 2: print("{}のa処理に入るよ".format(k-1)) move(k-1, start, end, yobi) print("") print("今{}の処理だよ".format(k)) print("{}を{}から{}軸へ移動".format(k,start, end)) if k >= 2: print("b処理に入るよ") move(k-1, yobi,start, end) move(3,1,2,3)
今3の処理だよ 2のa処理に入るよ 今2の処理だよ 1のa処理に入るよ 今1の処理だよ 今1の処理だよ 1を1から3軸へ移動 今2の処理だよ 2を1から2軸へ移動 b処理に入るよ 今1の処理だよ 今1の処理だよ 1を3から2軸へ移動 今3の処理だよ 3を1から3軸へ移動 b処理に入るよ 今2の処理だよ 1のa処理に入るよ 今1の処理だよ 今1の処理だよ 1を2から1軸へ移動 今2の処理だよ 2を2から3軸へ移動 b処理に入るよ 今1の処理だよ 今1の処理だよ 1を1から3軸へ移動
『Pythonで体験してわかるアルゴリズムとデータ構造』メモその6/分割統治法と動的計画法を知る
『Pythonで体験してわかるアルゴリズムとデータ構造』を読みながらアルゴリズムについて勉強する。
- 作者: 西澤弘毅,森田光
- 出版社/メーカー: 近代科学社
- 発売日: 2018/06/30
- メディア: 単行本
- この商品を含むブログを見る
第6章 アルゴリズムを設計する方法
この章のゴールは 複雑な問題を解く際にアルゴリズムをどのような方針で設計したらよいか、説明できるようになる
書籍中ではフィボナッチ数列を例にとって説明している。
フィボナッチ数列について
「フィボナッチ数列」とは，「前の２つの数を加えると次の数になる」という数列です。 ただし，１番目と２番目の数は両方とも１です。
フィボナッチ数列と中学入試問題 - すぐる学習会
どういうことかというと、
0, 1, 1, 2, 3, 5, 8, 12, 21, 34 …
上のような何かのルールにのっとっている数字の列をフィボナッチ数列という。 *1
そのルールが上の「前の２つの数を加えると次の数になる」。
基本的に0番目は0、1番目は１出ることがこの数列のルールになる。
3番目の結果は、0番目＋1番目＝1。
4番目の結果は、2番目＋3番目＝2。
というようにルールに合わせると結果が求められる。
フィボナッチ数列は、自然界にあふれていて枝の数や、ひまわりの種の数、カタツムリの殻の形などはフィボナッチ数列でできている。
上の話を漸化式で考えると
じゃあこれをどのように実装するのかというところで、アルゴリズムを考えていく上での解き方を考える。
分割統治法
そのままでは解決できない大きな問題を小さな問題に分割し、その全てを解決することで、最終的に最初の問題全体を解決する、という問題解決の手法である。
分割統治法 - Wikipedia
与えられた課題大きな回答を出すときに、力づくで解くのではなく、ある程度小さく区切って処理をしてしまおうという考え方。
小さく区切る＝再帰呼び出しを行って、自身を何度も呼び出すことで小さい処理を行っていく。
ただし、再起呼び出しするので、同じ処理を何度も繰り返すために、無駄な処理を繰り返しメモリ領域をひっ迫する可能性がある。
実装
6という大きな数字を分割し続けて、回答を出していく
def fib(n): print("{}の処理".format(n)) if n < 2: return n else: print("{}のa処理へ".format(n-1)) print() a = fib(n-1) print() print("{}のb処理へ".format(n-2)) b = fib(n-2) c=a+b print("{}={}+{}".format(c,a,b)) return c ans = fib(6) print() print("結果", ans)
6の処理 5のa処理へ 5の処理 4のa処理へ 4の処理 3のa処理へ 3の処理 2のa処理へ 2の処理 1のa処理へ 1の処理 0のb処理へ 0の処理 1=1+0 1のb処理へ 1の処理 2=1+1 2のb処理へ 2の処理 1のa処理へ 1の処理 0のb処理へ 0の処理 1=1+0 3=2+1 3のb処理へ 3の処理 2のa処理へ 2の処理 1のa処理へ 1の処理 0のb処理へ 0の処理 1=1+0 1のb処理へ 1の処理 2=1+1 5=3+2 4のb処理へ 4の処理 3のa処理へ 3の処理 2のa処理へ 2の処理 1のa処理へ 1の処理 0のb処理へ 0の処理 1=1+0 1のb処理へ 1の処理 2=1+1 2のb処理へ 2の処理 1のa処理へ 1の処理 0のb処理へ 0の処理 1=1+0 3=2+1 8=5+3 結果 8
やっぱり再帰的定義で実装するといまいちよくわからなくなるよなあ。
動的計画法
分割統治法の計算は無駄なので、計算結果を保存しておいて再利用していけば無駄なメモリを使わなくてよいのでは？というのが動的計画法。
フィボナッチ数列で考えるのであれば、配列の0番目から順番に計算することで、配列にすでに突っ込んだデータを流用できるよねという考え方。
人間が純粋にイメージするような計算手法。
欠点は小問題が多い場合、使用頻度の低いデータがメモリに残りっぱなしになること。
フィボナッチ数列だと、要素6番目まではいいけど1000番目のときに、0番目の要素って全然使ってないから無駄にメモリ食ってない？ってこと。
実装
def fib(n): A = [None] * (n+1) print(A) A[0] = 0 A[1] = 1 print(A) for i in range(2, n+1): A[i] = A[i-1] + A[i-2] print(A) return A[n] ans = fib(6) print() print("結果", ans)
[None, None, None, None, None, None, None] [0, 1, None, None, None, None, None] [0, 1, 1, None, None, None, None] [0, 1, 1, 2, None, None, None] [0, 1, 1, 2, 3, None, None] [0, 1, 1, 2, 3, 5, None] [0, 1, 1, 2, 3, 5, 8]
その他参考
*1:数列なので、先頭の0は1番目ではなく0番目
