Улучшение производительности BFS с помощью некоторого напоминания - PullRequest
Новая
       20

Улучшение производительности BFS с помощью некоторого напоминания

1 голос
/ 05 июня 2019

У меня есть проблема, я пытаюсь построить алгоритм, который будет находить расстояния от одной вершины до других в графе.

Допустим, на самом простом примере моя сеть выглядит следующим образом: 

network = [[0,1,2],[2,3,4],[4,5,6],[6,7]]

Я создал код BFS, который должен находить длину пути от указанного источника до вершин другого графа.

from itertools import chain
import numpy as np

n = 8
graph = {}

for i in range(0, n):
    graph[i] = []

for communes in communities2:
    for vertice in communes:
        work = communes.copy()
        work.remove(vertice)
        graph[vertice].append(work)

for k, v in graph.items():

    graph[k] = list(chain(*v))

def bsf3(graph, s):
    matrix = np.zeros([n,n])
    dist = {}
    visited = []
    queue = [s]
    dist[s] = 0
    visited.append(s)
    matrix[s][s] = 0

    while queue:

        v = queue.pop(0)
        for neighbour in graph[v]:

            if neighbour in visited:
                pass
            else:

                matrix[s][neighbour] = matrix[s][v] + 1


                queue.append(neighbour)
                visited.append(neighbour)



    return matrix

bsf3(graph,2)

Сначала я создаю график (словарь), а затем использую функцию для поиска расстояний.

Что меня беспокоит, так это то, что этот подход не работает с большими сетями (скажем, с 1000 человек).И я думаю о том, чтобы использовать какое-то напоминание (фактически, поэтому я сделал матрицу вместо списка).Идея состоит в том, что когда алгоритм вычисляет путь, скажем, от 0 до 3 (что он уже делает), он должен отслеживать другие маршруты таким образом, чтобы матрица [1] [3] = 1 и т. Д.

Таким образом, я бы использовал такую ​​функцию, как bsf3 (график, 1), она не будет вычислять все с нуля, но будет иметь доступ к некоторым значениям из матрицы.

Заранее спасибо!

1 Ответ

0 голосов
/ 05 июня 2019

Знание этого не полностью отвечает на ваш вопрос, но это еще один подход, который вы можете попробовать.

В сетях у вас будет таблица маршрутизации для каждого узла в вашей сети. Вы просто сохраняете список всех узлов в сети и в каком узле вы должны идти. Пример таблицы маршрутизации узла D 

A -> B
B -> B
C -> E
D -> D
E -> E

Вам нужно запустить BFS на каждом узле, чтобы построить всю таблицу маршрутизации, и это займет O(|V|*(|V|+|E|). Сложность пространства квадратична, но вы должны проверить все возможные пути.

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

...