Gesaan dan masa ia terpakai
Menugaskan masalah kepada pengaturcara ialah model yang berguna: masalah berada di sebelah kiri, pengaturcara di sebelah kanan, dan tepi bermaksud mereka berkongsi teg yang diperlukan. Setiap tepi boleh dipilih paling banyak sekali, dan objektifnya adalah untuk memaksimumkan tugasan. Gesaan temu duga awam PracHub memodelkan peruntukan kelayakan ini sebagai pemadanan bipartit dan meluaskannya kepada penjanaan tepi, penyelarasan teragih, dan perubahan penstriman; artikel ini menumpukan pada teras pengekodan mesin tunggal.
Perkara yang diuji oleh penemu duga
- Membezakan sebarang pemadanan tersedia (feasible), pemadanan maksimal (maximal), dan pemadanan kardinaliti maksimum (maximum-cardinality).
- Menggunakan laluan penambahan (augmenting paths) untuk menerangkan sebab pemadanan boleh berkembang sambil mengekalkan invarian.
- Menerangkan pelapisan BFS dan DFS untuk set laluan penambahan terpendek yang tak bersilang bucu (vertex-disjoint).
- Menyatakan masa kes terburuk O((V+E)√V), storan O(V+E), dan had algoritma tersebut.
Penjelasan untuk ditanya terlebih dahulu
- Adakah objektifnya kardinaliti maksimum, atau adakah terdapat pemberat, keutamaan, atau kekangan keadilan?
- Apakah batas pada n, m, dan E, dan adakah input tersebut sudah bersifat bipartit dan bebas pendua?
- Patutkah jawapan mengembalikan saiz sahaja, atau setiap pasangan dan setiap bucu yang tidak dipadankan?
- Adakah graf tersebut kelompok statik, atau adakah tepi akan disisipkan dan dipadamkan di bawah sasaran kependaman dalam talian?
Jawapan 30 saat
“Saya memodelkan dua kelas objek sebagai dua sisi graf bipartit dan kelayakan sebagai tepi. Saya mengekalkan pair_left dan pair_right. Setiap BFS bermula daripada setiap bucu kiri yang tidak dipadankan dan membina lapisan melalui tepi yang berselang-seli antara belum dipadankan dan sudah dipadankan. DFS kemudiannya mencari set laluan penambahan terpendek yang tak bersilang bucu dalam graf berlapis tersebut; menterbalikkan setiap laluan akan meningkatkan pemadanan. Apabila tiada lagi laluan penambahan yang tinggal, teorem laluan penambahan memberikan pemadanan maksimum. Kerumitan kes terburuk ialah O((V+E)√V); untuk graf kecil, pelaksanaan penambahan DFS yang lebih mudah mungkin sudah memadai.”
Penyelesaian langkah demi langkah
Langkah 1: Bina graf dan invarian
Simpan hanya tepi tersedia yang sebenar dalam senarai kejiranan. pair_left[u] dan pair_right[v] mesti menunjuk antara satu sama lain, atau kedua-duanya bernilai -1. Menterbalikkan satu laluan penambahan hanya mengubah tepinya, jadi tiada bucu yang menerima dua tepi dipadankan.
Langkah 2: Bina lapisan dengan BFS
Mula secara serentak daripada setiap bucu kiri yang tidak dipadankan. Rentasi tepi yang tidak dipadankan ke sisi kanan dan kemudian tepi yang dipadankan kembali ke bucu kiri, sambil merekodkan lapisan terpendek. Kekalkan lapisan terpendek yang boleh mencapai bucu kanan yang tidak dipadankan supaya DFS tidak meneroka laluan yang lebih panjang dalam fasa yang sama.
Langkah 3: Buat penambahan secara kelompok dengan DFS
Jalankan DFS daripada setiap bucu kiri yang tidak dipadankan. Mencapai bucu kanan yang tidak dipadankan dikira berjaya. Mencapai bucu kanan yang dipadankan akan berulang alik melalui bucu kiri padanannya hanya apabila lapisan meningkat sebanyak satu. Kursor kejiranan bagi setiap bucu kiri menghalang pengimbasan semula tepi yang gagal dalam fasa yang sama.
Langkah 4: Ketepatan dan penamatan
Laluan penambahan mempunyai satu lebih banyak tepi tidak dipadankan berbanding tepi dipadankan, jadi perbezaan simetri di sepanjang laluan tersebut meningkatkan kardinaliti sebanyak satu. Teorem laluan penambahan menyatakan bahawa pemadanan adalah maksimum tepat apabila tiada laluan penambahan wujud. Setiap fasa meningkatkan pemadanan, jadi gelung akan ditamatkan.
Langkah 5: Kerumitan dan pertukaran kompromi
Hopcroft–Karp mempunyai masa kes terburuk O((V+E)√V), ruang bantuan O(V), dan storan graf O(V+E). Pelaksanaan rujukan Princeton juga memperoleh liputan bucu minimum (minimum vertex cover); gesaan ini hanya memerlukan pemadanan. Untuk graf kecil, DFS bagi setiap bucu kiri adalah lebih pendek tetapi boleh mengambil O(VE) dalam kes terburuk. Objektif berpemberat memerlukan algoritma Hungarian atau min-cost flow sebagai ganti.
Pelaksanaan Python yang boleh dijalankan
from collections import deque
def hopcroft_karp(left_size, right_size, edges):
adj = [[] for _ in range(left_size)]
for left, right in edges:
adj[left].append(right)
pair_left = [-1] * left_size
pair_right = [-1] * right_size
distance = [-1] * left_size
def bfs():
queue = deque()
for left in range(left_size):
if pair_left[left] == -1:
distance[left] = 0
queue.append(left)
else:
distance[left] = -1
found = False
while queue:
left = queue.popleft()
for right in adj[left]:
mate = pair_right[right]
if mate == -1:
found = True
elif distance[mate] == -1:
distance[mate] = distance[left] + 1
queue.append(mate)
return found
def dfs(left, next_edge):
while next_edge[left] < len(adj[left]):
right = adj[left][next_edge[left]]
next_edge[left] += 1
mate = pair_right[right]
if mate == -1 or (
distance[mate] == distance[left] + 1
and dfs(mate, next_edge)
):
pair_left[left] = right
pair_right[right] = left
return True
distance[left] = -1
return False
matching = 0
while bfs():
next_edge = [0] * left_size
for left in range(left_size):
if pair_left[left] == -1 and dfs(left, next_edge):
matching += 1
return matching, pair_leftContoh jawapan berkualiti tinggi
“Saya terlebih dahulu mengesahkan bahawa objektifnya adalah kardinaliti maksimum, bukan pemadanan berpemberat, dan memodelkan kelayakan sebagai tepi bipartit. Dua tatasusunan pasangan mengekalkan invarian dua hala. BFS melapiskan laluan penambahan terpendek daripada semua bucu kiri yang tidak dipadankan; DFS menggunakan kursor tepi semasa untuk mencari sebanyak mungkin laluan tak bersilang bucu dalam graf lapisan tersebut, kemudian menterbalikkan tepinya. Apabila tiada laluan yang tinggal, teorem laluan penambahan membuktikan keoptimumannya. Pelaksanaan ini menggunakan masa O((V+E)√V) dan storan O(V+E); graf kecil boleh menggunakan DFS mudah, manakala objektif berpemberat memerlukan Hungarian atau min-cost flow.”
Kesilapan lazim
- Memanggil hasil tamak (greedy) sebagai maksimum; pemadanan maksimal boleh menjadi jauh lebih kecil daripada pemadanan maksimum.
- Menyimpan hanya satu sisi bagi setiap pasangan dan menghasilkan penghunian pendua selepas pembalikan.
- Menghentikan BFS pada sebarang laluan yang boleh dicapai, yang merosakkan pembentukan kelompok lapisan terpendek.
- Meninggalkan kursor tepi semasa dan mengimbas semula tepi yang gagal dalam fasa yang sama.
- Mendakwa O((V+E)√V) untuk pemadanan am, berpemberat, atau yang dikemas kini secara dinamik.
Soalan susulan dan respons mantap
Bagaimanakah anda menjana tepi kelayakan tanpa membandingkan kesemua n×m pasangan?
Bina indeks songsang mengikut teg. Masukkan objek sisi kanan ke dalam baldi (bucket), kemudian satukan dan nyahduplikasi baldi tersebut untuk setiap objek kiri. E masih boleh menjadi besar, jadi nyatakan E, kecondongan teg popular (hot-tag skew), dan had memori.
Mengapakah algoritma boleh berhenti apabila tiada laluan penambahan?
Setiap laluan penambahan meningkatkan saiz pemadanan sebanyak satu. Teorem laluan penambahan menyatakan bahawa pemadanan yang lebih besar wujud tepat apabila laluan penambahan wujud, jadi kegagalan untuk mencarinya membuktikan kardinaliti maksimum.
Apakah yang berubah untuk keutamaan berpemberat?
Hopcroft–Karp hanya mengoptimumkan bilangan tepi. Gunakan Hungarian atau min-cost max-flow, dan nyatakan semula kerumitan, had integer pemberat, serta pelan sandaran apabila tiada tugasan yang tersedia.
Bagaimanakah anda mengendalikan perubahan tepi yang berterusan (churn)?
Algoritma kelompok sesuai untuk pengiraan semula. Perkhidmatan dalam talian boleh mencari laluan penambahan secara setempat di sekitar bucu yang terjejas, tetapi mesti menyatakan kependaman, had penugasan semula, dan kontrak ketidakoptimuman sementara.