Удалить почти параллельный NetworkX кратчайший путь - PullRequest
Новая
       39

Удалить почти параллельный NetworkX кратчайший путь

1 голос
/ 13 января 2020

Я сгенерировал путь между местоположениями A и B с ограничением мест, которые я должен пройти, выбрасывая их или близко к ним, чтобы маршрут выглядел так: A -> c1 -> c2 - > B, даже если это не самый короткий путь.

Я использовал for path in nx.all_shortest_paths(UG, source=l1_node_id, target=l2_node_id,weight = 'wgt'):

, когда 'wgt' - это расстояние от края / скорости движения на этой дороге.

Я создал список списков, в котором каждый внутренний список является например, node_id: 

l_list = [
    [n11,n12,n13,n14....]
    [n21,n22,n23,n24....]
         ..
    ]

и на карте это выглядит так: (маркеры - это начало каждого маршрута, и я также покрасил их в разные цвета) enter image description here

Я хочу изменить его на один маршрут, но, как вы можете видеть, есть некоторые расщепления, такие как зеленый и красный, некоторые общие последовательности (которые я могу обработать), и вторая проблема - начало синего маршрута \ конец черного, который не имеет значения.

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

У меня есть отметки времени каждого маркера, но это просто говорит о том, что я был близко к этой области. (это места расположения сотовых антенн)

1 Ответ

0 голосов
/ 19 января 2020

Во-первых, вам нужно определить, что такое «почти параллельно», более кратко или более формально, вам нужно определить функцию подобия.

Выбор функции сходства / расстояния

Там Есть множество способов определить функцию подобия, вот один из них

Resample

Предполагая, что каждый узел n_i имеет координаты x и y (n_i_x,n_i_y). Вы можете пересчитать точки на оси x, чтобы новые точки отбирались по 1km.

Затем для каждых 2 маршрутов вы можете суммировать разницу в y ось. Используйте это расстояние для кластеризации маршрутов.

Другие идеи

Кластеризация

После того как вы определили функцию similarity, вы можете использовать алгоритм кластеризации на основе расстояния, я рекомендую использовать агломеративную кластеризацию sklearn .

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

...