UTPC 2013 H - Asteroids2

• 問題
• AC

素朴なBellman-Fordを書いたらTLEしたので、ほかの提出にならって「始点がマイナスに更新されたら終了」という処理を入れてみたら余裕で間に合った。しかし、それで間に合うのはテストケースが甘いだけでは……という予感がしたので$2 \times 10^8$回のループが必要な最悪ケースを手元で作ってみたところ、案の定10sec以上掛かっている。隣接リストで辺を持つという手抜きをやめてちゃんと書いても2sec以内にならなくて困ったのだが、最終的には最短距離を保持するテーブルを(signed-byte 32)にするというささいな変更で（おそらくキャッシュに載って）1300msになった。(signed-byte 32)とfixnumの差で間に合わなくなるくらいに厳しい設定は初めて見た気がする。

以下、雑多なメモ。

Bellman-Ford法の最悪ケースについて

試行錯誤している最中に思ったのだが、Bellman-Fordでは１ループの間に

1. ある頂点$v_1$への最短距離を更新する
2. 辺$(v_1, v_2)$を処理して$v_2$への最短距離を更新する

のように複数ステップ進める場合があるので、$V$ステップ進むのに本当に$V$回のループが必要であることは少ない。でも、処理する辺の順番を入力順などに固定してしまうと、（上で述べたように）１ループで１つしか進めないような最悪ケースを踏まされたときにだいぶ重くなる。だから最初に辺をシャッフルしたほうが安全……っていう考え方はあるんだろうか。あるいは、そもそも辺の順番が本質的であるような問題設定ってありえる？ うまく並べるとならしで${\mathcal O}(\log V)$ステップ進める、みたいな。

負閉路の検出について

• Bellman-Ford法の$V$回の更新でわかるのは「グラフ中のどこかにある負閉路」であって、それがパス$s-t$に影響する負閉路かどうかはわからない。ただ、この問題のグラフは強連結なのでそれは考えなくてよい。
• $s-t$に影響する負閉路が存在することは、$\{ V\text{回目で更新された頂点} \} \cap \{ s \text{から到達可能な頂点} \} \cap \{ \text{辺を逆にしたグラフで}t\text{から到達可能な頂点} \} \neq\emptyset$であることと同値？ もっとスマートな考え方があるかも。→ $V$回更新したあと、さらに$V$回更新して$s$から$t$への最短距離が更新される $\Leftrightarrow$ $s-t$に影響する負閉路がある、なのでそちらのほうが簡単っぽい。 これはダメで、やはり上のチェックが必要。始点を$0$に、他を$\infty$に初期化して$\infty$でないものを処理していく方針であれば、$s$から到達可能な頂点しか処理しないので、$\{ V\text{回目で更新された頂点} \} \cap \{ \text{辺を逆にしたグラフで}t\text{から到達可能な頂点} \}$が空かどうかをチェックするだけで良い。あるいは、$V$回目の更新で負閉路上にある点を検出したら、すべて$-\infty$に置き換えるという方法もあるらしい。¹ なるほど……
• 先に書いたように、始点を$0$に、他を$\infty$に初期化して$\infty$でないものを処理していく方針だと、始点から到達できない負閉路は検出されない。グラフのどこかにある負閉路を検出したいだけなら全部0からスタートするのが良さそう。

LPのprimalとdualの関係

この問題はポテンシャル問題として定式化できるので、そのLP双対である最短経路問題が非有界(unbounded) $\Rightarrow$ もとの問題は実行不可能(infeasible)というロジックになっている。²

ただ、この問題設定において、ポテンシャル問題の目的関数は何を意味しているんだろう。→後に少し整理した。

参考:
http://tokoharu.github.io/tokoharupage/docs/formularization.pdf
http://www.me.titech.ac.jp/~mizu_lab/text.html

---

1. segment_turaiさんのツイートより。 ↩︎

2. 主問題と双対問題がともに実行不可能の場合もあるので、逆は成りたたない。一般に、主問題が実行不可能 $\Rightarrow$双対問題が非有界または実行不可能である。 ↩︎