サブロウ丸

主にプログラミングと数学

数学

【Python】順序付きビンパッキング問題

この記事の応用です。 商品とビンに順序をつけた場合のビンパッキング問題になります。 ソースコード 実行結果 入力 うさぎ0が食べるりんごの量は1.2 うさぎ1が食べるりんごの量は2.2 うさぎ2が食べるりんごの量は1.0 うさぎ3が食べるりんごの量は0.7 うさぎ…

【Python】ビンパッキング問題

離散数学の組合せ論の代表的な問題としてビンパッキング問題というのがあります。 十分に用意された品物を、複数個のビン(容器)に詰めるときの最大利益を求める問題です。 このときビンの個数が1つであればナップサック問題と呼ばれる問題になります。 この…

ダブリング

ダブリングという計算手法に感動したので、No.572 妖精の演奏 - yukicoderこの問題の解説を書こうと思います。 問題文を読むと、なるほどいかにも動的計画法チックな問題ですね、 ということで、最初は普通に以下のような定式化を行いました。 gist.github.c…

deBoorの公式

上の記事で紹介したMATLABのcsapiはdeBoorの公式を用いて双3次スプラインを行っています。 この記事ではそのdeBoorの公式を自作してみたいと思います。 アルゴリズム さて、ここでどのようにfxやfyを計算するかというと、 この記事の方法を用います。スプラ…

【Matlab】双3次スプライン(csapi)

csapi関数を用いて双3次スプライン関数の生成と復元を行います。 双スプラインとは2変数のスプライン関数のことです。 言い換えれば平面の補間関数になります。 まずはソースコードから。 peaksというMatlabのサンプル関数からいくつかを標本点を取り出して…

有限差分法による勾配の計算

問題設定 一次近似 二次近似 三次近似 この三次近似について、幾何的にどうとらえられるかを考えてみました。 (面積で議論することもできると思います) 四次近似については’Runge-Kutta法’という方法が知られています。 それについては、こちらをどうぞ ルン…

【Matlab】 有理スプライン補間

有理スプライン補間をMatlabで実装してみました。 有理スプライン補間とは3次スプライン補間の3次の項を双曲線関数に置き換えたものです。 有理スプラインはパラーメータをうまく調節することで、 3次スプライン補間(参考: 3 次スプライン データ内挿 - MATL…

【Mac】Cbcソルバー 並列処理

Cbcとはオープンソースの混合整数線形計画(mixed integer liner program)ソルバーです。 混合整数線形計画問題とは読んで字のごとく、 線形計画問題の中に連続変数と、整数変数が混合している問題のことになります。 そのCbcソルバーで並列処理を行えるよう…

Newtonの差分商補間(後編)

これの後編です。 実際に簡単な関数でいくつか補間による近似を行なってみたいと思います。 fが近似したい関数、gがデータ点(0, 0) (1, 1) (2, 2)から構成した差分商補間になります。 fは2次式でかつ、前編の最後の定理「剰余なしのn項からなるNewtonの差分…

Newtonの差分商補間(前編)

Newtonの差分商補間の理論についてです。内容は高校レベルでしょうか。 最後の定理は強力ですね。 補間といえば、他にはLagrange補間が有名ですが、 Lagrange補間よりも計算量が少ないことが特徴です。 一番最後の証明は、「n点を補間するn-1次の多項式はLag…

線形計画問題における、とある条件を持つバイナリ変数の表現方法について

最近、線形計画問題に取り組んでいまして、以下のようなバイナリ変数xを定義する必要が出てきました。 バイナリ変数とは0と1の2値のみをとり得る変数のことです。 これがなかなか難しくて、いろいろ調べてみて、 2通りの定式化を行いました。 1つ目は以下の…

最短路問題を線形計画法で解く2

グラフの最短路問題はダイクストラ法等で解くのが普通ですが、 今回も線形計画法で解いてみたいと思います。(あえてね) ↓その1です。 inarizuuuushi.hatenablog.com が定式化となります。(とするとが続いているところは無視してください) 路の制約として、フ…

最短路問題を線形計画法で解く (Python)

グラフの最短路問題はダイクストラ法等で解くのが普通ですが、 今回は線形計画法で解いてみたいと思います。(あえてね) 定式化は こうなります。 最短路を解く問題なのに目的関数が最大化になっているところが面白いですね。 ad(j)については、jの隣接ノード…

最短路計算における、楕円を用いたグラフの枝刈り

上記のグラフのstartからgoalまでの最短路を求めたいとします。 (グラフの枝の重みは枝の長さ) 直感的には、startとgoalから離れた点や枝を考える必要はない(i.e.最短路にそれらの点や枝が含まれることがない)ように思えますが、 それをどう厳密に表現するか…

【Python】 newton法(非線形計画)

newton法とは、目的関数の最小化元(或いは最大化元)を求める問題に対する反復法と呼ばれる解法の一つです。 関数fと勾配、初期点を問題に合わせて入力する必要があります。

【Python】 最急降下法(非線形計画)

最急降下法とは、目的関数の最小化元(或いは最大化元)を求める問題に対する反復法と呼ばれる解法の一つです。 目的関数fと勾配、初期点を問題に合わせて入力する必要があります。

三角形の合同条件と、それに対応する面積公式

ある二つの三角形について、その形と大きさが等しいとき、それらは「合同である」と言います。 この合同についてみなさん、中学校で以下の三つの合同条件を習ったと思います。 ・三辺相等 ・二辺狭角相等 ・二角狭辺相等 例えば三辺相等について、 三角形の…

対称グラフの完全マッチング数について

完全マッチングについて面白い定理を見つけたので、ご紹介します。 まず、完全マッチングについて、 グラフ理論においてマッチングとは、グラフ中の枝集合で、互いに端点を共有しないもののこと。特に、これ以上枝を追加できないもののことを極大マッチング…

劣モジュラ2

今回は Chapter2 劣モジュラ最適化の基礎 2.4 列もジュラ最適化と多様体の 貪欲解の最適性についてです。 ラグランジュ緩和については以下のPDFが分かりやすくまとまっていると思います。 http://www.bunkyo.ac.jp/~nemoto/lecture/opt-model/2008/duality1-…

劣モジュラ1

「劣モジュラ最適化と機械学習」という河原先生と永野先生が書かれた本を最近勉強しています。 https://www.amazon.co.jp/劣モジュラ最適化と機械学習-機械学習プロフェッショナルシリーズ-河原-吉伸/dp/4061529099/ref=sr_1_fkmr0_1?ie=UTF8&qid=1492411085…