Kemunculan Parti LAN Hari Kod

Hari 23: Parti LAN

Github Repo - Penyelesaian

Cabaran hari ini agak dijalankan, dan agak mudah (atau sekurang-kurangnya Bahagian 1 adalah).

Bahagian 1:

Kumpulkan semua sambungan dalam trio di mana mana-mana komputer segi tiga bermula dengan t. Semudah itu, kemudian hitung bilangan segi tiga.

Untuk mencapainya, kami membuat pemetaan nod -> connections (jiran) , jadi objek sambungan kami akan kelihatan seperti:

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

Untuk mendapatkan trio, kita boleh mengulangi sambungan dan mendapatkan semula jiran mereka - ingat dalam Python kerana nod dalam sambungan akan menggelung ke atas kekunci dan tidak mengembalikan nilai. Untuk mengakses nilai, kita perlu menggunakan kekunci (nod) untuk mengaksesnya melalui sambungan indeks[nod].

Untuk setiap pasangan nod jiran, ia menghasilkan gabungan. Contohnya:

Jika nod = 'kh' dan jiran = {'tc', 'dr'}, pasangannya ialah ('tc', 'dr'). Ia menyemak sama ada dua jiran (jiran1 dan jiran2) turut disambungkan antara satu sama lain (melalui sambungan[jiran1]).

Jika ia disambungkan, segitiga wujud antara nod, jiran1 dan jiran2.
Segitiga diisih dan ditambah pada set untuk mengelakkan pendua.

Kemudian cari semua sambungan di mana mana-mana nod bermula dengan t menggunakan

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

Bahagian 2

Pada bahagian 2 kita perlu mencari set terbesar komputer yang saling bersambung. Apabila bekerja dengan graf seperti persediaan, nod yang saling berkaitan kami panggil klik.

Mari kita pecahkan ini menggunakan algoritma Bron-Kerbosch. Algoritma Bron-Kerbosch digunakan untuk mencari kumpulan terbesar (dipanggil cliques) dalam graf. Dalam konteks ini, graf hanyalah koleksi nod (seperti komputer) yang disambungkan oleh tepi (sambungan). Begini cara algoritma berfungsi dan bagaimana ia berkaitan dengan menyelesaikan teka-teki kami.

Apa itu Clique?

Klik ialah sekumpulan nod di mana setiap nod disambungkan terus kepada setiap nod lain.

Bayangkan anda berada di sebuah parti, semua orang mengenali orang lain dalam kumpulan itu. Jika seorang pun tidak mengenali orang lain, itu bukan rumpun.

Dalam teka-teki kami, matlamatnya adalah untuk mencari kumpulan terbesar komputer yang saling bersambung di pesta LAN. Kumpulan ini adalah kumpulan terbesar.

Apakah subset?

Sebuah subset ialah sekeping yang lebih kecil daripada kumpulan yang lebih besar, contohnya:

