Permintaan dan kapan ini berlaku
Menetapkan masalah ke pemrogram adalah model yang berguna: masalah berada di sebelah kiri, pemrogram di sebelah kanan, dan sebuah sisi berarti mereka memiliki tag yang diperlukan yang sama. Setiap sisi dapat dipilih paling banyak satu kali, dan tujuannya adalah memaksimalkan penugasan. Sebuah perintah wawancara PracHub publik memodelkan alokasi kelayakan ini sebagai pencocokan bipartit dan memperluasnya ke pembuatan sisi, koordinasi terdistribusi, dan perubahan streaming; artikel ini berfokus pada inti pengodean mesin tunggal.
Apa yang sedang diuji oleh pewawancara
- Membedakan pencocokan yang layak (feasible), maksimal (maximal), dan kardinalitas maksimum (maximum-cardinality).
- Menggunakan jalur augmentasi untuk menjelaskan mengapa pencocokan dapat bertambah sambil mempertahankan invarian.
- Menjelaskan pelapisan BFS dan DFS untuk himpunan jalur augmentasi terpendek yang saling lepas simpul (vertex-disjoint).
- Menyatakan waktu kasus terburuk O((V+E)√V), penyimpanan O(V+E), dan batasan algoritma.
Klarifikasi untuk ditanyakan terlebih dahulu
- Apakah tujuannya adalah kardinalitas maksimum, atau ada bobot, prioritas, atau batasan keadilan?
- Berapa batas untuk n, m, dan E, dan apakah input sudah bersifat bipartit serta bebas duplikat?
- Apakah jawabannya hanya perlu mengembalikan ukuran, atau setiap pasangan dan setiap simpul yang tidak cocok?
- Apakah graf berupa batch statis, atau sisi akan disisipkan dan dihapus di bawah target latensi online?
Jawaban 30 detik
“Saya memodelkan dua kelas objek sebagai dua sisi dari graf bipartit dan kelayakan sebagai sisi-sisinya. Saya mempertahankan pair_left dan pair_right. Setiap BFS dimulai dari setiap simpul kiri yang belum cocok dan membangun lapisan melalui pergantian sisi yang belum cocok dan yang sudah cocok. DFS kemudian menemukan himpunan jalur augmentasi terpendek yang saling lepas simpul pada graf berlapis tersebut; membalikkan setiap jalur akan meningkatkan pencocokan. Ketika tidak ada lagi jalur augmentasi yang tersisa, teorema jalur augmentasi memberikan pencocokan maksimum. Kompleksitas kasus terburuk adalah O((V+E)√V); untuk graf kecil, implementasi augmentasi DFS yang lebih sederhana mungkin sudah cukup.”
Solusi langkah demi langkah
Langkah 1: Bangun graf dan invarian
Simpan hanya sisi layak yang nyata dalam daftar ketetanggaan. pair_left[u] dan pair_right[v] harus saling menunjuk satu sama lain, atau keduanya bernilai -1. Membalikkan satu jalur augmentasi hanya mengubah sisi-sisinya, sehingga tidak ada simpul yang menerima dua sisi yang cocok.
Langkah 2: Bangun lapisan dengan BFS
Mulai secara bersamaan dari setiap simpul kiri yang belum cocok. Telusuri sisi yang belum cocok ke sisi kanan lalu sisi yang sudah cocok kembali ke simpul kiri, catat lapisan terpendeknya. Pertahankan lapisan terpendek yang dapat mencapai simpul kanan yang belum cocok agar DFS tidak menjelajahi jalur yang lebih panjang pada fase yang sama.
Langkah 3: Lakukan augmentasi secara batch dengan DFS
Jalankan DFS dari setiap simpul kiri yang belum cocok. Mencapai simpul kanan yang belum cocok berarti berhasil. Mencapai simpul kanan yang sudah cocok akan berulang melalui simpul kiri pasangannya hanya jika lapisannya bertambah satu. Kursor ketetanggaan per-simpul-kiri mencegah pemindaian ulang sisi yang gagal pada fase yang sama.
Langkah 4: Kebenaran dan penghentian
Jalur augmentasi memiliki satu sisi belum cocok lebih banyak daripada sisi yang sudah cocok, sehingga perbedaan simetris di sepanjang jalur tersebut meningkatkan kardinalitas sebanyak satu. Teorema jalur augmentasi menyatakan bahwa suatu pencocokan bernilai maksimum tepat ketika tidak ada jalur augmentasi yang ada. Setiap fase meningkatkan pencocokan, sehingga perulangan pasti berhenti.
Langkah 5: Kompleksitas dan kompromi
Hopcroft–Karp memiliki waktu kasus terburuk O((V+E)√V), ruang bantu O(V), dan penyimpanan graf O(V+E). Implementasi referensi Princeton juga menghasilkan minimum vertex cover; perintah ini hanya membutuhkan pencocokan. Untuk graf kecil, DFS per simpul kiri lebih pendek tetapi dapat membutuhkan waktu O(VE) dalam kasus terburuk. Tujuan berbobot memerlukan algoritma Hungarian atau min-cost flow sebagai gantinya.
Implementasi Python yang dapat dieksekusi
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 jawaban berkualitas tinggi
“Pertama-tama saya mengonfirmasi bahwa tujuannya adalah kardinalitas maksimum, bukan pencocokan berbobot, dan memodelkan kelayakan sebagai sisi bipartit. Dua larik pasangan mempertahankan invarian dua arah. BFS menyusun lapisan jalur augmentasi terpendek dari semua simpul kiri yang belum cocok; DFS menggunakan kursor sisi saat ini untuk menemukan sebanyak mungkin jalur yang saling lepas simpul dalam graf lapisan tersebut, lalu membalikkan sisi-sisinya. Ketika tidak ada jalur yang tersisa, teorema jalur augmentasi membuktikan keoptimalannya. Implementasi ini menggunakan waktu O((V+E)√V) dan penyimpanan O(V+E); graf kecil dapat menggunakan DFS sederhana, sedangkan tujuan berbobot memerlukan Hungarian atau min-cost flow.”
Kesalahan umum
- Menyebut hasil greedy sebagai maksimum; pencocokan maksimal bisa jauh lebih kecil daripada pencocokan maksimum.
- Hanya menyimpan satu sisi dari setiap pasangan dan menciptakan okupansi duplikat setelah pembalikan.
- Menghentikan BFS di sembarang jalur yang dapat dijangkau, yang merusak pengelompokan lapisan terpendek.
- Menghilangkan kursor sisi saat ini dan memindai ulang sisi yang gagal dalam satu fase.
- Mengklaim O((V+E)√V) untuk pencocokan umum, berbobot, atau yang diperbarui secara dinamis.
Pertanyaan lanjutan dan respons yang kuat
Bagaimana cara menghasilkan sisi kelayakan tanpa membandingkan semua pasangan n×m?
Bangun indeks terbalik berdasarkan tag. Masukkan objek sisi kanan ke dalam bucket, lalu gabungkan (union) dan hapus duplikat bucket untuk setiap objek kiri. E masih bisa berukuran besar, jadi laporkan E, ketimpangan tag populer (hot-tag skew), dan batas memori.
Mengapa algoritma dapat berhenti ketika tidak ada jalur augmentasi?
Setiap jalur augmentasi meningkatkan ukuran pencocokan sebanyak satu. Teorema jalur augmentasi menyatakan bahwa pencocokan yang lebih besar ada tepat ketika jalur augmentasi ada, sehingga kegagalan untuk menemukannya membuktikan kardinalitas maksimum.
Apa yang berubah untuk preferensi berbobot?
Hopcroft–Karp hanya mengoptimalkan jumlah sisi. Gunakan Hungarian atau min-cost max-flow, dan nyatakan kembali kompleksitas, batas bobot bilangan bulat, dan fallback ketika tidak ada penugasan yang layak.
Bagaimana Anda menangani perubahan sisi yang terus-menerus (churn)?
Algoritma batch cocok untuk komputasi ulang. Layanan online dapat mencari jalur augmentasi secara lokal di sekitar simpul yang terpengaruh, tetapi harus menyatakan latensi, batas penugasan ulang, dan kontrak non-optimalitas sementara.