割り当て問題(ハンガリアン法)

割り当て問題を解きたかった。配属の数理(1) のようなもの。すでに Hungarian algorithm に 2 種類の Python 実装が参照されている。

まず bmc/munkres の参照元の Munkres’ Assignment Algorithm を実装した。アルゴリズムが少し改良されて step0 で正方形のマトリックスにしなくてもいいようになっている。ほぼ翻訳しただけ。

もうひとつは 5xtof-durr/makeSimple と同じアプローチ。https://www.cs.ucsb.edu/~suri/cs231/Matching.pdfhttp://www.cse.ust.hk/~golin/COMP572/Notes/Matching.pdf を参考にした。こっちはだいたい理解したつもり。

いきなり slacky で考えるのは難しかったから、2 次元の slack で考えてアルゴリズムを理解してから slacky で最適化した。

この実装のポイントは equality graph \(G=(V,E_l)\)(\(E_l = \{x, y \mid l(x) + l(y) = w(x, y)\}\))を作成するところにあると思う。\(slack[x][y] = 0\) の場合に \(x\) と \(y\) は隣接(マッチング)しているという意味で slack は \(G\) の隣接行列とみなせる。そのため (slacky, y) の min をとっている部分は slack が 0 の場合には隣接ノード \(y \in N(S)-T\) を取得することでもある。

5xtof-durr/makeSimple の実装では slack に parent も含めることでさらにマッチングの増大にも利用している。この部分は The Dynamic Hungarian Algorithm for the Assignment Problem with Changing Costs の Figure 2 (b) を手で書くことによって理解できた。

solve() メソッドで \(X\) をイテレートしているように、ひとつずつ仮マッチングを行うのもポイント。

  1. 未マッチの \(x\) をルートとする
  2. \(x\) に関する最小の slacky と \(y \not\in T\) を取得する。\(\not\in T\) はルートからの増加パスに含まれないことを意味する。最小の slacky が 0 なら、\(y\) は \(G\) における \(x\) の隣接ノードである
  3. そうでなければ、最小の slacky で slacky を減算することで \(G\) を更新し、\(y\) は \(G\) における \(x\) の隣接ノードとなる
  4. もし \(y\) が未マッチなら、ルートから \(y\) は \(G\) における増加パスだからマッチングを増大でき終了
  5. そうでなければ、\(y\) のマッチ済みの \(x’\) を \(x\) として 2 に戻る

という流れ。

5xtof-durr/makeSimple の実装はアルゴリズムを理解していくにつれて、すごく注意深くて巧妙だということがわかっていった。すごい。

納得いく出来ではないけど…


Deriving Precedence Climbing

Deriving precedence climbing で式の評価を行う。文法を機械的に変換して疑似コードを導く。Advanced Calculator を少し簡単にして

    Pi        Pi number
    sqrt()    Square root
1   ()        Brackets
2   !         Factorial
3   -         Unary minus
4   ^         Exponent
5   mod       Modulus divide
6   *         Multiply (left-to-right precedence)
7   +         Add (left-to-right precedence)

で考える。単項マイナスの方が累乗より優先度が高いから 2^-32^(-3) となる。-3^2(-3)^2 となる。また階乗の方が単項マイナスより優先度が高いから -3!-(3!) となる。

まずこの文法をそのまま書く。

S  --> E0 end
E0 --> E1 | E0 "+" E1
E1 --> E2 | E1 "*" E2
E2 --> E3 | E2 "mod" E3
E3 --> E4 | E4 "^" E3
E4 --> E5 | "-" E5
E5 --> E6 | E6 "!"
E6 --> P
P  --> "Pi" | "sqrt(" E0 ")" | "(" E0 ")" | v

たとえば E0

  • + を含まない場合は E1
  • + を含む場合は E0 "+" E1

に相当する。+ が複数ある場合は E0 に代入して E0 "+" E1 = (E0 "+" E1) "+" E1 となるから左結合をみたす。同様に累乗の ^E4 "^" E3 = E4 "^" (E4 "^" E3) となって右結合をみたす。

単項マイナスと階乗はそれぞれ連続しないと考える。

Read More


City Blocks Flyover

