雑感
気になった本
- Amazon.co.jp: 実践 コンピュータビジョン: Jan Erik Solem, 相川 愛三: 本
- Amazon.co.jp: Amazon Web Services パターン別構築・運用ガイド: NRIネットコム株式会社, 佐々木 拓郎, 林 晋一郎, 小西 秀和, 佐藤 瞬: 本
- Amazon.co.jp: プログラミング言語C++第4版: ビャーネ・ストラウストラップ, Bjarne Stroustrup, 柴田 望洋: 本
- Amazon.co.jp: C++のエッセンス: ビャーネ・ストラウストラップ, Bjarne Stroustrup, 柴田 望洋: 本
- Amazon.co.jp: 深層学習 (機械学習プロフェッショナルシリーズ): 岡谷 貴之: 本
- Amazon.co.jp: スパース性に基づく機械学習 (機械学習プロフェッショナルシリーズ): 冨岡 亮太: 本
直線数最適化障害物回避問題
解きたい問題
- 障害物のある平面において起点と終点を結ぶ経路を探索し直線数を最小化したい。
- 障害物は線分で与えられる。
- 経路の長さは目的としない。
この画像は問題の単なる一例であり、障害物は平面上に自由に置けるものとする。
解決手順
- 適当な細かさのGridに対応させて考える。
- 障害物により格子点の連結を切断する。
- BeamSearchを用いて起点から終点までの経路を求める。
- 得られた点列をGreedyに直線列に変換。
- 焼きなまし法(SimulatedAnealing)で直線数を減らす。
考察
- 与える問題のパラメータによってGridの細かさなどを変更する必要がある。
- BeamSearchは驚くほど便利。
- SimulatedAnealingは「近傍をどう生成するのか」が難しい。
- 今回は、「経路のうちの一点を選ぶ」「移動先としてランダムに新しい格子点を選択」「障害物に当たらないかを検査」「当たらないなら前後の直線を縮約できればやる」として近傍を生成した。
- はじめGridなどを考えずにデカルト平面上でSA法を適用し経路探索と直線数最小化を一度にしようとしたが精度や計算量的に失敗だった。
- 残る問題としては交差判定に時間がかかっている点。SA法の中で近傍探索する際にすべての障害物と着目する直線との交差判定をしている。BoundingBoxなどで不必要な交差判定をなくしたほうが良い。
結果
可視化について
- D3.jsを用いて描画した。
- ソルバはJSON形式で結果を出力。
ruby -run httpd -- . -p 8000
によりHTTPサーバを立てる。- カレントディレクトリにJSONファイルとそれを表示するHTMLファイルを置く。
- SVGをPNGに変換し保存。変換用コードは下に示すJavaScriptコード。
VimのViewを自動的に保存/復帰
autocmd BufWinLeave ?* if &buftype == '' | mkview | endif autocmd BufWinEnter ?* if &buftype == '' | silent loadview | endif
- buftypeを見ることで特殊なバッファ(helpなど)を処理から除外
- ファイルパターンに ?* を指定することでファイル名を指定しない呼び出し(vimコマンドを無引数で実行するときなど)を除外
大域最小カット(Global Minimum Cut)
問題
連結無向グラフのカットのうち最小のものを求める。
実装
解説
PSReadline
PowerShellの初期状態ではBashのように
- Ctrl+P/Ctrl+Nキーでコマンド履歴を呼び出し
- PageUp/PageDownでバッファを移動
などを行うことができない。
この問題はPSReadLineモジュールによって解決する。
これでかなり使いやすくなった。
インストール
(new-object Net.WebClient).DownloadString("http://psget.net/GetPsGet.ps1") | iex Import-Module PsGet Install-Module PsReadline
ちなみにWindows10からはPsGetを導入する必要はないらしい。標準でインストールされるPowerShell5に新しいパッケージマネージャが組み込まれているそうだ。
Install-Module -Name PSReadline
とするだけでインストールできるみたいだ。
設定
if ($host.Name -eq 'ConsoleHost') { Import-Module PSReadline Set-PSReadlineOption -EditMode Emacs -BellStyle None }
プロファイルに上記コードを追加する。