3

我正在尝试使用 Java 嵌入式 API 在 Neo4J 中实现有状态的 AStar 遍历。也就是说，一旦我到达图中的某个节点，我想传递一个对象，该对象包含一些收集到分支的上下文信息，用于选择/修剪向前的关系。这个想法是该PathExpander.expand()方法将检查包含在状态对象中的遍历的上下文，并决定哪些路径有资格进行扩展，以及以何种顺序。我这样做是为了防止非法的多节点子路径（实际上是转弯限制）被视为返回的最佳路径的一部分。该技术适用于 Dijkstra 遍历，因为GraphAlgoFactory具有生成 dijkstra 的工厂方法，这些方法支持通过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)

可以预见的是，我对PathFinderfindSinglePath()实例的调用以不合时宜的方式结束：

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参数？查看 post 1.8 API 文档似乎也没有（明显的）答案。

或者，是否有更好的方法来确保一组“非法”多节点子路径永远不会出现在从findSinglePath()Dijkstra 或 AStar PathFinder 调用返回的最佳路径中？

4

1 回答 1

1

因此，Dijkstra 算法是在 Neo4j 中使用遍历框架实现的，而 A* 是自定义实现。然而，有一个 TraversalAStar 类在遍历框架之上实现了 A*。该类没有构造函数让您通过https://github.com/neo4j/neo4j/pull/604解决的问题进入初始分支状态。

与 GraphAlgoFactory 提供的相比，很少有人关注比较和优化 TraversalAStar，但它应该提供您所追求的功能......一旦它被合并。

于 2013-03-10T19:47:41.787 回答