코드데이 랜파티의 출현

23일차: LAN 파티

Github Repo - 솔루션

오늘의 챌린지는 다소 실행적이고 다소 단순했습니다(적어도 Part 1은 그랬습니다).

1부:

삼각형 컴퓨터 중 하나가 t로 시작하는 트리오로 모든 연결을 수집하세요. 정말 간단합니다. 그렇다면 삼각형의 수를 세어보세요.

이를 달성하기 위해 노드 매핑을 생성합니다 -> connections(neighbors) 이므로 연결 개체는 다음과 유사하게 보입니다.

connections = {
    'kh': {'tc', 'dr'},
    'tc': {'kh', 'dr', 'zx'},
    'dr': {'kh', 'tc', 'xy'},
    'zx': {'tc'},
    'xy': {'dr', 'tz'},
    'tz': {'xy'}
}

트리오를 얻기 위해 연결을 반복하고 이웃을 검색할 수 있습니다. Python에서 연결의 노드는 키를 반복하고 값을 반환하지 않는다는 점을 기억하세요. 값에 액세스하려면 키(노드)를 사용하여 인덱스 연결[노드]을 통해 값에 액세스해야 합니다.

이웃 노드의 각 쌍에 대해 조합을 생성합니다. 예:

노드 = 'kh'이고 이웃 = {'tc', 'dr'}인 경우 쌍은 ('tc', 'dr')입니다. 두 이웃(neighbor1 및 neighbor2)도 서로 연결되어 있는지 확인합니다(연결[neighbor1]을 통해).

연결되어 있으면 노드, 이웃1, 이웃2 사이에 삼각형이 존재합니다.
중복을 피하기 위해 삼각형이 정렬되어 세트에 추가됩니다.

그런 다음
를 사용하여 t로 시작하는 노드가 있는 모든 연결을 찾습니다.

triangles_with_t = [triangle for triangle in triangles if any(
    node.startswith('t') for node in triangle)]

2부

2부에서는 상호 연결된 컴퓨터의 가장 큰 집합을 찾아야 합니다. 설정, 상호 연결된 노드와 같은 그래프로 작업할 때 우리는 파벌(clique)이라고 부릅니다.

Bron-Kerbosch 알고리즘을 사용하여 이를 분석해 보겠습니다. Bron-Kerbosch 알고리즘은 그래프에서 가장 큰 그룹(파벌이라고 함)을 찾는 데 사용됩니다. 이러한 맥락에서 그래프는 가장자리(연결)로 연결된 노드(예: 컴퓨터)의 모음일 뿐입니다. 알고리즘의 작동 방식과 이것이 퍼즐 해결과 어떻게 관련되는지는 다음과 같습니다.

파벌이란 무엇입니까?

파벌은 모든 노드가 다른 모든 노드와 직접 연결되는 노드 그룹입니다.

당신이 파티에 있다고 상상해 보세요. 모두가 그룹의 다른 사람들을 모두 알고 있습니다. 한 사람이라도 다른 사람을 모른다면 파벌이 아닙니다.

우리 퍼즐의 목표는 LAN 파티에서 상호 연결된 컴퓨터의 가장 큰 그룹을 찾는 것입니다. 이 그룹은 가장 큰 파벌입니다.

부분 집합이란 무엇입니까?

하위 집합은 더 큰 그룹의 작은 부분입니다. 예를 들면 다음과 같습니다.

