Поиск пути/навигация с neo4j

Question

Я знаю, что, вероятно, меня ругают за это, но я надеюсь, что кто-то поможет мне указать мне в правильном направлении.

Я пытаюсь создать способ найти приложение, например, карты googles, но пометить маршруты для нескольких точек на карте.

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

Может ли кто-нибудь предлагать ресурсы на картах, статьях и т. Д., Чтобы помочь мне? Я пытался использовать Google для статей, но могу найти любые совпадения, поэтому я предполагаю, что использую неправильные термины, такие как «поиск пути» или «направления»

Спасибо!

Answer 1

Я бы start with this article. Чтобы задать более конкретный вопрос, вам понадобится модель данных и пример того, что вы пытаетесь сделать.

Но в целом используемый язык, вероятно, является «кратчайшим путем». Как правило, если вы пытаетесь найти путь от точки A до точки B, вы ищете «самый короткий путь», где «стоимость пути» минимальна. Иногда стоимость - это расстояние, а иногда и стоимость - время, но в любом случае вы обычно ищете кратчайший путь, а не только какой-либо путь.

Answer 2

Графические базы данных хорошо подходят для поиска путей, особенно с помощью shortestPath, как упомянуто FrobberOfBits.

Это работает хорошо, если у вас есть узлы, которые могут образовывать путь. Из того, что я понимаю в ваших комментариях, на самом деле вам нужно будет создавать эти узлы динамически сначала в зависимости от предпочтений вождения пользователя.

Кроме того, по-видимому, в настоящее время у вас нет модели данных для точки A до точки B?

Это, как я хотел бы продолжить, кратко:

Прецедент является точка А мой дом, и точка 2, где живут Neo4j Community смотритель, на карте было бы:

Все маленькие белые точки в маршруте от А до В могут быть узлами Neo4j.

Теперь вы говорите, что, например, для того, чтобы присоединиться к маршруту, есть удивительная девушка с приоритетом движения 50 км, поэтому текущий маршрут должен измениться.

Как и в приложении, не заставить пользователей выбрать промежуточную точку, вы должны создать его на лету.

Итак, мое быстрое решение состоит в том, чтобы получить точку на радиусе, который будет ближе всего к точке назначения начального маршрута.

Чтобы добиться этого, сначала вы будете нуждаться в начальный азимут от текущего положения девушки к месту назначения (здесь Дрезден)

Где LAT1 и lon1 являются положение девушки, и LAT2, lon2 положение Дрездена

Затем, учитывая этот исходный подшипник, вы можете рассчитать позицию, начиная с девушки в подшипнике bearing и 50 км расстояния, например

В PHP это будет выглядеть (проверено):

// Function that calculate new coordinates from point A 
// Given a bearing and a distance to point B 
function getAwayPosition($lat1, $lon1, $lat2, $lon2, $distance) 
{ 
    // Getting true course from point A to point B 
    $la1 = deg2rad($lat1); 
    $la2 = deg2rad($lat2); 
    $lo1 = deg2rad($lon1); 
    $lo2 = deg2rad($lon2); 

    $y = sin($la2-$la1)*cos($lo1); 
    $x = cos($lo1*sin($lo2))-sin($lo1)*cos($lo2)*cos($la2-$la1); 
    $course = fmod(rad2deg(atan2($y, $x)+360), 360); 

    // Getting the new lat/lon points from lat1/lon1 given the course and the distance 
    $bearing = deg2rad($course); //back to radians for the coordinates calculation 
    $laa = asin(sin($la1 * cos($distance/6371 + $la1 * cos($course)))); 
    $loo = $lo1 + atan2(sin($bearing) * sin($distance/6371) * cos($la1), cos($distance/6371) - sin($la1) * sin($laa)); 

    return array(
     'lat' => rad2deg($laa), 
     'lon' => rad2deg($loo), 
     'bearing' => $course 
    ); 
} 

NB: Существует также функция haversin в Cypher для вычисления расстояния земли, я не играл так много с ней, хотя

Таким образом, вы можете добавить узел, который будет представлять желаемую позицию для девушки, чтобы присоединиться к поездке.

До сих пор мы теперь имеем 3 хороших узлов для Neo4j:

Теперь я думаю, что это будет до вашей модели данных для остальной части процесса, если маршрут от А до В не создавайте уже узлы Neo4j в своей базе данных, вы можете построить его динамически, вычислив расстояние от всех точек с помощью API Карт Google и установите его как свойство отношения. Затем вы можете сделать Cypher shortestPath и уменьшить свойство отношения расстояния.

Если у вас уже есть узлы, представляющие несколько промежуточных точек исходного маршрута от A до B, вы можете использовать Neo4j Spatial и получить ближайшую точку от желаемой позиции девушки до промежуточных узлов маршрута и создать связь с расстоянием. И снова shortestPath за лучший сопоставленный маршрут.

Второе решение было бы лучше, потому что вы будете немедленно иметь график, чтобы играть с:

И простой Cypher запрос, если вы хотите, чтобы получить путь с наименьшими километров:

MATCH (a:Point {id:'A'}), (b:Point {id:'B'}) 
MATCH p=allShortestPaths((a)-[:NEXT_POINT]-(b)) 
RETURN p, reduce(totalKm = 0, x in relationships(p)| totalKm + x.kilometers) as distance 
ORDER BY distance ASC 

Существует также алгоритм Djikstra со свойствами затрат доступны с Neo4j REST API http://neo4j.com/docs/stable/rest-api-graph-algos.html

Некоторые ресурсы:

• https://software.intel.com/node/341473
• http://www.movable-type.co.uk/scripts/latlong.html
• http://williams.best.vwh.net/avform.htm

Так как заключение, если вы хотите использовать Neo4j для определения наилучшего маршрут, вам нужно помочь ему с некоторыми данными в базе данных ;-)

Answer 3

То, что вы, кажется, описываете, - это маршрут от А до Б через разные путевые точки (места людей), но с целью минимизировать общее расстояние, пройденное от А до Б. Путь в графе с этими характеристиками известен как Minimum Spanning Tree. Реально, тот факт, что люди могут путешествовать, чтобы встретить «главный маршрут», просто вводит дополнительные путевые точки, это не изменяет общую проблему или то, как это классически решено.

Ни Cypher, ни REST API не имеют функции для вычисления минимальных связующих деревьев и, к сожалению, просто собирают кратчайшие пути между отдельными узлами (например, используя алгоритм Дейкстры), а затем попытка создать путь из этих сегментов кратчайшего пути не будет оптимальной в общем случае.

Однако нетрудно реализовать Prim's algorithm через плагин сервера или неуправляемое расширение в Neo4j, и я бы порекомендовал вам изучить это.