週に一回は書きますよ 月に4つ記事を書けばノルマは満たされます。
上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
名称のEclipseとは「食(蝕)」の意の英語で、日食や月食を指し、Javaを開発した米Sun Microsystems(太陽)との関係を想起させる。
Eclipse (統合開発環境) - Wikipedia

こんな凄い名前であることに全然気づいていませんでした。

スポンサーサイト

迷路のことを考えていたのは、迷路を利用してグラフを生成できないかと思ったからでした(突っ込み所だけど後にとっておいて。) 考えていたのは次のようなアルゴリズムです。

  • 空間に粗いグリッドを引いて、それに沿って迷路を作る。
  • 空間上にランダムに点を撒く。
  • 点と点とをつなぐ線分のうち、迷路の壁にぶつからないものだけを辺として採用する。

このアルゴリズムに到った経緯です。最短経路を求めさせる問題で、どんなグラフが適切か考えていました。 頂点と辺の数を決めてランダムに辺を渡すという方法が一番素直です。私はこの方法では満足できません。この生成方法だと始点と終点が近くなりがちなのです。もっと一般的なグラフ、もっと現実の問題に近いグラフ、それからもっと病的なグラフがほしいのです。

まず想定していたのは空間に点を撒いて近い点をつなげるアルゴリズムでした。これは適度にランダムなグラフができ、しかもスタートからゴールまで適度に距離があります。 しかしこれでは、場合によっては最短距離を求めるのがえらく簡単になります。たとえばゴールの方向がわかっている場合、大体その方向になるように向かうだけでほぼ最短距離になります。A*法が効きすぎます。

そこで迷路です。直進で最短距離に行けないのは迷路に決まっています。迷路に沿う形でグラフを作れば、スタートからゴールまで距離のある、しかも難しいグラフができるはずです。空間をどのくらいに区切って迷路を作るか、その中にどのくらいの頂点を撒くかはあまり考えていないものの、迷路はそれほど細かくないほうがいいような気がします。

ところで迷路もグラフじゃないかと突っ込んだ人はいませんか。今日はそれに気づきました。と言うことはつまり粗いグラフの中に密なグラフ構造を埋め込むといったことをしているわけですね。循環を持たない迷路はグラフで言うとツリーです。一般化すると上のアルゴリズムは次のような感じになります。

  • 適当なグラフを作る。
  • グラフから適当に枝を取り除いて木を作る。
  • 木に沿う形で頂点、辺を配置してグラフを作る。

一般化して何ができるかはまだよくわかりません。上に書いた生成方法では実はくだらないグラフしかできないと言うことが証明されるかも知れません><

N次元グリッドでの迷路作成アルゴリズムがほしくなりました。知っているアルゴリズムは二次元の迷路生成だけです。それらが拡張できないか電車の中で考えてみましたが、三次元でも頭が痛くなりました。

google:迷路生成で検索したところ二次元の迷路についてはすばらしい解説をたくさん発見。三次元以上の解説は殆どありませんが。 その中ではこの 自動生成迷路の記事は二次元限定ですが、さまざまな手法を図を用いて説明していてすばらしいです。わかりやすすぎる。

一般次元にすぐ適用できるのは上のリンク先の穴掘り法です。一般のグラフに適用可能であると迷路生成 @ Stardust Crownにも書いてあります。 そのほかは三次元でも私の理解を超えるので無理です。

共立出版工系数学講座 グラフ・ネットワーク・組合せ論のDinitz(Dinic)のアルゴリズムは最適じゃない気がします。正しいけど少し遅い。 この本だと距離ラベルをsourceからの距離で計算しています。逆に、sinkからの距離で計算したほうが速いのではないかと思うのです。こっちだとdfsのときにフローが確実にsinkへ流れてゆきます。sourceからの距離で計算するとフローが行き止まりに突き当たってバックトラックすることが多くなります。もちろん、一回バックトラックした枝は切除していいのでそれほど遅くなるわけではありませんが。

雑な例で調べたら等倍~二倍程度の速さでした。自信を持って速いといえるほど速くないです。

夜1時から開始。前回が凄惨だったので失ったratingを取り戻しに来ました。

とは言ったものの、明らかに眠かったです。もう400 pts の問題が全然読めませんでした。 なかなか問題が意味不明だったし。とりあえず250 ptsと400 ptsを解いて、1000眺めてたら時間終了していました。解いた問題でも、一番重いケースやコーナーケースを全然試していません。さらにChallenge Phaseではもう寝てました。

朝起きたら部屋二位。かなりの人が400 ptsをSystem Testで落としていました。どんなコーナーケースがあったのでしょう。とりあえずratingは半分以上取り戻しました

B. V. Cherkassky and A. V. Goldberg. On Implementing Push-Relabel Method for the Maximum Flow Problem. Technical Report STAN-CS-94-1523, Department of Computer Science, Stanford University, 1994.

その他いろいろ。

  • Preflow Push Algorithmができる前はDinitzのアルゴリズムが最速で、これの変種が膨大に研究されていた。
  • GoldbergはPreflow Pushだけで何年も論文を出してたりする。
  • 速度計測の論文も腐るほどある。標準テストケースもたくさん用意されていて、Network Flows and Matchingといった本に詳しく記述されているらしい。
    • さすがに本はすぐには手に入らない。
  • ymatsuさんお勧めAlgorithm Designを眺め中。

まじめに調べると先行研究はものすごくたくさんありますね。教科書に載らないほど。いや、Algorithm Designにはすべて収まっているのかな。

http://www.ne.jp/asahi/new/legend/mansaku/diary.html#20080517

教習の初期に、曲がっている最中にハンドルを戻す感覚がつかめなくて苦労しました。曲がり終わってからハンドル戻そうとすると手遅れ。余計曲がってしまう。 回転半径とか意識できるようになるのは正直路上に出てからだったと思います。

昨日の話。

Amazon.co.jp ご注文の発送
14:47
Amazon.co.jpからのお知らせ

       ご注文いただいた商品をできるだけ早くお客様にお届けするため、
以下の商品を分割して発送させていただきました。残りの商品も、準備
でき次第発送いたします。
(snip)
お客様へのご請求は、発送済みの商品についてのみ行いました。
(Amazon.co.jpの規約により、お客様に発送した商品についてのみお支
払いいただいております)
以下の商品は、準備ができ次第分割して発送いたします。
(snip)

あらら。

Amazon.co.jp ご注文の発送
17:19
Amazon.co.jpからのお知らせ

お客様からご注文いただいた 商品 を本日発送させていただきました。

ご注文の処理が完了しましたのでお知らせします。

Amazon.co.jpをご利用いただき、ありがとうございました。またのご利用を
お待ちしております。

amazonはせわしないですね。

  • stackはpush, pop, top
  • queueはpush, pop, front
  • priority_queueはpush, pop, top

規則性がつかめません。

この間のGoldberg-Tarjanの実装バグを特定しました。 実装として活性頂点をキューで保持していて、そのキューに終点が紛れ込んだのが原因でした。 始点と終点は活性ではないはずですが、間違えて活性として扱ってしまったため終点からフローをすべて始点に戻して流量が0になっていました。

もともと、始点と終点はキューから除外していました。 flow pushして頂点をキューに追加する際に、頂点が始点や終点でないのを確認していました。しかし、初期条件での活性点を追加するところではチェックを忘れていました。初期条件での活性点は始点から枝一本でたどれる頂点なので、つまり始点と終点とが直接つながっているとこのバグを踏みます。pkuの1459番のデータにはそういうものはないので、バグを踏まずacceptされていました。

あるえー。昨日の記事はどうも間違っているらしいです。今日は次のように書くつもりでした。

昨日の記事、正しい定義は次のとおりでした。

#define TLIST0() NullList
#define TLIST1(a) TypeList<a, TLIST0()>
#define TLIST2(a, b) TypeList<a, TLIST1(b) >
#define TLIST3(a, b, c) TypeList<a, TLIST2(b, c) >
#define TLIST4(a, b, c, d) TypeList<a, TLIST3(b, c, d) >

空白がないとシフト演算子ができるという罠。本当は括弧でマクロ全体をくくったりして安全にできるといいのですが、ここで括弧を書くとまた文法エラーになります。

しかし納豆神が書いたプログラムは確かにcygwin GCC 3.4.4のコンパイルを通ります。 TLISTは期待通りにコンパイルされ、どこにも右シフトは存在しないようです。

多分私のプログラムのエラーはこれとはちょっと違う原因でエラーになったのでしょう。困ったことに今はエラーが再現しません。ちゃんとバージョン管理してなかったのでどういう状況だったのかもよくわかりません。

いまさらhgで管理を始めました。

つい魔が差して Modern C++ DesignのTypeListをそらで書こうとしたところ、コンパイラエラー祭りになりました。

TypeListは型のリストです。まず次の型を書きます。

template<typename H, typename T>
struct TypeList {
  typedef H Head;
  typedef T Tail;
};

これをcons cellと見立てます。これを使うと、たとえば次のような、char, short, longからなるリストが作れます。NullListはstruct NullList{};といった程度のものです。

TypeList<char, TypeList<short, TypeList<long, NullList> > >
こういったリストを用いて、たとえばchar, short, longすべてについて何かを行うといった関数が書けます。

ここまではうまく書けたのですが、次で失敗をしました。TypeListの列を書くのが面倒なので、普通はラッパーマクロを書きます。

#define TLIST0() NullList
#define TLIST1(a) TypeList<a, TLIST0()>
#define TLIST2(a, b) TypeList<a, TLIST1(b)>
#define TLIST3(a, b, c) TypeList<a, TLIST2(b, c)>
#define TLIST4(a, b, c, d) TypeList<a, TLIST3(b, c, d)>

これを使って、たとえば上のリストはTLIST3(char, short, long)とできます。

さて、上のTLISTnの定義はコンパイルできません。TLIST3(char, short, long)と書いたとたんにエラーになるはずです。おかしいのはどこでしょうか。


5/13追記:どうもこのままで正しいらしいです。私は何かエラーを受けたのですがそれはTLIST由来ではなかったらしいです。不正確ですみません。

ついでに最大流の速度実測を適当に書いたところ、Goldberg-Tarjanだけ時々値が違うという落ちがつきました。明らかにバグです。

論文の引用の仕方を忘れております。

読んだのは今井先生のを大体と、Ahujaのアルゴリズムの部分の半分。

今井先生のは基本は最大流アルゴリズムの速度の実測。ランダムグラフとグリッドと、それから実際のグラフ(鉄道網)を使っています。 選んだアルゴリズムにGoldberg-Tarjanがないのが残念。

速度の実測方法がわかったのが一番の収穫です。正確に言うと実測方法は別にたいしたことなくて、 たいしたことない実測方法で実測して論文になるとわかったのが一番の収穫です。 これを読むまでは、ランダムなグラフをどのように生成すればいいかいろいろ悩んでました。 一応グラフの連結などを調べたほうがいいかとか。 しかし論文を見た感じでは、余り何も考えなくてもよいようです。 たとえばグラフの連結性は各頂点の次数がある程度確保されれば自動的に満たされます。

それから、グリッドをグラフとして利用することは思いつきませんでした。 グラフが疎か密か位しか想定していなかったので、これも助かります。 次元を増やしたり、むしろN次元上にランダムに頂点を撒いてボロノイ図で接している兆点間を結んだりとかいろいろなパターンができそうです。

Ahujaのほうは、Ahuja-Orlinだと思っていたアルゴリズムがGabowのアルゴリズムだったことが一番の衝撃です。Ahuja-Orlinとして紹介されているアルゴリズムはまったく違う、Goldberg-Tarjanと同じポテンシャルを使うものでした。本人が書いているのでおそらくそれが正しいのでしょう。

http://shinh.skr.jp/m/?date=20080511#p02

げ、w3mの検索は/しか使ってませんでした。w3mのキーバインドはviのものしか、あるいはlessのものしか記憶していない感じが。

ちょっと補足。私もたとえばmainまで飛ぶときは検索を使ってました。ただ、最近はもっと激しく、たとえば=に飛ぶとかx2に飛ぶとか、さらにはシェルの編集のために直前の|まで飛ぶとかができるようになりました。

この辺を注意するようになったのは、インクリメンタルサーチを酷使しているハカーに会ったからです。彼はタイピングが速い上に、かなり変なところまでインクリメンタルサーチで一発で飛んでいて、コマンドラインをあっという間に修正していました。 これは見習うしかない。

帰国してからxyzzyの操作に慣れません。出張中はずっとMacbook Proを使っていて、carbon emacsかterminal app上でemacsを使っていました。そのため今までは気づかなかった違いに戸惑います。

一番大きな違いはインクリメンタルサーチ後の挙動です。インクリメンタルサーチした後に矢印キーで下や上を押して移動することができません。C-pやC-nは有効なので、それらを使えということだと思いますが。

インクリメンタルサーチを酷使するようになったのはごく最近です。今まではこれはただの検索だと思っていました。今ではカーソル移動の手段です。文全体を把握しているなら、矢印キーやC-fを連打するよりも検索したほうが大体速いです。同じ行の中でも変数名や演算子(=とか|とか)をキーにして移動します。日本語の場合はまったくうまくいきませんが。

vmware serverをホストOS:Windows XP, ゲストOS:debian etchで導入したのでメモ。 火曜日に一回試したときは失敗しましたが今日はうまく行きました。

昨年冬に新調したコンピュータのWindows XP側に、vmware serverを導入してみました。 目的は常駐サーバの設定です。実はすでにこの機械はubuntuとdual bootになってます。しかしubuntuはまったく使っていませんでした。実家なのでWindowsが必要なのです。そのためubuntuで常時立ち上げておくことができません。常時立ち上がってないサーバほど役に立たないものはないでしょう。Windowsと共存するためにはvmware serverを導入することにしました。

まずはvmware serverを導入。メールアドレスを書いてシリアル番号を送ってもらう必要があります。そのほかのインストールは普通にできました。

次にlinux導入イメージを用意。今回はdebianを入れてみました。jp.debianのネットワークインストールページからdebian-40r3-i386-netinst.isoをダウンロード。

次の二つのページを参考にしました。

まずvm作成。Typical, Other Linux 2.6.xで。ネットワークをブリッジにして、ついでにメモリを432MBにしてみました。どのくらいメモリがいるのかわかりません。 VM作成後に、CD-ROMにnetinstall用イメージを設定。CD-ROMをクリックしてUSE ISO imageを選び、先ほどのイメージを選択。

起動。日本語で適当に。ネットワークミラーにcdn.debian.or.jpが見つからないのでftp.jp.debian.orgを設定。デスクトップ環境をはずして設定。

最後のGRUBのインストールでなぜか刺さりました。一時間ほど放置したものの変化が見られず、仕方ないのでリセット。CDからブートするように、vmware起動画面でESCを押してブートデバイスをCD-ROMに指定して再インストール。二度目で成功。

起動後、とりあえずexport LANG=C。ls -lとかmanで漢字が出て、すべて豆腐になるのを回避。記事を参考に、とりあえずapt-get upgradeするのがよさそうなのでaptの設定。cdn.debian.or.jpを設定して、CDROMを削除してcontribとnon-freeを追加。

deb http://cdn.debian.or.jp/debian etch main contrib non-free
deb-src http://cdn.debian.or.jp/debian etch main contrib non-free
deb http://security.debian.org etch/updates main contrib non-free
deb-src http://security.debian.org etch/updates main contrib non-free
#apt-get update, #apt-get upgradeしてとりあえず放置。まだ何もできてないですが。

時々不思議に刺さります。書いたのはgrubインストールのときだけですが、前回はもっといろいろと刺さりました。それからネットワークの不調も頻発します。再起動で直りますが、再起動で直すのはWindows脳な感じがします。

とりあえずさくっとEdmonds-Karp, Dinitz, Ahuja-Orlin, Goldberg-Tarjanを書いて uva 1459に投稿してみました。グラフはすべて隣接行列で表現して、vector<vector<int> >に保存しています。 結果はそれぞれ1547, 157, 1360, 344 ms。pkuは最適化してくれないのでvectorで多次元配列を作ると最大100倍くらい遅くなった記憶がありますが、その中では適当な速さで動いているようです。ところでDinitz何か壊れてませんか?何でこんなに爆速なんでしょう。

Ahuja-Orlinはちゃんと論文を読んでないのでおかしい可能性が高いです。 それから、Ahuja-Orlinは流量を1づつしか増やせないようなグラフだと効果はないですよね。よくわかってませんが。

Goldberg-Tarjanは頂点の選び方もheuristicsも何もしていません。queueにexcited verticesを保存して順に取り出しただけ。これをpriority_queueにすると頂点をもう少しまじめに選べるはずです。そのほかのheuristicsはまったくわかっていません。文献は元論文でいいのでしょうか。

