gggggraziegrazie

graizegrazieさんのやったこと、学んだことを記録する雑記帳です

QR分解

QR分解は、m \ x \ nの実行列Aを、m次の直交行列Qとm \ x\ nの上三角行列Rとの積に分解する操作を指します。なおこの分解は必ず成立します[1]。QR分解は線形最小二乗法を解いたり、[4]曰く行列Aの固有値を求めるために使用されます。その計算手法としては、ハウスホルダー法やグラムシュミット分解などがあります。[3]によると、QR分解はLU分解に比べて計算量は増えるものの、安定した解を求められるそうです。
また[2]によると、幾何学的に直交行列は回転を表します。確かに回転行列をR(\theta)とすると、R(\theta) \ R^T(\theta) \ = \ R(\theta) \ R(-\theta) \ = \ Iとなります。また上三角行列は拡大・縮小＆スキュー（せん断）を表します。このことから、行列Aによる線形変換の回転とスケーリング、スキューの成分を取り出す働きがあると言えます。

参考文献

[1]QR分解 - Wikipedia
[2]zellij.hatenablog.com
[3]Python NumPy SciPy サンプルコード: QR 分解, コレスキー分解 | org-技術
[4]www.msi.co.jp

LU分解

正方行列Aを、下三角行列(Lower triangular matrix)Lと上三角行列(Upper triangular matrix)Uの積に分解する操作を指します。連立方程式の厳密解を求める際に使われます。また
\begin{align} A_1 \vec{x} \ &= \ \vec{b_1} \\ A_2 \vec{x} \ &= \ \vec{b_2} \\ A_3 \vec{x} \ &= \ \vec{b_3} \\ \end{align}
の様に左辺が変化する場合は、計算を各方程式毎に行う必要があるため、計算量がO(n^3/3)となります（ガウスの消去法を使用）。一方
\begin{align} A \vec{x} \ &= \ \vec{b_1} \\ A \vec{x} \ &= \ \vec{b_2} \\ A \vec{x} \ &= \ \vec{b_3} \\ \end{align}
の様に左辺が一定の場合は、計算量をO(n^2)削減することができます。

参考文献

mathwords.net
LU分解 - [物理のかぎしっぽ]
http://ocw.nagoya-u.jp/files/58/05.pdf

Branch and Bound（分枝限定法）法

分枝限定法とは、組合せ計画問題で厳密解を求めるための手法の１つです。組合せ計画問題とは、ある関数を最大化するパラメータの組の様に、パラメータの有限個の組み合わせの中から目的を満たす組を求める問題です。分枝限定法は、条件分岐を駆使して問題を部分問題にどんどん分割してきます。これを分枝操作といいます。ある部分問題において、これ以上解を探索する必要がないと判断した（部分問題を解いた）場合、部分問題の分割を止めます。これを限定操作といいます。これにより、分枝限定法は探索時間の削減を図ります。部分問題の解は暫定解と呼ばれ、各部分問題を解いた時点での最良の解と言えます。探索する必要がないと判断する条件は下記の通りです。

  • 既に最適解が得られた
  • 現在の暫定解よりも良い解が得られる可能性がなくなった
  • 許容解が存在しないことがわかった（つまり実行不可能）＝　その条件分岐が不適当だということがわかった

なお部分問題を解く際、分枝限定法は問題の制約条件を緩和することで、問題を解きやすくします。緩和後の問題は緩和問題と呼ばれます。緩和問題は元の問題の条件を緩和しただけなので、緩和問題の解 \supset 元々の問題の解となります。そのため緩和問題の解を求めた後に修正することで、最終的に元の問題の解を得られることができます（できることが多いそうです）。緩和の例は下記の図に記載の様に、不連続な値域→連続的な値域に変えるのが一般的なようです。

f:id:graziegrazie:20181019040829p:plain
出典：[1]

分枝限定法のフローは、下図のチャートの通りです。
f:id:graziegrazie:20181019035642p:plain

