Статьи

Поиск пути с помощью неуправляемых расширений Neo4j

Октябрь 10, 2018

В Расширении Neo4j я показал вам, как создать неуправляемое расширение для разогрева кеша узлов и отношений. Давайте попробуем сделать что-нибудь более интересное, например, разоблачить алгоритм поиска A * (A Star) через REST API. График, который мы создали ранее, выглядит так:

Я создал сетку узлов 5 на 5 со свойствами x и y и связями между ними «next_to» со случайным временным свойством. Свойства x и y узла говорят нам, где вдоль сетки находится этот узел, а свойство time между двумя смежными узлами говорит нам, сколько времени требуется для перемещения по соединяющему их пути. A * находит путь с наименьшей стоимостью между начальным узлом и конечной точкой.

A * должен знать: начальный и конечный узлы, какой-то способ оценить расстояние до конечного узла и стоимость обхода отношений. С этой информацией A * перемещается по графику по пути с наименьшей известной эвристической стоимостью, которая является просто суммой стоимости пройденного в данный момент пути и оценки для конечного узла.

Посмотрите видео ниже для наглядной демонстрации алгоритма A * в действии.

Чтобы сделать это в Neo4j, мы добавили бы метод в файл MyService.java, который мы создали ранее.

import org.neo4j.graphalgo.*;
import org.neo4j.kernel.Traversal;

    @GET
    @Path("/astar/{from}/{to}")
    @Produces("application/json")
    public Response routeAStar(@PathParam("from") Long from, @PathParam("to") Long to, 
                               @Context GraphDatabaseService db) throws IOException {
       Node nodeA = db.getNodeById(from);
       Node nodeB = db.getNodeById(to);

       EstimateEvaluator<Double> estimateEvaluator = new EstimateEvaluator<Double>()
	        {
	            public Double getCost( final Node node, final Node goal )
	            {
	                double dx = (Double) node.getProperty( "x" ) - (Double) goal.getProperty( "x" );
	                double dy = (Double) node.getProperty( "y" ) - (Double) goal.getProperty( "y" );
	                double result = Math.sqrt( Math.pow( dx, 2 ) + Math.pow( dy, 2 ) );
	                return result;
	            }
	        };

       PathFinder<WeightedPath> astar = GraphAlgoFactory.aStar(
           Traversal.pathExpanderForAllTypes(),
           CommonEvaluators.doubleCostEvaluator( "time" ), estimateEvaluator );

       WeightedPath path = astar.findSinglePath( nodeA, nodeB );

       return Response.ok().entity( path.toString() ).build();
    }

Мы создали EstimateEvaluator , что в данном случае используется евклидово расстояние для его эвристики и свойства времени для фактической стоимости прохождения отношений. Мы используем GraphAlgoFactory и метод aStar, перебирая все типы отношений с помощью pathExpander .

Давайте попробуем перейти от узла 1 к узлу 12 в панели администратора REST:

Мы получаем путь от узла 1 до 2, от 7 до 12 с весом 8,0 (если вы попробуете это дома, ваши числа могут отличаться, поскольку ваш график будет генерироваться случайным образом).

get /example/service/astar/1/12
(1)--[next_to,1]-->(2)--[next_to,2]-->(7)--[next_to,12]-->(12) weight:8.0

Мне нравится компактное представление пути, но что, если я хочу увидеть больше, чем это? Например, я хочу вернуть хорошее JSON-представление времени, которое занимает путь, узлов и отношений в пути, и их соответствующих свойств? Я могу создать HashMap и добавить к нему нужные мне кусочки:

Map<String, Object> astarMap = new HashMap<String, Object>();
astarMap.put("time", path.weight());

List<Object> nodes = new ArrayList<Object>();
for ( Node node : path.nodes() )
    {
	 Map<String, Object> nodeMap = new HashMap<String, Object>();
        		 nodeMap.put("id", node.getId());
        		 nodeMap.put("x", node.getProperty("x"));
        		 nodeMap.put("y", node.getProperty("y"));
     nodes.add(nodeMap);
          }
astarMap.put("nodes", nodes);

List<Object> relationships = new ArrayList<Object>();
for ( Relationship relationship : path.relationships() )
    {
         		 Map<String, Object> relMap = new HashMap<String, Object>();
                  relMap.put("id", relationship.getId());
                  relMap.put("rel_type", relationship.getType().name());
                  relMap.put("start_node", relationship.getStartNode().getId());
                  relMap.put("end_node", relationship.getEndNode().getId());
                  relMap.put("time", relationship.getProperty("time"));
         relationships.add(relMap);
          }

astarMap.put("relationships", relationships);

ObjectMapper objectMapper = new ObjectMapper();
         return Response.ok().entity(objectMapper.writeValueAsString(astarMap)).build();

Когда я снова запускаю команду get, я теперь возвращаю:

{"time":8.0,
 "nodes":[{"id":1,"y":0.0,"x":0.0},
          {"id":2,"y":1.0,"x":0.0},
          {"id":7,"y":1.0,"x":1.0},
          {"id":12,"y":1.0,"x":2.0}],
 "relationships":[{"start_node":1,"id":1,"time":3.0,"rel_type":"next_to","end_node":2},      
                  {"start_node":2,"id":2,"time":4.0,"rel_type":"next_to","end_node":7},
                  {"start_node":7,"id":12,"time":1.0,"rel_type":"next_to","end_node":12}]
}

Что немного более многословно, но легче иметь дело. Если вы хотите узнать больше об A * и поиске путей, я рекомендую блог Амит Патель о программировании игр . Код как всегда доступен на github .

С неуправляемыми расширениями вы можете получить свой торт и съесть его тоже. Полная мощность и скорость встроенного Java API по сравнению с REST. Используйте это с умом и наслаждайтесь.

37
Share: