2016-01-26

雑感

気になった本

2015-12-15

直線数最適化障害物回避問題

計算機科学アルゴリズムメモ Ruby D3.js

f:id:with137d:20151216230500p:plain

解きたい問題

障害物のある平面において起点と終点を結ぶ経路を探索し直線数を最小化したい。
障害物は線分で与えられる。
経路の長さは目的としない。

f:id:with137d:20151216230507p:plain この画像は問題の単なる一例であり、障害物は平面上に自由に置けるものとする。

解決手順

適当な細かさのGridに対応させて考える。
障害物により格子点の連結を切断する。
BeamSearchを用いて起点から終点までの経路を求める。
得られた点列をGreedyに直線列に変換。
焼きなまし法(SimulatedAnealing)で直線数を減らす。

Rubyによるソースコード(Ideone)

考察

与える問題のパラメータによってGridの細かさなどを変更する必要がある。
BeamSearchは驚くほど便利。
SimulatedAnealingは「近傍をどう生成するのか」が難しい。
- 今回は、「経路のうちの一点を選ぶ」「移動先としてランダムに新しい格子点を選択」「障害物に当たらないかを検査」「当たらないなら前後の直線を縮約できればやる」として近傍を生成した。
はじめGridなどを考えずにデカルト平面上でSA法を適用し経路探索と直線数最小化を一度にしようとしたが精度や計算量的に失敗だった。
残る問題としては交差判定に時間がかかっている点。SA法の中で近傍探索する際にすべての障害物と着目する直線との交差判定をしている。BoundingBoxなどで不必要な交差判定をなくしたほうが良い。
結果

可視化について

D3.jsを用いて描画した。
ソルバはJSON形式で結果を出力。
ruby -run httpd -- . -p 8000によりHTTPサーバを立てる。
カレントディレクトリにJSONファイルとそれを表示するHTMLファイルを置く。
SVGをPNGに変換し保存。変換用コードは下に示すJavaScriptコード。

結果表示用HTML(codepad)

WindowsからLinuxにPuttyで接続して開発しているためブラウザでデータをやり取りしたかった。WinSCPは手間。D3.jsによる可視化はその点においても親和性の高いやり方だと思った。
SVGからPNG画像の変換についてはSave SVG as an Image | TechSlidesを参考にした。

2015-07-09

VimのViewを自動的に保存/復帰

メモ Vim

autocmd BufWinLeave ?* if &buftype == '' | mkview | endif
autocmd BufWinEnter ?* if &buftype == '' | silent loadview | endif

buftypeを見ることで特殊なバッファ(helpなど)を処理から除外
ファイルパターンに ?* を指定することでファイル名を指定しない呼び出し(vimコマンドを無引数で実行するときなど)を除外

2015-07-05

大域最小カット(Global Minimum Cut)

メモ計算機科学アルゴリズム Ruby

問題

連結無向グラフ $G=(V,E)$ のカットのうち最小のものを求める。

実装

ソースコード(IdeOne)

解説

乱択アルゴリズムによる実装。
一辺をランダムに選んで縮約していく。
最後に2点残る。これらの点に縮約された点が大域最小カットである可能性は $1/\binom{n}{2}$ 以上。
頂点の数を $n$ とし、 $\binom {n}{2} \ln n$ 回アルゴリズムを繰り返すとき、大域最小カットが得られない確率は $\frac{1}{n}$ 以下となる。
決定的アルゴリズムの素朴な実装は始点 $s$ を任意に選び、 $s-t$ カットアルゴリズムを $n-1$ 回使用して最小値をとったものとなる。これは多項式時間アルゴリズムである。
このKargerによる方法をさらに改良したアルゴリズムがある。参照(pdf)
大域最小カット問題は画像の領域分割に使えるらしい。

2015-07-04

最近点対問題(Closest Pair of Points)

メモ計算機科学アルゴリズム Ruby

問題の定義

平面上のn個の点の中からユークリッド距離が最小の点の組み合わせを出力する。

実装

ソースコード(Ideone)

解説

入力をランダムにシャッフルしたのちに逐次添加アルゴリズムを用いる。
アルゴリズムが実行される任意の時点において、一辺の長さ $\frac{\delta}{2}$ のメッシュ構造が保たれている。 $\delta$ はその時点で発見済みの二点間の最小距離。
このメッシュ構造においては、最小距離を更新される可能性のある点は、着目している点の周り25個の小正方形内に限られる。
計算量は $O(n)$ 。素朴な実装では $O(n^{2})$ 、ソートして分割統治するアルゴリズムでは $O(n \log n)$ であるから驚くべき改善である。

2015-06-26

PSReadline

メモ PowerShell

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
}

プロファイルに上記コードを追加する。

参考

about_PSReadline
PSReadLine
PSReadLine - コマンドライン編集機能強化
 How to install the PowerShell console extension PSReadLine

2015-06-24

VLCプレイヤーでの文字化け問題

メモ

VLC Playerを使用時にプレイリスト内のタイトル等の曲情報が文字化けする問題があった。
はじめにフォントの設定の問題かと思ったがそうではなかった。
ID3タグ内の情報がShiftJISで保存されていることが原因だった。
とりあえずMP3内のID3v2タグをUnicodeに変換するID3Uniというソフトで変換して対処した。

noise

計算機科学や各種設定のメモ

雑感