가중치를 적용한 그래프의 모든 단순 경로에 대한 순회 비용을 업데이트하는 효율적인 병렬 알고리즘

Question

각 경로마다 ~ 10,000 개의 간단한 경로와 사이클이있는 비교적 작은 방향 그래프 (~ 10 노드)로 작업하고 있습니다. 나는 이러한 단순한 경로와 순환을 모두 가로 지르는 총 비용의 정렬 된 목록을 유지하려고합니다. 내 모서리에는 여러 가지 다른 가중치가 있지만 집계 함수는 모두에 대한 교환 가능/연관성 (예 : 합계 및 곱하기)입니다.

지금은 rethinkdb (nosql 데이터베이스)와 Python을 사용하고 있습니다. 모든 가능한 간단한 경로를 미리 계산하고, 해시 맵에 저장하고, 가중치가 업데이트 될 때마다 다시 계산합니다. 내 해시 맵은 일부가되는 모든 단순 경로와 사이클에 대해 지정된 에지 (가중치가 방금 업데이트 됨)를 가리 킵니다. 그런 다음 모든 것을 다시 계산합니다.

글쎄, 나는 이것이 매우 느리고 확장되지 않는 것을 발견했다! 나는 이것이 이라는 어려운 문제인이라는 것을 알고 있었지만 상대적으로 작은 그래프에서는 가능하다고 생각했습니다.

원래 접근 방식의 비효율은 일부가 서로 뭉친 경우에도 모든 단일 경로의 낭비적인 중복 계산에있는 것처럼 보였습니다. 예를 들어, A → B → C → D → E의 비용은 A → B → C와 C → D → E의 조합입니다. 그렇다면 왜 똑똑하게 계산하지 않으시겠습니까? 나는 이것을하는 방법을 생각해 냈다. 그리고 그것은 단지 하나의 작은 조각을 도와주는 것처럼 보이지 않았다. 그것은 나를 정말로 뒤로 물러 설 필요가 있다고 생각하게했다.

그래서 인터넷에 접속하여 검색을 한 다음이 유용한 문서를 발견했습니다 : https://blog.blazegraph.com/?p=628. 그것은 말한다 :

큰 그래프 안티 패턴이 "큰 그래프에 모든 것을 던져 다음 다른 문제를 우리에게 수평 확장을 준 같은 도구를 사용하여 . :지도/줄이고 키 - 값 저장"을한다

나는 이것이 정확히 내가하고있는 것 (잘못된 것)입니다.

GPU가이 기사에서 언급 한 메모리 대역폭 문제에 대한 올바른 해결책 인 것 같습니다. 단,이 문제를 병렬로 처리하는 방법을 잘 모르겠습니다.

질문 :

1. 방법 병렬로이 문제를 접근하는? 집회 - 적용 - 올바른 방향으로 흩어져 있습니까? 전에이 일이 어디 있었 니?

2. 병렬 처리없이 현재 접근 방식을 효과적으로 최적화하는 방법은 무엇입니까?

   1. 열거 내 그래프

   2. 의 모든 단순 경로와 사이클 가장자리와 가중치의 사전을 계속 : 참고로

   , 여기에 내 현재의 알고리즘의 스케치입니다. 예 :, ('A','B') 는이 B를 노드 간 A에서 가장자리

   edges_weights[('A','B')] # -> {'x': 1.3, 'y': 32, 'z': 0.231232} 
   

3. 각 에지에 관여하는 모든 간단한 경로 및 사이클 등의 사전 유지 인 경우도

   paths_containing_edges[('A','B')] 
   # -> 
   # [ 
   #  (('A','B'), ('B','C')), 
   #  (('A','B'), ('B','C'), ('C','D')), 
   #  (('A','B'), ('B','C'), ('C','A')), 
   #  ... 
   #  (('A','B'), ('B','C'), ('C','D'), ('D','A')) 
   # ] 
   

4. 을 사전 경로 및 비용 사전을 초기화하십시오.

   paths_costs = { 
        (('A','B'), ('B','C')): {'x': ..., 'y': ..., 'z': ...} 
   } 
   

5. 가장자리가 업데이트 될 때 :

   i. 해당 가중치를 업데이트하십시오. edges_weights

   ii. 이 가장자리를 포함하는 모든 간단한 경로를 조회하고 업데이트 :

fn = lambda p,q: p+q # the cost aggregation function   
weight_keys = ['x','y','z'] 
for path in paths_containing_edges[updated_edge]: 
    # path is a tuple of edge tuples, i.e. (('A','B'),('B','C'),('C','D')) 
    for w in weight_keys: 
    paths_costs[path][w] = reduce(fn,[edges_weights[e][w] for e in path]) 

은 분명히 중첩 루프 일어나고 조회의 많은이 있습니다 ...하지만 내가 다른 일을 할 수있는 방법을 볼 수 사투를 벌인거야.

Answer 1

귀하의 문제를 올바르게 이해했는지 확신 할 수 없습니다. 그래도 시도해 보겠습니다 :

노드가 n 개 이상있는 경우 노드 사이에 최대 (n * n-n)/2 에지가 있습니다.

n이 10이면 가장자리가 50 개 있다는 것을 의미합니다.

사이클을 시작하기 전에 노드 10 개에 대한 최대 경로 길이는 10입니다. 가장자리의 간단한 배열은 가장자리의 무게 정보에 액세스 할 수 있는지 확인해야합니다. 예를 들어 A-> B-> C-> D-> E-> G-> H-> I-> J

당신은 (A-> B) (B-> C 이제 질문은 : 무엇이 더 빠릅니까? - 하위 항목에 대한 솔루션을 찾기위한 검색 비용은 얼마입니까? (D-> E) (E-> F) (E-> G) (HI) 이 또는 단순히 배열 포인터 위에 추가하고 해당 포인터를 유지? 10.000 포인터를 유지하고 숫자를 합하면 정말 빨라야합니다. 특히 CPU가 잘 처리 할 수있는 숫자로 가중치를 유지하는 경우. 나는 그들이 int이고 길고 float이나 double이 아닌 것으로 가정하고 64 비트 CPU를 가지고도 아무런 문제가 없어야한다.

귀하의 작은 숫자를 감안할 때 계산을위한 CPU주기를 줄이는 C/Assembler와 같은 적절한 프로그래밍 언어를 사용하여 가장 효율적인 계산을 간단히 작성하려고합니다. 내 직감은 이것이 효율적인 알고리즘을 찾는 것보다 빠를 것이라는 점이다. (작은 수의 n에 대해서만 - 컷 오버 포인트가 어디 있을지 궁금하다.)