diff options
Diffstat (limited to '_site/blog/neo4j-a-star-search/index.html')
| -rw-r--r-- | _site/blog/neo4j-a-star-search/index.html | 31 |
1 files changed, 15 insertions, 16 deletions
diff --git a/_site/blog/neo4j-a-star-search/index.html b/_site/blog/neo4j-a-star-search/index.html index 0d918c7..1fca4b6 100644 --- a/_site/blog/neo4j-a-star-search/index.html +++ b/_site/blog/neo4j-a-star-search/index.html @@ -46,24 +46,23 @@ <br> <div class="twocol justify"><p>Back in 2018, we used <a href="https://neo4j.com/" class="external" target="_blank" rel="noopener noreferrer">Neo4J</a> graph database to track the movement of marine vessels. We were interested in the shortest path a ship -could take through a network of about 13,000 route points. Algorithms based on -graph theory, such as A* search, provide optimal solutions to such problems. -In other words, the set of route points lends itself well to a model based on -graphs.</p> +could take through a network of about 13,000 route points. Graph theoretic +algorithms provide optimal solutions to such problems, and the set of route +points lends itself well to graph-based modelling.</p> <p>A graph is a finite set of vertices, and a subset of vertex pairs (edges). Edges can have weights. In the case of vessel tracking, the route points form -the vertices of a graph; the routes between them, the edges; and the distances -between them are the weights. For different reasons, people are interested in -minimizing (or maximizing) the weight of a path through a set of vertices. For -instance, we may want to find the shortest path between two ports.</p> - -<p>Given such a graph, an algorithm like Dijkstra’s search could compute the -shortest path between two vertices. In fact, this was the algorithm Neo4J -shipped with at the time. One drawback of Dijkstra’s algorithm is that it -computes all the shortest paths from the source to all other vertices before -terminating at the destination vertex. The exhaustive nature of this search -limited our search to about 4,000 route points.</p> +the vertices of a graph; the routes between them the edges; and the distances +between them the weights. For various reasons, people are interested in +minimizing (or maximizing) the weight of a path through a set of vertices, such +as the shortest path between two ports to predict a vessel’s arrival time.</p> + +<p>Given a graph, an algorithm like Dijkstra’s search could compute the shortest +path between two vertices. In fact, this was the algorithm Neo4J shipped with +at the time. One drawback of Dijkstra’s algorithm is that it computes all the +shortest paths from the source to all other vertices before terminating at the +destination vertex. The time complexity of this exhaustive search prevented our +database from scaling beyond 4,000 route points.</p> <p>The following enhancement to Dijkstra’s search, also known as the A* search, employs a heuristic to steer the search in the direction of the destination @@ -350,7 +349,7 @@ public class ShortestPathAStar extends Algorithm<ShortestPathAStar> { <p>The heuristic function is domain-specific. If chosen wisely, it can significantly speed up the search. In our case, we achieved a 300x speedup, enabling us to expand our search from 4,000 to 13,000 route points. The <a href="https://github.com/neo4j-contrib/neo4j-graph-algorithms/releases/tag/3.4.0.0" class="external" target="_blank" rel="noopener noreferrer">v3.4.0</a> of the -Neo4J graph algorithms shipped with the A* search algorithm.</p> +Neo4J graph algorithms shipped with our A* search algorithm.</p> </div> <p class="post-author right">by W. D. Sadeep Madurange</p> |