City Blocks Flyover のシンプルな解き方を思いついた。MathJax のテストをかねて。

\(X = \{x_0, …, x_n\}\)、\(Y = \{y_0, …, y_m\}\) として、\((x_0, y_0)\) から \((x_n, y_m)\) への線分が通るブロックを数える。

まず、何もない座標に \((x_0, y_0)\) と \((x_n, y_m)\) を対頂点とする長方形と線分を描く。この長方形をブロックをみなせば線分が通るブロックは 1 個。

次に \(y = y_1\) な直線を引くと元のブロックは上下に分割されて線分の通るブロックは 1 つ増える。同様に \(j = m-1\) まで \(y = y_j\) な直線を引くごとにブロックは上下に分割され、線分の通るブロックは 1 つ増える。

\(X\) についても同様に直線を引いていく。次の場合がある。

  1. すでに引いた \(y = y_j\) な直線と線分との交点の左右を通る場合
  2. 交点を通る場合

図を書いてみると明らかで 1 の場合は、すでに線分の通っているブロックを左右に分割し線分の通るブロックは 1 つ増える。2 の場合は線分の通っているブロックに影響を及ぼさない。

というのをもう少し整理してコードにする。



autopep8 はじめました

gofmt を使い出して、今までいかに無駄にコーディングスタイルに気をつかってきたか思い知った。コーディングスタイルはプログラムに欠かせないけど、それに気をつかうのは人の仕事じゃなかった。PEP 8 に違反しないように注意してスペースバーを叩き、注意のもれたところは Flycheck に怒られて手で直していたなんて、なんて無駄な作業だったんだろう。

だから Python で書くときには autopep8(と py-autopep8.el)を使っていく。むしろあらゆる言語で自動整形ツールを使いたい。ツールの整形結果が好みに合わないこともあるけど、そういうのは些細な問題なんだと思う。そういうのを気にしてコーディングスタイルに気をつかいながらプログラミングするより、ツールに慣れてみようと思った。


Go と Python の式の評価順

Go

Order of evaluation から。

関数内では、式のオペランド・代入・return 文・すべての関数呼び出し・メソッド呼び出し・(チャネルの)通信演算(communication operations)は字句の左から右の順に評価される。

たとえば

y[f()], ok = g(h(), i()+x[j()], <-c), k()

では f()h()i()j()<-cg()k() の順に関数呼び出しと通信が行われる。でも x の評価とインデクシング、および y の評価と比べての順序は決められていない。

a := 1
f := func() int { a++; return a }
x := []int{a, f()}
m := map[int]int{a: 1, a: 2}
n := map[int]int{a: f()}

という例では

  • x[1, 2] または [2, 2] となる。af() の評価順は不定
  • m{2: 1} または {2: 2} となる。map の代入の評価順は不定
  • n{2: 3} または {3: 3} となる。キーと値の評価順は不定

らしい。http://play.golang.org/p/F_E-lfJIOR では全部後者になった。

Read More


Python と Go の多重代入

7.2. Assignment statements から

x = [0, 1]
i = 0
i, x[i] = 1, 2
print(x)

[0, 2] がプリントされる。[2, 1] がプリントされると思っていた。a, b = b, a のように値を交換するときには左辺と右辺が同時に評価されると思っていたから。

そうではなくて多重代入の場合は、まず右辺でタプルを生成した後で左辺の左から順に代入していると考えるといいのかも。

  1. i, x[i] = 1, 2
  2. i, x[i] = (1, 2)
  3. i = (1, 2)[0]
  4. x[i] = (1, 2)[1]

というふうに。これなら値の交換のときも

  1. a, b = b, a
  2. a, b = (b, a)
  3. a = (b, a)[0]
  4. b = (b, a)[1]

で矛盾しない。

>>> x = [1, 2, 3]
>>> x[0], x[x[0]] = x[1], x[0]
>>> x
[2, 2, 1]

のように右辺で x の要素を参照するような場合もこの解釈でいける。

Go では逆に左辺と右辺が同時に評価されるような結果になった。


Assignments で規定されていた。左辺のインデックス式とポインタの間接参照、および右辺の式がすべて評価された後で、左から右に順に代入される。


1 2 3 4 5