Jika klik terbesar ialah (A,B,C,D), maka subset yang lebih kecil boleh menjadi A,B,CorB C D` di mana kesemuanya disambungkan. Subset ini masih berkelompok kerana semua nod dalam subset disambungkan.

Mengapa Menggunakan Algoritma Bron-Kerbosch?

Mencari kumpulan terbesar dengan kekerasan (mencuba setiap kumpulan yang mungkin) adalah lambat untuk input yang besar. Contohnya, jika terdapat 3,000 komputer, terdapat berbilion kumpulan yang mungkin untuk diperiksa.

Algoritma Bron-Kerbosch menjadikan proses ini lebih pantas dengan:

• Bermula dengan kumpulan yang lebih kecil (subset) dan mengembangkannya.

• Berhenti awal apabila kumpulan tidak boleh berkembang menjadi kumpulan yang lebih besar.

• Mengelakkan pemeriksaan berulang bagi subset yang sama.

Bagaimana ia berfungsi?

Algoritma Bron-Kerbosch berfungsi secara rekursif, bermakna ia terus memanggil dirinya untuk membina kumpulan langkah demi langkah. Begini cara ia berfungsi:

Input:
R: Sekumpulan nod yang mungkin membentuk klik (bermula kosong).
P: Senarai nod yang masih boleh menyertai klik (bermula dengan semua nod).
X: Senarai nod yang telah kami semak (bermula kosong).

Langkah:
Jika P dan X kedua-duanya kosong:
R ialah klik maksimum (anda tidak boleh menambah lebih banyak nod padanya). Simpan R sebagai hasilnya.

Jika tidak:
Pilih nod daripada P dan tambahkannya pada R.
Kemas kini ? dan ? untuk hanya memasukkan nod yang menyambungkan R.

baharu

Panggil algoritma sekali lagi dengan R,P dan
baharu X.

Apabila selesai, alihkan nod dari P ke X (ia diproses).

Ini berulang sehingga semua nod diproses, memastikan semua klik ditemui tanpa pemeriksaan berlebihan.

Bagaimana Ini Menyelesaikan Teka-teki?

Input: Katakan kami mempunyai senarai sambungan komputer, seperti:

ular sawa
A-B
A-C
B-C
B-D
C-D

Sambungan ini mewakili graf di mana nod (komputer) disambungkan dengan tepi (wayar).

Matlamat: Cari kumpulan komputer terbesar di mana setiap satu disambungkan terus ke setiap komputer lain.

Proses:

Algoritma bermula dengan kumpulan yang lebih kecil (subset) dan cuba mengembangkannya menjadi kumpulan.
Ia berhenti jika kumpulan tidak dapat berkembang lebih jauh (kumpulan maksimum).

Di antara semua kumpulan, ia mengenal pasti yang terbesar.

Output:
Sebagai contoh, rumpun terbesar ialah
{B,C,D}.

Bagaimana pula dengan Subset?
Dalam konteks teka-teki:

Subset bagi rumpun (cth. {B,C} daripada {B,C,D}) tidak menarik kerana ia lebih kecil daripada rumpun terbesar.

Algoritma mengelakkan pemeriksaan berlebihan subset dengan menjejaki nod yang diproses (X).

Rekap:

Klik: Kumpulan di mana setiap nod disambungkan kepada setiap nod lain.

Subset: Kumpulan yang lebih kecil diambil daripada kumpulan yang lebih besar.

Bron-Kerbosch:
Mencari semua klik dalam graf.
Fokus pada kumpulan terbesar tanpa membuang masa pada subset yang lebih kecil.

Penyelesaian Teka-teki:
Gunakan algoritma untuk mencari kumpulan terbesar komputer yang saling bersambung di pihak LAN.

Saya harap ini telah membantu anda memahami penyelesaiannya, mempelajari tentang algoritma Bron-Kerbosch dan mempelajari sesuatu yang baharu tentang sintaks Python.

Seperti biasa, sila hantar saya pengikut atau hubungi di Twitter.

Hasilnya ialah kumpulan terbesar, iaitu jawapan kepada teka-teki.

Mata Python lain yang berguna:

Panggilan rekursif Bron-Kerbosch, lulus dalam beberapa sifat diubah suai r | nod, p & sambungan[nod].

Dalam Python

r | nod - mencipta set baharu dengan semua nod daripada set nod semasa dalam klik yang kami bina (r), ditambah satu lagi nod yang kami tambah.

p & sambungan[nod] - Ini mencipta set baharu yang mengandungi hanya nod yang:

• Ada dalam kedua-dua p (set nod yang masih boleh menjadi sebahagian daripada rumpun).

• Ada juga dalam connectionsnode.

Penjelasan:
& ialah pengendali persimpangan untuk set.
connections[node] ialah set nod yang disambungkan terus ke nod.

p & sambungan[nod] bermaksud "cari nod sepunya antara p dan sambungan[nod]."

Atas ialah kandungan terperinci Kemunculan Parti LAN Hari Kod. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!