3

Java 組み込み API を使用して、Neo4J でステートフル AStar トラバーサルを実装しようとしています。つまり、グラフ内の特定のノードに到達したら、ブランチから収集されたコンテキスト情報を保持するオブジェクトを渡し、それ以降の関係を選択/剪定するために使用したいと考えています。PathExpander.expand()メソッドは、状態オブジェクトに含まれるトラバーサルのコンテキストを調べ、どのパスがどの順序で展開に適しているかを決定するという考え方です。これは、不正なマルチノード サブパス (実際にはターン制限) が返された最適パスの一部と見なされないようにするためです。GraphAlgoFactoryには、 InitialStateFactoryを介した初期状態の設定をサポートするダイクストラ生成ファクトリ メソッドがあるため、この手法はダイクストラ トラバーサルでうまく機能します。パラメータ:

dijkstra(PathExpander expander, InitialStateFactory stateFactory, String relationshipPropertyRepresentingCost) 
dijkstra(PathExpander expander, InitialStateFactory stateFactory, CostEvaluator<Double> costEvaluator)

偉大な。ただし、AStar トラバーサルで初期状態を設定するための対応するファクトリ メソッドが見つかりません。唯一のオプションは次のとおりです。

aStar(PathExpander expander, CostEvaluator<Double> lengthEvaluator, EstimateEvaluator<Double> estimateEvaluator) 
aStar(RelationshipExpander expander, CostEvaluator<Double> lengthEvaluator, EstimateEvaluator<Double> estimateEvaluator)

予想どおり、 PathFinderインスタンスでの私のfindSinglePath()呼び出しは、次のような早すぎる終了を迎えます。

java.lang.UnsupportedOperationException: Branch state disabled, pass in an initial state to enable it
    at org.neo4j.kernel.Traversal$1.getState(Traversal.java:100)[neo4j-kernel-1.8.jar:1.8]

では、AStar アルゴリズム ファクトリ メソッドのInitialStateFactoryパラメータを使用せずに「初期状態を渡す」にはどうすればよいでしょうか。ポスト 1.8 の API ドキュメントを見ると、(明白な) 答えもないようです。

あるいは、「不正な」マルチノード サブパスのセットが、findSinglePath()Dijkstra または AStar PathFinders で呼び出されて返された最適なパスに表示されないようにするためのより良い方法はありますか?

4

1 に答える 1

1

したがって、ダイクストラアルゴリズムはトラバーサルフレームワークを使用してNeo4jに実装されますが、A*はカスタム実装です。ただし、トラバーサルフレームワークの上にA*を実装するTraversalAStarクラスがあります。そのクラスには、 https：//github.com/neo4j/neo4j/pull/604がアドレス指定するものを介して、初期ブランチ状態を渡すことができるコンストラクターがありません。

GraphAlgoFactoryが提供するものと比較して、TraversalAStarの比較と最適化にはほとんど焦点が当てられていませんが、それがマージされると、必要な機能を提供するはずです。

于 2013-03-10T19:47:41.787 に答える