가장 큰 파벌이 (A,B,C,D)라면 더 작은 하위 집합은 모두 연결되어 있는 A,B,CorB C D`가 될 수 있습니다. 하위 집합의 모든 노드가 연결되어 있기 때문에 이러한 하위 집합은 여전히 ​​파벌입니다.

Bron-Kerbosch 알고리즘을 사용하는 이유는 무엇입니까?

무차별 대입(가능한 모든 그룹을 시도)으로 가장 큰 파벌을 찾는 것은 입력이 큰 경우 느립니다. 예를 들어 컴퓨터가 3,000대라면 확인할 수 있는 그룹은 수십억 개가 됩니다.

Bron-Kerbosch 알고리즘은 다음을 통해 이 프로세스를 더 빠르게 만듭니다.

• 소규모 그룹(하위 집합)에서 시작하여 확장합니다.

• 그룹이 더 큰 집단으로 성장할 수 없을 때 조기 중단.

• 동일한 하위 집합에 대한 반복 확인을 방지합니다.

어떻게 작동하나요?

Bron-Kerbosch 알고리즘은 재귀적으로 작동합니다. 즉, 계속해서 자신을 호출하여 단계별로 파벌을 구축합니다. 작동 방식은 다음과 같습니다.

입력:
R: 파벌을 형성할 수 있는 노드 그룹(비어 있음).
P: 여전히 파벌에 가입할 수 있는 노드 목록(모든 노드로 시작).
X: 이미 확인한 노드 목록(비어 있는 상태로 시작).

단계:
P와 X가 모두 비어 있는 경우:
R은 최대 파벌입니다(더 많은 노드를 추가할 수 없습니다). 결과적으로 R을 저장합니다.

그렇지 않은 경우:
P에서 노드를 선택하여 R에 추가합니다.
업데이트 ? 그리고 ? 새로운 R에 연결된 노드만 포함합니다.

새로운 R,P 및
을 사용하여 알고리즘을 다시 호출합니다. X.

완료되면 노드를 P에서 X로 이동합니다(처리됨).

이 작업은 모든 노드가 처리될 때까지 반복되어 중복 검사 없이 모든 파벌이 발견되도록 합니다.

이것이 퍼즐을 어떻게 해결합니까?

입력: 다음과 같은 컴퓨터 연결 목록이 있다고 가정해 보겠습니다.

파이썬
A-B
A~C
BC
BD
CD

이러한 연결은 노드(컴퓨터)가 모서리(와이어)로 연결된 그래프를 나타냅니다.

목표: 각 컴퓨터가 다른 모든 컴퓨터에 직접 연결되어 있는 가장 큰 컴퓨터 그룹을 찾습니다.

과정:

알고리즘은 더 작은 그룹(하위 집합)에서 시작하여 이를 파벌로 성장시키려고 합니다.
그룹이 더 이상 성장할 수 없으면 중지됩니다(최대 파벌).

모든 파벌 중에서 가장 큰 파벌을 식별합니다.

출력:
예를 들어, 가장 큰 파벌은
입니다. {B,C,D}.

하위 집합은 어떻습니까?
퍼즐의 맥락에서:

파벌의 하위 집합(예: {B,C,D}의 {B,C})은 가장 큰 파벌보다 작기 때문에 흥미롭지 않습니다.

이 알고리즘은 처리된 노드(X)를 추적하여 하위 집합의 중복 검사를 방지합니다.

요약:

Clique: 모든 노드가 다른 모든 노드와 연결되어 있는 그룹

하위 집합: 큰 집단에서 가져온 작은 집단.

브론-커보쉬:
그래프의 모든 파벌을 찾습니다.
더 작은 하위 집합에 시간을 낭비하지 않고 가장 큰 파벌에 집중합니다.

퍼즐 풀이:
알고리즘을 사용하여 LAN 파티에서 상호 연결된 컴퓨터의 가장 큰 그룹을 찾으세요.

이 내용이 솔루션을 이해하고 Bron-Kerbosch 알고리즘에 대해 배우고 Python 구문에 대한 새로운 내용을 배우는 데 도움이 되었기를 바랍니다.

언제나 그렇듯이 저를 팔로우하거나 Twitter로 연락해 주세요.

결과는 퍼즐의 답인 최대 파벌입니다.

기타 유용한 Python 포인트:

Bron-Kerbosch 재귀 호출은 일부 수정된 속성 r | 노드, p 및 연결[노드].

파이썬에서

르 | node - 우리가 만들고 있는 파벌(r)의 현재 노드 집합의 모든 노드와 우리가 추가하는 다른 노드로 새 집합을 만듭니다.

p &connections[node] - 다음과 같은 노드만 포함하는 새 세트를 생성합니다.

• 두 p(여전히 파벌의 일부가 될 수 있는 노드 집합)에 있습니다.

• 연결노드에도 있습니다.

설명:
&는 집합의 교차 연산자입니다.
연결[노드]는 노드에 직접 연결된 노드의 집합입니다.

p & 연결[노드]는 “p와 연결[노드] 사이의 공통 노드를 찾는다”를 의미합니다.

위 내용은 코드데이 랜파티의 출현의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!