なお分枝限定法を実装する場合、下記を検討する必要があります。

  • 探索
    • どのような順番で部分問題を選ぶか　→　一般的なのは最良優先探索（最も良い許容解が得られそうな部分問題を優先）、深さ優先探索（部分問題の深さがより大きい問題を優先）
  • 限定操作
    • 実行不可能性の判定方法
    • 緩和問題の解き方
  • 分枝操作
    • 問題の分解方法

今回は概念の話に終始しましたが、具体例が必要という場合は[3]を見ると良い気がします。

# 参考文献
[1]http://www.ie.u-ryukyu.ac.jp/~e085739/_downloads/H22.Math.Prog.No.7.pdf
[2]http://www.dais.is.tohoku.ac.jp/~shioura/teaching/mp11/mp11-06.pdf
[3]http://dopal.cs.uec.ac.jp/okamotoy/lect/2013/opt/handout05.pdf

github上のプロジェクトをカスタムしてbitbucket上に自分専用プロジェクトとしてコミットする方法

下記のページがわかりやすいです。
簡単に説明すると、まずbitbucket上にからのレポジトリを作り、そこにgithub上のレポジトリをpullします。その上で変更点をadd & commitするという流れです。

Forking a Github repo to Bitbucket · GitHub

プログラムを書く際に注意すべき点

Programming

順次追記していきます。

  • プログラムを書く際、関数の引数として与える数字の単位系・座標系は、クラス毎・ファイル毎に揃えよう

単位系・座標系が入り混じると、想定と異なる単位系・座標系で数値を入力し、想定と異なる挙動に悩まされる可能性が高まります。もちろん単体テストをしていれば防げる訳ですが、製品開発をしているならまだしも、研究開発や趣味で書いている場合は中々テストまでは書かないのではないかと思いますので、ご注意ください。

英語の文章を書くときに便利なサービス

英語 文書作成

ここでは説明を省略します。お手数ですがご自身で内容の確認をお願いいたします。

  • Grammaly : 文法的な間違いや冠詞・単語の使い方が不正確な場合に指摘をしてくれます

www.grammarly.com

  • Reverso Translation : 文法というよりも、冠詞・単語の使い方の間違いを指摘してくれるように感じます。

www.reverso.net

ROSにおけるCMakeLists.txtの書き方

ROS

逐次わかったこと、気づいたことを追記していきます。

catkin_package(　 # ここには自ら（このCMakeLists.txtが含まれているROS Packageのことを書きます
INCLUDE_DIRS # headerファイルを探しに行く時のルートディレクトリを記載します　→　1)へ
LIBRARIES # add_libraryで定義したライブラリ名を列挙します →　2)へ
CATKIN_DEPENDS # あんまりわかっていないので後日....
DEPENDS # あんまりわかっていないので後日....
)

1) INCLUDE_DIRS
例えば"package_name/include/foo/bar.h"というファイルがあります。find_packgeなどで外部の情報を得ない限り、ソースファイルと同じディレクトリのheaderしかincludeできません。しかしINCLUDE_DIRSを定義すれば、定義したパスからも探してくれます。例えば"INCLUDE_DIRS include"と定義すれば、ソースファイルに"#include "と記載すれば、そのheaderは見つかります。少し変えて"INCLUDE_DIRS include/foo"とすれば、"#include "とすれば見つかります。なおINCLUDE_DIRSにパスを書く場合は、CMakeLists.txtからの相対パスを書くか、絶対パスを書く必要があります。

2)LIBRALIES
add_libraryで定義したライブラリ名を列挙することで、他のパッケージがこのパッケージをfind_packageした時、他のパッケージがそのライブラリを使用することができます。そのため、LIBRARIESに間違ってもadd_executableに記載した名前、はたまた存在しない名前を書くと、他のパッケージがfind_packageした時に、"CMake Error at /home/ユーザ名/catkin_ws/devel/share/パッケージ名/cmake/パッケージ名Config.cmake:該当行 (message):
Project 'その他のパッケージ' tried to find library 'ライブラリ名'. The library is neither a target nor built/installed properly. Did you compile project 'floor_plan_matcher'? Did you find_package() it before the subdirectory containing its code is included?"等と表示され、find_packgeが失敗します。ご注意ください。このパッケージが出た場合、find_packageしようとしているパッケージのLIBRARIESの定義を確認してみてください。