パーサジェネレータについて調べた
パーサジェネレータの位置づけ
少しだけパーサジェネレータについて書く。パーサジェネレータとはパーサを生成できるソフトウェアのことである。
そもそもパーサとはなんだったか確認しよう。
パーサ（＝構文解析器）
パーサとは 構文解析器 - Wikipedia である。
XMLを読み取るパーサの例としては Document Object Model - Wikipedia や Simple API for XML - Wikipedia。要はDOMやSaxである。Javaを書いたことがあればちょっとは使ったことがあるはず。最近はXMLからJavaに変換する時は Java Architecture for XML Binding - Wikipedia を使うかもしれない。
構造を持った入力テキストの処理をおこなうものはすべてパーサだと言える。
なぜテキストに構造を持たせなければいけないのか？それは データ記述言語 - Wikipedia に書かれている以下のような理由による：
データ記述言語は、以下の点に主眼を置いて作られた。
１．複雑なデータ構造をもつデータを格納する。
２．データの記述方法や個々のデータ要素へのアクセス方法の共通化をはかる。
３．データをテキスト形式で格納する。
ただのテキストファイルだと、日付や誰によって更新されたか、どの部分が列でどの部分が行か？わからない。そういったデータの格納の仕方を定めたXML, JSON, HTML, そしてCSVやTSVすべてデータ記述言語と言える。XMLがまどろっこしいのは別にプログラマーがマゾだからではなく、付与したい情報が多いからである。
パーサジェネレータの利点
パーサがデータ記述言語によって構造化されたデータを読み取れることはわかった。では、パーサジェネレータは何ができるのか？
パーサジェネレータは、なんとこのデータ記述言語のルールを記述するだけでパーサを作ってくれる。スゴイ！
次の記事でそれを実践していく：
パーサジェネレータの実装の種類
Wikipediaを見ると、以下のような手法があるようだ
AtCoder - AtCoder Beginner Contest 012 (バスと避けられない運命) を解いてみた
解法
Rubyによる解答 TLE
アルゴリズムは正しそうですが11個のテストケースでTLEしてしまいました。
Submission #1725365 - AtCoder Beginner Contest 012 | AtCoder
D言語による解答 AC!
しかしそんなことでは諦めない。もちろん俺らは抵抗するで？拳で*1
Submission #1728053 - AtCoder Beginner Contest 012 | AtCoder
AOJ - ALDS1_12_B (ダイクストラ法) を解いてみた
AOJ - ALDS1_12は、重み付きのグラフアルゴリズムです。
最短経路 ダイクストラ法 | アルゴリズムとデータ構造 | Aizu Online Judge
この問題が解けるとAtCoderの以下の問題も解けます
問題設定
最短経路問題というのは、２つのノード間を結ぶ経路の中で重みが最小の経路を求める最適化問題のことらしい。
詳しいところはWikipediaをよめばよろし → 最短経路問題 - Wikipedia
一筆書きは求められていません。一度訪問したノードからは再出発できます。
最短経路問題の分類とアルゴリズムの使いどころ
今回はWikipediaの記述が役に立っています。最短経路問題は条件ごとに複数のアルゴリズムが適用されるみたいです。
Wikipediaの記述を整理すると…
[最短経路問題] │ ├── [ 2頂点対最短経路問題 ] (単一始点と同じロジックで対応できる) │ ├── [ 単一始点最短経路問題（SSSP） ] │ ├── [ 辺の重みなし有向グラフ ] → 幅優先探索 │ ├── [ 辺の重みが非負値の有向グラフ ] → ダイクストラ法 │ └── [ 辺の重みが任意の実数の有向グラフ ] → ベルマン-フォード法 │ └── [ 全点対最短経路問題 ] └── ワーシャル-フロイド法
チラチラ数学の論文っぽい参照が散見されますが、競プロのために論文は読まんでいいはず…。とにもかくにも、最短経路を求めるときに辺の重みがマイナスじゃなけりゃダイクストラ法を使えばいいのです。あと、もう一つダイクストラ法には制約があって、有向グラフ（辺が一方通行）のものしか適用できないようです。
AOJの問題の注意
アルゴリズム
疑似コード
Wikipediaの疑似コードを見ると、ソースの内容が前回のプリム法と似ていることに気付くかもしれません。プリム法ではノードの距離の比較の際、隣接行列の値と現在の距離だけを比較していましたが、ダイクストラ法は隣接行列の値と現在もっているノードの距離と現在の距離を比較します。
再びヨークカレッジ ペンシルバニア校/York College of Pennsylvaniaのレジェメを見る。
Lecture 22: Single Source Shortest Paths - Dijkstra's Algorithm
DIJKSTRA(G,w,s) INITIALIZE-SINGLE-SOURCE(G,s) S = ∅ Q = G.V while Q ≠ ∅ u = EXTRACT-MIN(Q) S = S ∪ {u} for each vertex v ∈ G.Adj[u] RELAX(u,v,w) # ↑ ここの関数は単に分割されとるだけ # 一番下のRELAX関数をここにコピペするとプリム法とほぼ同じ INITIALIZE-SINGLE-SOURCE(G,s) for each vertex v ∈ G.V v.d = ∞ v.pi = NIL s.d = 0 RELAX(u,v,w) if v.d > u.d + w(u,v) v.d = u.d + w(u,v) v.pi = u
*1:統一してくれ…
