Как оптимизировать алгоритм этого дейкстры? - PullRequest
Новая
       36

Как оптимизировать алгоритм этого дейкстры?

0 голосов
/ 13 октября 2019

Я пытаюсь найти кратчайший путь между 2 точками, где ребра заданы «соседями» в виде списков, в файле json 

with open(r'C:\ads\game_board_2019.geojson') as f:
    adjacency = json.load(f)
adjacency = pd.DataFrame.from_dict(
    [i['properties'] for i in adjacency['features']], ).set_index('id', drop=True)

(кадр данных pandas выглядит следующим образом)

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

Ниже мой текущий алгоритм 

start = np.random.choice(adjacency.index)
end = np.random.choice(adjacency.index)

# vertices = np.array(adjacency.index, dtype='<U7')
vertices = list(adjacency.index)
n_vertices = len(vertices)
adjacency['label'] = np.inf
adjacency['path'] = [np.empty(0, dtype='<U7')]*n_vertices
adjacency.at[start, 'label'] = 0

for i in range(n_vertices):
    cur = adjacency.loc[vertices].label.idxmin()
    if (cur == end):
        break
    vertices.remove(cur)
    neighbourhood = adjacency.loc[cur].neighbours
    for j in np.intersect1d(neighbourhood, vertices):
        new_weight = adjacency.at[cur, 'label'] + 1
        if adjacency.at[j, 'label'] > new_weight:
            adjacency.at[j, 'label'] = new_weight  # weight == 1 for all edges
            adjacency.at[j, 'path'] = np.append(adjacency.at[cur, 'path'], cur)
path = adjacency.loc[end].path

Этот алгоритм работает, но слишком неэффективен (занимает около 15 секунд, чтобызапустить, когда желаемое количество времени составляет около 0,5 секунд). Есть предложения по улучшению?

1 Ответ

0 голосов
/ 13 октября 2019

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

...