この記事について
Neo4jを使ったグラフアルゴリズムの実装を紹介してみようという計画「グラフアルゴリズム入門 - javaとNeo4jで学ぶ -」の一部です（どこまで続くか・・・）
サンプルコードはこちらにおいた。
旅行計画問合せ
「旅行計画問合せ（Trip Planning Query）」とは、例えば、ある地点からスタートして、名所を観光、レストランで食事、ホテルに到着というように、与えられたカテゴリ（名所・レストランなど。POI=Point of interestと呼ばれる）を持つような地点を経由して、できるだけ短い時間で、目的地に到達するようなルートを求める問合せのことを言う（参考文献[1]）。この問題は、一般的には、最適解を求める多項式時間で解けるアルゴリズムが存在しないため、準最適解を効率よく求める手法なども研究されている。
ここでは、双方向ダイクストラ法の簡単な応用として、参考文献[2]で述べられている「寄り道経路探索アルゴリズム」を単純化したものを紹介する。参考文献[2]では複数個の解を求めるものだが、ここでは1つのみ求めるように単純化している。以下「寄り道探索」と略す。旅行計画問合せで、与えられるカテゴリが1つだけの場合を考える。例えば、会社から家に変えるまでにラーメン屋に寄り道して帰りたいが、最も短時間で行けるルートは何か、というような問合せである。この場合は、双方向ダイクストラ法を応用して、最適解を求めるシンプルな方法がある。
スタートとゴールから同時に探索を開始し、ダイクストラ法による展開を実施する。もし、片側から求めるカテゴリノード（ラーメン屋）を見つけたら、それを片側の解候補として登録していく。同じノードに対して、両側からの解の候補が見つかったとき、それを最適解の候補として登録する。それを進めていき、双方向ダイクストラ探索のように、よりより候補が見つからないことが判断できたら探索を終了すればよい。
探索終了の判断には、同様に三角不等式を利用するがイメージを下図に示す。
双方向ダイクストラ法の場合は、両側からの現在の探索距離（プライオリティキューの先頭のコスト）が、現在得られている最短距離を上回れば、より良い解が見つからないから終了した。寄り道探索の場合、既にPOIが一つでも発見されている場合は、そのPOIまでの距離（片側の解候補の距離）の情報を利用してもよい。その場合の条件は、
- 全体の解候補の距離が、（スタート側から探索して到達した距離）＋（エンド側の解候補の距離の最小値）を下回る
- 全体の解候補の距離が、（エンド側から探索して到達した距離）＋（スタート側の解候補の距離の最小値）を下回る
となる。これは複数の解を求める場合に役立つ条件になる。
Neo4jによる実装
まず、返却される値は以下としよう。
- POIを通る最短経路（パス）
- POI（ノード）
返却値のクラスにPOIを追加した（すべてのサンプルで共有しているのは趣味悪いが適宜修正...）。
// result class for samples
public class Output {
public String out;
public Node node;
public Path path;
public double cost;
public Node poi;
}
ここでは、双方向ダイクストラ探索のプログラムを最小限修正する実装を紹介しよう。終了条件は双方向ダイクストラ探索と同様の条件としている。解を一つだけ求めるのであれば、その条件で問題はない。
まず、片側だけで最後まで到達してしまう場合は削除してよい（必ずPOIを見つける必要があるから）。
POIが見つかった場合については、双方向ダイクストラ法における両側からの探索をつなぐ部分のプログラムを、以下のように修正されればよい（スタート側）。
// If POI is found, check total path
if(cur_ni_f.nd.getProperty(category_property, "If property is missing, this value will be returned").equals(category)){
// find the node in the other side
final NodeInfo ni_t = nodes_t.get(cur_ni_f.nd);
// the node is in the other side map , it is poi, and total_cost can be lower
if(ni_t != null && ni_t.nd.getProperty(category_property, "If property is missing, this value will be returned").equals(category) && total_cost > cur_ni_f.cost + ni_t.cost) {
min_ni_f = cur_ni_f;
min_ni_t = ni_t;
poi = ni_t.nd;
total_cost = cur_ni_f.cost + ni_t.cost;
}
}
- 繋がっているかを調べるためには、到達したノードがPOIかどうかを調べ、そのPOIに到達している反対側の経路があるかどうかを調べれば良い。
- 最初のgetPropertyの第2引数は、ノードに該当するプロパティが存在しないときのデフォルト値である（第2引数がない場合、該当するプロパティが存在しない場合は例外扱いとなる）。グラフデータベースでは、関係データベースとは異なり、どのようなプロパティを持つかがノードによってバラバラだからこのような仕組みが用意されている。
- 反対側のキュー（プログラム上はmapのnodes_tを使っているが同等）にノードが登録されているかを調べ、そのノードがPOIであれば、経路が見つかったと判断できる。その経路のコストがこれまで見つかった最小値よりも小さければ、それを結果として登録すればよい。
他は大きな変更はない。細かいところはサンプルコード参照。
参考文献
[1]Li, Feifei et al.,"On Trip Planning Queries in Spatial Databases", SSTD(2005)
[2]大沢裕，藤野和久,"前処理を必要としない道路ネットワーク上での最短寄り道経路探索アルゴリズム", 電子情報通信学会論文誌D, Vol.J93-D, No.3, pp. 203–210 (2010)