次はベンチマークです。速度計測のために最大流問題をたくさん生成するの必要があります。 たとえばグラフの形状だと、頂点数をNとして辺の数がO(N), O(N^(1.5)), O(N^2)くらいの完全ランダム、二部グラフあたりを用意すればよさそうです。一方容量はよくわかりません。ランダムからはじめますか。それとは別にいくつかのアルゴリズムに対する病的ケースが必要ですがこれもわかりません。 nyaasanはどういうグラフを作ったのか気になります。

半日の掃除を三日続けてやっと床が登場しました。学生時代の論文コレクションがそのまま残っていたという状況から復帰するのは大変でした。本が本棚に収納できないとか、そもそも本棚が足りないとか。座布団か埃かよくわからないものがあったりもしました。

いまだに本棚には物理の本がたくさんあります。大部分はまず読まない気がします。NielsenやPeskinはまだ面白いかもしれないけど、そもそもジャンル違いなキッテルとか、それから大学一年の数学、物理の教科書とかは正直必要ありません。誰かほしい人いますかね。

それからいらないものといえば英語の漫画とDVD。どちらも出張中に英語勉強として買ってきたものです。漫画はもう読まないと思います。タイトルはガンスリンガーガール1-3とMegaTokyo1,2,4。DVDはLOST Season 1とガンスリンガーガール。Herosとかも買いましたがこちらは見るはずです。

max flow問題をちゃんと復習することにしました。ちゃんと実装したことがなさ過ぎるので。

以前の議論 (1) (2) (3)を参考に論文を集めてみました。足りないのは問題の例です。あんまりにmaxflowそのままな問題だけではつまらないので材料がいくつかあると助かるのですが。topcoderで検索してみますか。


追記: 手持ちの教科書である藤重先生の工系数学講座をチラッと見たら、最速とされているDinitz(Dinic)のアルゴリズムがちゃんと載っていることを発見しました。気づいていませんでした。ついでにちょっと読んだところ、昔よりちゃんと読めることに感動。

飛行機ではずっと世界樹を登っていました。第三層中ボス撃破から20階到達まで。

第三層の中ボスの撃破に苦労しました。防御しないと一撃でやられるという状態でした。 そろそろパラディンが必要だろうということでクエストを消化しながら育成。前作も第三層のアリを倒すときに初めてパラディンを導入していました。パラディンがLv 20 くらいになったところで、フロントガード10を覚えて突入。数回の挑戦で倒しました。作戦は術師をツバメ返しとアナコンダで速攻始末。ブシドーとパラディンが事故死するのとパラディンのMPが足りなくなるのを運でカバーしました。

第三層ボスを続けて撃破。これは強いという評判を聞いていたものの、特に工夫することもなく中ボスとほぼ同じ設定で撃破できました。戦闘終盤でなんとかの抱擁だか接吻だかを食らって何回も全滅しましたが、回避策をわかってからはすぐ撃破しました。というか撃破できたのは偶然で、その後でその偶然が攻略法だったことに気づきました。

現在は第四層最下層。まだボスは見つけていません。パーティーは大体以下のとおりです。第二層突破したときに全員引退させたのでいくつか職業が変わっています。レベルは三層突破で32,今は37くらいです。

  • ブシドーは上段ツバメ。
  • ダークハンターはアナコンダとジエンド。縛りはどれがいいのかわかりません。
  • ドクトルマグスは毒斬と睡斬とエリアヒール。巫剣を使わせてみました。
  • カースメーカーは睡眠と博識と変化。
  • レンジャーはアイテムレンジャーのまま。アザーズステップは今作も健在。あと移動スキル。
  • ガンナーは基本セットと適当。そろそろ火力なくなってきました。
  • パラディンは後から育てたのでレベルがほかのキャラクタより10位低いです。フロントガード。

通常戦闘はアザーズステップ→睡眠で鉄壁。守備力が紙でも、攻撃されなければ問題はありません。ボス戦はカースメーカーをはずしてガンナーにしています。しかしブシドーの攻撃量に比べるとガンナーのは豆粒なので余り役に立っていない気もします。

一昨日から昨日の飛行機で帰国しました。今日は普通に出社です。

自宅のコンピュータはセキュリティアップデート祭りがなかなか終わりません。

上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。