Code Day LAN パーティーの到来

23日目: LANパーティー

Github リポジトリ - ソリューション

今日のチャレンジはかなり実行的で、やや単純でした (少なくともパート 1 はそうでした)。

パート 1:

三角形のコンピューターのいずれかが t で始まるトリオ内のすべての接続を収集します。非常に簡単で、三角形の数を数えます。

これを実現するには、ノード -> のマッピングを作成します。 接続 (近隣) なので、接続オブジェクトは次のようになります:

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') になります。 2 つの近隣 (neighbor1 と neighbors2) も相互に接続されているかどうかを確認します (connections[neighbor1] 経由)。

それらが接続されている場合、ノード、neighbor1、neighbor2 の間に三角形が存在します。
重複を避けるために、三角形はソートされてセットに追加されます。

次に、
を使用して、いずれかのノードが t で始まるすべての接続を検索します。

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

パート 2

パート 2 では、相互接続されたコンピューターの最大セットを見つける必要があります。セットアップなどのグラフを操作する場合、相互接続されたノードをクリークと呼びます。

Bron-Kerbosch アルゴリズムを使用してこれを分解してみましょう。 Bron-Kerbosch アルゴリズムは、グラフ内の最大のグループ (クリークと呼ばれる) を見つけるために使用されます。この文脈では、グラフはエッジ (接続) で接続されたノード (コンピューターなど) の単なるコレクションです。アルゴリズムがどのように機能するのか、そしてそれがパズルの解決にどのように関係するのかを説明します。

クリークとは何ですか?

クリークは、すべてのノードが他のすべてのノードに直接接続されているノードのグループです。

あなたがパーティーに参加していると想像してください。グループの全員が他のメンバーのことを知っています。一人でも他の人を知らない場合、それは派閥ではありません。

私たちのパズルの目標は、LAN パーティーで相互接続されたコンピューターの最大のグループを見つけることです。このグループは最大の派閥です。

サブセットとは何ですか?

サブセットは、大きなグループの小さな部分です。次に例を示します。

最大のクリークが (A,B,C,D) である場合、より小さなサブセットはすべて接続された A,B,CorB C D` になる可能性があります。 サブセット内のすべてのノードが接続されているため、これらのサブセットは依然としてクリークです。

ブロン・ケルボッシュ アルゴリズムを使用する理由

力ずくで最大のクリークを見つける (考えられるすべてのグループを試す) と、入力が大きい場合は時間がかかります。たとえば、3,000 台のコンピューターがある場合、チェックする可能性のあるグループは数十億存在します。

Bron-Kerbosch アルゴリズムは、次の方法でこのプロセスを高速化します。

• 小さなグループ (サブセット) から始めて、それを拡大します。

• グループがより大きな派閥に成長できない場合は、早期に終了します。

• 同じサブセットの繰り返しチェックを回避します。

どのように機能するのでしょうか？

Bron-Kerbosch アルゴリズムは再帰的に動作します。つまり、段階的にクリークを構築するために自分自身を呼び出し続けます。仕組みは次のとおりです:

入力:
R: クリークを形成する可能性のあるノードのグループ (空から始まります)。
P: クリークにまだ参加できるノードのリスト (すべてのノードから始まります)。
X: すでにチェックしたノードのリスト (空から始まります)。

手順:
P と X が両方とも空の場合:
R は最大クリークです (これ以上ノードを追加することはできません)。結果として R を保存します。

それ以外の場合:
P からノードを選択し、それを R に追加します。
アップデート ？そして ？新しい R に接続されているノードのみを含めます。

新しい R、P、および
を使用してアルゴリズムを再度呼び出します。 ×.

完了したら、ノードを P から X に移動します (処理されます)。

これはすべてのノードが処理されるまで繰り返され、冗長なチェックを行わずにすべてのクリークが確実に見つかるようになります。

これでパズルはどのように解けるでしょうか?

入力: 次のようなコンピューター接続のリストがあるとします。

Python
A-B
A〜C
B-C
B-D
C-D

これらの接続は、ノード (コンピューター) がエッジ (ワイヤー) で接続されているグラフを表します。

目標: 各コンピュータが他のすべてのコンピュータに直接接続されている最大のコンピュータ グループを見つけます。

プロセス:

アルゴリズムは、より小さなグループ (サブセット) から開始し、それらをクリークに成長させようとします。
グループがこれ以上成長できない場合 (最大クリーク)、停止します。

すべてのクリークの中で、最大のクリークを特定します。

出力:
たとえば、最大のクリークは
です。 {B、C、D}.

サブセットについてはどうですか?
パズルのコンテキストでは:

クリークのサブセット (例: {B,C,D} の {B,C}) は、最大のクリークよりも小さいため、興味がありません。

このアルゴリズムは、処理されたノード (X) を追跡することで、サブセットの冗長なチェックを回避します。

要約:

クリーク: すべてのノードが他のすべてのノードに接続されているグループ。

サブセット: より大きなクリークから抽出された小さなグループ。

ブロン=カーボッシュ:
グラフ内のすべてのクリークを検索します。
小さなサブセットに時間を無駄にすることなく、最大のクリークに焦点を当てます。

パズルの解決策:
アルゴリズムを使用して、LAN パーティーで相互接続されたコンピューターの最大のグループを見つけます。

これが、解決策を理解し、Bron-Kerbosch アルゴリズムについて学び、Python 構文について新しいことを学ぶのに役立つことを願っています。

いつものように、お気軽にフォローしていただくか、Twitter にご連絡ください。

結果は最大のクリークであり、これがパズルの答えです。

その他の Python に関する役立つポイント:

Bron-Kerbosch 再帰呼び出しは、いくつかの変更されたプロパティを渡します。ノード、p、接続[ノード].

Python の場合

r |ノード - 構築しているクリーク (r) 内の現在のノード セットのすべてのノードと、追加している別のノードを含む新しいセットを作成します。

p &connections[node] - これにより、以下のノードのみを含む新しいセットが作成されます。

• 両方の p (クリークの一部である可能性があるノードのセット) にあります。

• はconnectionsnodeにもあります。

説明:
& は集合の交差演算子です。
connection[node] は、node に直接接続されているノードのセットです。

p &connections[node] は、「p とconnections[node] の間の共通ノードを見つける」ことを意味します。

以上がCode Day LAN パーティーの到来の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。