Найти минимальное расстояние между точками

#python #python_3x #алгоритм #графы

Нам нужно перейти из одной точки на плоскости в другую.
Но у нас есть ограничение на расстояние перехода за 1 раз

Также у нас даны координаты еще нескольких точек
Например:

1 1    
6 6    
2 3    
6 7    
3 9


Если сразу напрямую перейти нельзя(из-за огран), то придется переходить через другие
точки.Как найти минимальное расстояние?
    

Ответы

Ответ 1

Идея: строим граф, отбросив все рёбра не удовлетворяющие ограничению. Веса рёбер
- расстояния. Дальше ищем кратчайший путь.

Реализация с использованием модулей: Pandas, SciPy, NetworkX:

import pandas as pd
import networkx as nx
from scipy.spatial.distance import cdist, pdist, squareform
import matplotlib.pyplot as plt

# maximum allowed distance
max_dist = 5

# reading points coordinates CSV -> Pandas.DataFrame
df = pd.read_csv(r'c:/temp/data.csv', header=None, names=['x','y'])

# adjacency matrix of distances
adj_mx = squareform(pdist(df))
adj_mx[adj_mx > max_dist] = 0

# building a graph from the adjacency matrix
G = nx.from_numpy_matrix(adj_mx)

source = 0  # index of the source point
target = 3  # index of the target point

path = nx.shortest_path(G, source=source, target=target, weight='weight')
print(f'the shortest path between [{source}] and [{target}]: {path}')


#### drawing the graph
# node's positions
pos = nx.spring_layout(G)
edge_labels = {k:f'{v:.3}' for k,v in nx.get_edge_attributes(G, 'weight').items()}

nx.draw_networkx(G, pos, node_size=700)
nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels)

plt.show()


Вывод на печать:

the shortest path between [0] and [3]: [0, 2, 1, 3]


График:


Ответ 2

Построить граф связности точек с учетом ограничений по переходам.
Использовать А*


Ответ 3

Возможно вам поможет волновой алгоритм.
- посетите все возможные точки от начальной, отметьте их как "шаг 1"
- посетите все непосещенные точки, доступные из точек "шаг 1" и отметьте их как "шаг 2"
- повторяйте шаги, пока не посетите нужную вам точку
- когда дойдете до нужной точки - восстановите путь назад до исходной находя ближайшую
точку предыдущего шага