ma38su.org

最短経路問題をあえてLPで解いてみる

2009-03-28 (Sat)
Algorithm

ちょっと一度，自分でシンプレックス法を実装してみるかなーと思っていろいろ調べてたら，最短経路問題が線形計画問題に緩和して簡単に解ける（最適解が小数にならない）ということを知った．よく考えれば確かにそうなのだけど，せっかくなので基本の基本なのかもしれないけど，試してみた．

とりあえず，GLPKを使ってみた．まず定式化して.modに記述する．たいした問題じゃないので（面倒なので）最短経路を求めるグラフは描画しないが，頂点はv1からv6からなる有向グラフにおいて，v1から，v6の最短経路を求める．その最短経路問題の定式化を以下に示す．

var x1 >= 0;
var x2 >= 0;
var x3 >= 0;
var x4 >= 0;
var x5 >= 0;
var x6 >= 0;
var x7 >= 0;
var x8 >= 0;
var x9 >= 0;
var x10 >= 0;

minimize profit: 8*x1 + 4*x2 + 6*x3 + 5*x4 + 3*x5 + 9*x6 + x7 + 7*x8 + x9 + 2*x10;
s.t. v1: - x1 - x2                                          = -1;
s.t. v2:   x1      - x3 - x4 + x5                           =  0;
s.t. v3:        x2           - x5 - x6                      =  0;
s.t. v4:             x3                - x7 - x8 + x9       =  0;
s.t. v5:                  x4      + x6 + x7      - x9 - x10 =  0;
s.t. v6:                                      x8      + x10 =  1;

結果は，以下の通りちゃんと整数で出力された．

Problem:    path
Rows:       7
Columns:    10
Non-zeros:  30
Status:     OPTIMAL
Objective:  profit = 14 (MINimum)

   No.   Row name   St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 profit       B             14
     2 v1           NS            -1            -1             =            -4
     3 v2           NS             0            -0             =             3
     4 v3           B              0            -0             =
     5 v4           NS             0            -0             =             7
     6 v5           NS             0            -0             =             8
     7 v6           NS             1             1             =            10

   No. Column name  St   Activity     Lower bound   Upper bound    Marginal
------ ------------ -- ------------- ------------- ------------- -------------
     1 x1           NL             0             0                           1
     2 x2           B              1             0
     3 x3           NL             0             0                           2
     4 x4           B              1             0
     5 x5           B              1             0
     6 x6           NL             0             0                           1
     7 x7           B              0             0
     8 x8           NL             0             0                           4
     9 x9           NL             0             0                           2
    10 x10          B              1             0
（以下略）

Comments: 0
Trackbacks: 0

Vimperator 2.0 beta 2.0

2009-02-27 (Fri)
Software

ぜんさんにVimperatorを勧めてみたら早速使ってもらえたみたいだけど，中途半端に勧めたせいもあって，不満を書き連ねられてしまった．めんどうですが，多少設定をしないと十分に使えません．

研究室で布教活動をしていたときも，2.0の導入について書いてるページがほとんどないなーと思ってたのでついでに軽くまとめてみる．

インストール

とりあえず，http://vimperator.org/trac/wiki/Vimperatorから，2.0 beta 2.0をFirefoxにインストールする．

vimperatorrc

Windowsだとユーザ環境変数HOME以下(MacやLinuxだと，~/以下)に，

.vimperatorrc
_vimperatorrc

のどちらかの名前で設定ファイルを作る．
:mkvimperatorrc
と打ってもできるらしい．とりあえずやっておくべき設定を書いておく．

" タイトルバーの表記を直す
set titlestring="Mozilla Firefox"

" Tabキー押さなくても自動補完
set wildoptions=auto

" sで，登録してるキーワードの補完(gでGoogleとか)，lで:openなどの補完をアドレスバーの補完が可能
set complete=sl

" 検索結果を強調表示
set hlsearch

" 履歴を1000件
set history=1000

" 自動でテキストエリアにフォーカスしない（なんか微妙）
set focuscontent

" 最初の補完を早くするらしい
set preload

" tabバーを1件以上で表示
set showtabline=1

" menuバーを表示(Macは不要)
set guioptions=m

" ステータスバーにFeedのアイコンを表示させる
js << EOF
(function(){
	var feedPanel = document.createElement('statusbarpanel');
	var feedButton = document.getElementById('feed-button');
	feedPanel.setAttribute('id','feed-panel-clone');
	feedPanel.appendChild(feedButton.cloneNode(true));
	feedButton.parentNode.removeChild(feedButton);
	document.getElementById('status-bar').insertBefore(feedPanel,document.getElementById('security-button'));
})();
EOF

vimperator プラグイン

http://coderepos.org/share/browser/lang/javascript/vimperator-plugins/trunkから，必要なプラグインをダウンロードして，$HOME/.vimperator/plugin以下におく

.vimperatorrcにプラグイン用の設定を書き足す．

" migemo_hints.js / ローマ字入力でhintの絞り込み
" XUL/migemoが別途必要 https://addons.mozilla.org/ja/firefox/addon/5239
set hintmatching=custom

" feedSomeKeys_2.js / 指定したキーをスルーさせる
autocmd LocationChange .* :fmapc
"" LDR
autocmd LocationChange reader¥¥.livedoor¥¥.com/reader :fmap j k s a p o v c  <S> z b
"" Gmail
autocmd LocationChange mail¥¥.google¥¥.com/mail :fmap -depth 4 c / j k n p o u e x s r a # < > z ? gi gs gt gd ga gc
"" その他必要に応じて．．．

" ime_controller.js / ex mode および textarea mode への移行時にIMEを指定の状態に切り変える
let g:ex_ime_mode = 'inactive'
let g:textarea_ime_mode = "inactive"

あとは好みで，キーバインドの設定をj,kでのスクロール量の変更したりとかの設定をすると幸せになれそうです．

" jの移動量3倍
noremap j 3<C-e>

" kの移動量3倍
noremap k 3<C-y>

" hで戻る
noremap h <A-Left>

" lで進む
noremap l <A-Right>

" 矢印キーや，C-n, C-pでも補完を選択できるように
cmap <Down> <TAB>
cmap <Up> <S-TAB>
cmap <C-n> <TAB>
cmap <C-p> <S-TAB>

EOF

Comments: 0
Trackbacks: 0

Vimperator

2009-02-24 (Tue)
Software

gitとかsvnで管理するほどでもないので，とりあえず貼付けておく．

set titlestring="Mozilla Firefox"
set wildoptions=auto
set hlsearch
set showtabline=0
set complete=sl
set history=1000
set focuscontent
set preload
set verbose=9
set showtabline=1

map j 3
map k 3
map h 
map l 
map bs :bs 

" move feed to status bar
js << EOF
(function(){
	var feedPanel = document.createElement('statusbarpanel');
	var feedButton = document.getElementById('feed-button');
	feedPanel.setAttribute('id','feed-panel-clone');
	feedPanel.appendChild(feedButton.cloneNode(true));
	feedButton.parentNode.removeChild(feedButton);
	document.getElementById('status-bar').insertBefore(feedPanel,document.getElementById('security-button'));
})();
EOF

" migemo_hints.js
set hintmatching=custom

" google_search.js
map gs :gsearch 

" feedSomeKeys_2.js
autocmd LocationChange .* :fmapc
autocmd LocationChange reader¥¥.livedoor¥¥.com/reader :fmap j k s a p o v c  <S> z b
autocmd LocationChange mail¥¥.google¥¥.com/mail :fmap -depth 4 c / j k n p o u e x s r a # < > z ? gi gs gt gd ga gc

" ime_controller.js
let g:ex_ime_mode = 'inactive'
let g:textarea_ime_mode = "inactive"

" direct_bookmark.js
let g:direct_sbm_use_services_by_post = "h"
let g:direct_sbm_use_services_by_tag = "h"
map a :sbm [

colorscheme original
echo .vimperatorrc sourced

カラースキームもあちこち参考にしながら多少自分好みにしてみたけど，ほとんどデフォルトで問題ないなーって思ったりする．

" Hint
hi Hint         z-index:5000; font-family: "Lucida Grande", monospace; font-size: 11px; padding: 0 0.25em; margin: -0.5em 0 0 -1em; background-color: #f07e00; border: 1px #ff7d00 solid; -moz-border-radius: 4px; color: white; font-weight: bolder; opacity: 0.9;
hi HintActive   z-index:4990; background-color: #88FF00; color: black;
hi HintElem     z-index:4900;	background-color: yellow; color: black;

" Status Line
hi StatusLine font-size: 11px; color: #000; background: url("chrome://global/skin/statusbar-background.gif") #949393 repeat-x top left; border-top: 1px solid #888; height: 22px; padding-left: 0.5em;
hi StatusLineSecure font-size: 11px; color: #262626; background: url("chrome://global/skin/statusbar-background.gif") #949393 repeat-x top left; border-top: 1px solid #888; height: 22px; padding-left: 0.5em;
hi StatusLineBroken font-size: 11px; color: #d00f0f; background: url("chrome://global/skin/statusbar-background.gif") #949393 repeat-x top left; border-top: 1px solid #888; height: 22px; padding-left: 0.5em;