오프라인 환경에서 분산 된 메시지 브로드 캐스팅에 알고리즘이 필요함 (전화로)

Question

시스템은 전화 (음성 또는 텍스트)로 사전 등록 된 커뮤니티로 메시지를 신속하고 안정적이며 분산 방식으로 브로드 캐스트 할 수 있어야합니다. 메시지는 미리 정의 된 규칙 및 연락처 목록에 따라 구성원간에 전달됩니다.

준비 단계가 온라인 :

은 "방송"은 "메일 링리스트"

명 자신의 전화 번호 (및 보안 구)

로 등록하여 가입을 여는

1. 각 연락처를 얻을 다른 구성원의 2-4 숫자 목록 (보안 문구 포함).

브로드 캐스터는 그의 연락처 목록을 호출하여 메시지를 시작합니다. 브로드 캐스트 규칙은 간단합니다. 전화를 받고 (보안 문구가 들릴 때) 메시지를 청취하고 같은 방식으로 메시지를 사용자의 대화 상대 목록으로 전달할 수 있습니다.

내 질문입니다 -에 최적화하는 방법 (연락처 목록을 작성하는 방법을 의미) 회원에 연결하는 방법 : 퀵 (트리의 최소 수준)

을 메시지를 배포

1. 을
2. 각 목록에 4 개 이하의 연락처 (더 좋은 2 또는 3)
3. 일부 중복 수준 (회원이없는 경우 전체 분기를 자르지 않음).

Answer 1

간단한 대답으로 트리를 분기 한 다음 각 분기의 "잎"을 다른 분기의 모든 비 잎과 연결하도록하십시오.

자세한 설명을 제공해 드리겠습니다. 네가 15 명 있다고 가정 해보자.

이

{ 
    1: [2, 3], 
    2: [4, 5], 
    3: [6, 7], 
    4: [8, 9], 
    5: [10, 11], 
    6: [12, 13], 
    7: [14, 15], 

그런 다음이있다 8, 9, 10, 11 아래 잎 아래 잎이 3이다 12, 13, 14, 15. 그래서 지금 당신이 그들을 연결 : 다음과 같이 다음을 시작

8: [3, 6], 
    9: [7, 12], 
    10: [13, 14], 
    11: [15], 
    12: [2, 4], 
    13: [5, 8], 
    14: [9, 10], 
    15: [11] 
    } 

그래서 나무 아래에 2 개, 나무 아래에 3 개가 있습니다. 한쪽면에 아무 것도없는 경우 다른쪽에 연결되어 있습니다.

분기 요인을 늘리면 잎이있는 트리의 부분이 증가하므로 모든 것이 다중으로 연결되도록 할 수 있습니다. (또한 루트에서 모든 요소까지의 거리를 줄입니다.)