2019自作CNCマシン・レーザーカッターについてMac+Arduino:自作CNCマシンの記録。CNCシールドV3.5+bCNCを使用中。BluetoothモジュールおよびbCNCのPendant機能でスマホからもワイヤレス操作可能。その他、電子工作・プログラミング、機械学習などもやっています。MacとUbuntuを使用。レーザーシールド制作・改良*CNCマシンの制作記録は2016/04/10〜の投稿に書いてあります。今回は動的計画法(DP)と再帰的アルゴリズムについてです。これもまたTSP(巡回セールスマン問題)から派生したアルゴリズムなので勉強用に記録しておきます。要は演算を効率化して、ある程度の規模の組み合わせ問題においても計算可能にしていく工夫という感じです。(ILP)というアルゴリズムにも関係していくようで、TSP以外にも様々な組み合わせ問題や最適化問題に応用できるためもう少し勉強してみようかと。Matchingを見つける演算の際にも使えるのかもしれません。線形計画問題(LP)はラグランジュ緩和に発展できるようなので、以前勉強したサポートベクターマシン(SVM)にも通じるし、機械学習における最適化を数理的に理解する上でも役立ちそうです。TSPをきっかけにいろんなアルゴリズムに派生しましたが、今回はこの中でも動的計画法(DP)とメモ化再帰について試してみることにしました(まだまだ覚えることはたくさんありそう)。Notebook使用)簡単な例として階乗のアルゴリズムから。fact(n-1)関数fact(n)の内部で自身の関数を呼び出す方法。n=5なら5!=5*4*3*2*1=120。fib(n-2)これも関数fib(n)内で自身の関数fib(n-1)とfib(n-2)を呼び出す方法。この方法の場合はn=30あたりから計算に時間がかかってきて、n=35だと2.34s、n=40で26.7sもかかってしまいます。いうのは、fib(n)を求めるにはfib(n-1)を求めなければならず、fib(n-1)を求めるにはfib(n-2)を求めなければいけなくなり、毎回n=1まで遡って計算しなければいけなくなり、その都度計算が重複してしまうためのようです。nが大きい値になると現実的な時間内では計算不可能となるため、高速化するには以下の方法で。末尾再帰(高速化):フィボナッチ数をサンプルとすれば、一度計算した値(一つ前と二つ前の値)を記憶させておく末尾再帰という方法。n1)こうすることで、n=40で26.7sかかっていたのが14.1usになり、n=1000でも982usで済みます。nが大きい値であっても計算可能。ループを使うなら以下。n2試してみるとこちらのほうが速い。n=1000で57us。動的計画法:もうひとつメモ化:Memoization(Memorizationではなく)という方法で一度計算した内容を重複しないように記録しておく方法。動的計画法(ボトムアップ)。memo[n]この場合、n=1000で162usなので処理は高速な方。事前にn個数だけリストに変数を格納する分メモリを消費。似たような方法で、リストの代わりにディクショナリを使った方法は以下。トップダウンで再帰的な動的計画法。valディクショナリの場合はその都度必要に応じてキーと値を格納できるので、事前にn個分の値を格納するリストを用意しなくてもよい。n=1000で594us程度。memo[-1]リストを使って普通にappendしていくだけなのでわかりやすい。n=1000で190usなので結構高速。これもリストにn個分の値を格納するので、それだけメモリを使う。ライブラリ/デコレータの使用:またライブラリを使うことでメモ化することも可能。1001)]functoolsライブラリをインポートし、最初に書いた演算が遅くなってしまう再帰関数にデコレータである@lru_cacheを追加すればメモ化が可能。この場合n>988だとエラー(スタックオーバーフロー)になってしまうため、forループで987から1000まで計算させれば大丈夫。Notebookの時間計測用マジックコマンド。自前でデコレータを用意する場合は以下。fib_mem(n-1)この場合、n=1000で6.44us。これはかなり高速だし汎用的なので便利かもしれない。なんとなく動的計画法や再帰関数の基本を理解してみましたが、次回はこれをTSP(巡回セールスマン問題)に適用して厳密解を求めてみたいと考えています。掲載されているGrbl1.1対応ソフトの一つでもあります。2017年現在では、このページの内容はやや古いものとなっています(Grbl0.9以前のもの)。