Оптимизация сетевых соединений с помощью Python

Question

У меня следующая ситуация:

(1) У меня большая сетка. По некоторым условиям я хочу дополнительно наблюдать конкретные точки / ячейки в этой сетке. Каждая ячейка имеет ID и координаты X, Y отдельно. Итак, в этом случае давайте рассмотрим только одну ячейку - помеченную буквой C на изображении, которая расположена на краю сетки. По какой-то формуле я могу получить все соседние ячейки первого порядка (отмечены 1 на изображении) и второго порядка (отмечены 2 на изображении).

(2) При дополнительном условии я идентифицирую некоторые ячейки в соседних ячейках и отмечен оранжевым на втором изображении. Что я хочу сделать, это соединить все оранжевые ячейки друг с другом, оптимизируя расстояния и принимая во внимание только min() расстояния. Моей первой попыткой было наблюдать клетки только путем вычисления расстояний до клеток более низкого порядка. Поэтому, когда я смотрю на ячейки соседних ячеек 2, я смотрю только на ячейки 1. Решение связей представлено на рисунке 2, но оно не является оптимальным, поскольку идеальное решение будет сравнивать расстояния всех ячеек, а не только ячеек нижнего соседнего порядка. Делая это, я получаю ситуацию, представленную на рисунке 3. И проблема в том, что ячейки, конечно, не связаны с центром. Что делать?

Текущий код:

CO - список центральных точек.

data - все идентификаторы со значениями X, Y

CO_list = CO['ID'].tolist()

neighbor100 = []
for p in IskanjeCO_list:
    d = get_neighbors100k2(p, len(data)) #function that finds the ID's of neighbours of the first order
    neighbor100.append(d)

neighbor200 = []
for p in IskanjeCO_list:
    d = get_neighbors200k2(p, len(data)) #function that finds the ID's of neighbours of the second order
    neighbor200.append(d)

flat100 = []
for i in neighbor100:
  for j in i:
    flat100.append(j)

flat200 = []
for i in neighbor200:
  for j in i:
    flat200.append(j)

neighbors100 = flat100
neighbors200 = flat200

data_sosedi100 = data.iloc[flat100,].reset_index(drop=True)
data_sosedi200 = data.iloc[flat200,].reset_index(drop=True)

dist200 = []

for b in flat200:
    d = ((pd.DataFrame((data_sosedi100['X']* - data.iloc[b,]['X'])**2
         + (data_sosedi100['Y'] - data.iloc[b,]['Y'])**2 )**0.5)).sum(1)
    dist200.append(d.min())

data_sosedi200['dist'] = dist200

data_sosedi200['id'] = None
for e in CO_list:
    data_sosedi200.loc[data_sosedi200['FID_2'].isin((get_neighbors200k2(e, len(data)))),'id'] = e

Есть ли у вас какие-либо предложения по дальнейшей оптимизации? Я надеюсь, что я представил все изображение. При необходимости уточню дальше. Если вы видите часть кода, где я смогу оптимизировать этот цикл, я был бы очень благодарен!

Answer 1

Я определил точки вручную, чтобы работать с: импортировать NumPy как NP от оператора import itemgetter, attrgetter

nodes = [[-2,1], [-2,0], [-1,0], [0,0], [1,1], [2,1], [2,0], [1,2], [2,2]]
center = [0,0]

def find_neighbor(node):
    n=[]
    for i in range(-1,2):
        for j in range(-1,2):
            if not (i ==0 and j ==0):
                n.append([node[0]+i,node[1]+j])
    return [N for N in n if N in nodes]

def distance_to_center(node):
    return np.sqrt(node[0]**2+node[1]**2)

def distance_between_two_nodes(node1, node2):
    return np.sqrt((node1[0]-node2[0])**2+(node1[1]-node2[1])**2)

def next_node_closest_to_center(node):
    min = distance_to_center(node)
    next_node = node
    for n in find_neighbor(node):
        if distance_to_center(n) < min:
            min = distance_to_center(n)
            next_node = n
    return next_node, min

def get_path_to_center(node):
    node_path = [node]
    distance = 0.
    while node!= center:
        new_node = next_node_closest_to_center(node)[0]
        distance += distance_between_two_nodes(node, new_node)
        node_path.append(new_node)
        node=new_node

    return node_path,distance

def furthest_nodes_from_center(nodes):
    max = 0.
    for n in nodes:
        if get_path_to_center(n)[1] > max:
            furthest_nodes_pathwise = []
            max = get_path_to_center(n)[1]
            furthest_nodes_pathwise.append(n)
        elif get_path_to_center(n)[1] == max:
            furthest_nodes_pathwise.append(n)
    return furthest_nodes_pathwise

def farthest_node_from_center(nodes):
    max = 0.
    farthest_node = center
    for n in nodes:
        if distance_to_center(n) > max:
            max = distance_to_center(n)
            farthest_node = n
    return farthest_node

def closest_node_to_center(nodes):
    min = distance_to_center(farthest_node_from_center(nodes))
    for n in nodes:
        if distance_to_center(n) < min:
            min = distance_to_center(n)
            closest_node = n
    return closest_node

def closest_node_center_with_furthest_distance(node_selection):
    if len(node_selection) == 1:
        return node_selection[0]
    else:
        return closest_node_to_center(node_selection)


print(closest_node_center_with_furthest_distance(furthest_nodes_from_center(nodes)))

Выход:

[2, 0]
[Finished in 0.266s]

Запустив все узлы, я теперь могу определить, что самый дальний узел по траектории, но все еще ближе к центру, равен [2,0], а не [2,2]. Итак, мы начинаем оттуда. Чтобы найти другой с другой стороны, просто разбейте данные, как я сказал, на отрицательные значения x и положительные. если вы запустите его из списка только ячеек с отрицательным значением x, вы получите [-2,1]

Теперь, когда у вас есть 2 начальные ячейки [2,0] и [-2,1], я оставлю вас для выяснения алгоритма навигации по центру, проходящему через все ячейки, используя шаги в моих комментариях (теперь вы можете пропустить шаг 1, потому что это ответ опубликован)