3

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

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

1 1    
6 6    
2 3    
6 7    
3 9

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

3
  • 2
    Первое что приходит на ум это построить граф, отбросив все рёбра не удовлетворяющие ограничению. Веса рёбер - расстояния. Дальше ищем кратчайший путь. 29 окт 2018 в 6:19
  • С помощью чего в питоне это лучше реализовать ?
    – overfitt
    29 окт 2018 в 6:25
  • Я бы копал в сторону “networkx” и “scipy” / “sklearn” 29 окт 2018 в 6:29

3 ответа 3

4

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

Реализация с использованием модулей: 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]

График:

введите сюда описание изображения

4
  • Спасибо большое!
    – overfitt
    29 окт 2018 в 9:43
  • Не пропускает либу networkx, придется мне как-то это в ручную делать)
    – overfitt
    29 окт 2018 в 10:13
  • я пользуюсь дистрибутивом Anaconda - в нем установка: conda install networkx. Да и обычный pip install networkx должен нормально утсанавливать NetworkX 29 окт 2018 в 10:33
  • Я про компилятор сайта,на котором весит эта задача,он для решения задачи не все либы пропускает
    – overfitt
    29 окт 2018 в 10:43
1

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

2
  • Эта "разновидность" - BFS, поиск в ширину, на самом деле - основа волнового и др. Однако тут не показано, как учитывать веса рёбер (расстояния)
    – MBo
    29 окт 2018 в 7:58
  • Я предполагаю, что если по пути назад выбирать ближайшую точку - то все должно получиться. Надо проверить.
    – Mark
    29 окт 2018 в 8:11
0
  1. Построить граф связности точек с учетом ограничений по переходам.
  2. Использовать А*

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.