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;
- Comments: 0
- Trackbacks: 0
screen
ローカルだと,Terminal.appのタブで事足りるのだけど,遠隔のサーバで作業すると,そうも行かないので,screen使ってるのだけど,UTF-8を表示させようとすると化けるどころか固まるさえよくあっていろいろ面倒だった.
ちょっと調べてみたら,
screen -U
でUTF-8が表示できるようになるらしい.ついでに,
termcapinfo xterm* ti@:te@
でMacのTerminal.appでバッファをスクロールできるようになる.よくわからないけど遠隔でログインしてるLinuxでもうまくいってる.この辺かなり不便だったので解消できてうれしい.ここらへんの細かいとこまでちゃんとまとめてくれてるドキュメントがどこかにないかなー?
ちょっと何か書くくらいならはてダが楽でいいなー,と最近思えてきた.
- Comments: 0
- Trackbacks: 0
うごメモ
- 2008-12-19 (Fri)
- Days
DSiをうまく使ってるなぁと思う.それにしても,ニンテンドーのサービスはいつもぶれがないなーと感心します.
それにしても,WordPressじゃ,貼付けられないなんて...プラグイン書くか...
- Comments: 0
- Trackbacks: 0