サブロウ丸

大学生です

数学

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

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

Python newton法(非線形計画)

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

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

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

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

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

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

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

劣モジュラ1

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