Graf dan Batas Komputasi · Pelajaran 10 dari 10
P, NP, dan masalah yang sulit
9 menit baca · BelajarCode
Sejauh ini, hampir semua masalah yang kita selesaikan punya algoritma polinomial. Tetapi ada banyak masalah penting yang, sejauh diketahui, tidak punya algoritma polinomial.
Kelas P dan NP
| Kelas | Artinya | Contoh |
|---|---|---|
| P | Masalah keputusan yang bisa diselesaikan dalam waktu polinomial | Apakah ada jalur dari A ke B? Apakah array terurut? |
| NP | Masalah keputusan yang jawabannya "ya" bisa diperiksa dalam waktu polinomial jika diberi bukti | Apakah ada himpunan bagian yang jumlahnya tepat K? |
| NP-complete | Masalah tersulit di NP: jika satu saja bisa diselesaikan dalam waktu polinomial, semua masalah NP juga bisa | SAT, subset sum, pewarnaan graf dengan 3 warna, versi keputusan knapsack |
| NP-hard | Setidaknya sesulit NP-complete, belum tentu termasuk NP | Versi optimisasi dari travelling salesman |
Setiap masalah di P juga termasuk NP: jika bisa diselesaikan cepat, tentu bisa diperiksa cepat. Pertanyaan apakah P = NP, yaitu apakah setiap masalah yang mudah diperiksa juga mudah diselesaikan, adalah salah satu masalah terbuka terbesar dalam ilmu komputer dan matematika.
Memeriksa jauh lebih mudah dari menemukan
1from itertools import combinations23angka = [267, 961, 1153, 1000, 1922, 493, 1598, 869, 1766, 1246]4target = 580256def periksa(pilihan):7 return all(x in angka for x in pilihan) and sum(pilihan) == target89print("Memeriksa satu bukti:", periksa([961, 1153, 1922, 1766]))1011dicoba = 012ditemukan = None13for r in range(1, len(angka) + 1):14 for pilihan in combinations(angka, r):15 dicoba += 116 if sum(pilihan) == target:17 ditemukan = pilihan18 break19 if ditemukan:20 break21print("Menemukan:", ditemukan, "setelah mencoba", dicoba, "himpunan bagian")22print("Paling banyak yang harus dicoba:", 2 ** len(angka) - 1)Memeriksa satu bukti: True Menemukan: (961, 1153, 1922, 1766) setelah mencoba 269 himpunan bagian Paling banyak yang harus dicoba: 1023
Memeriksa sebuah bukti hanya butuh penjumlahan, Θ(n). Menemukan buktinya, sejauh yang diketahui, bisa membutuhkan pemeriksaan sampai 2ⁿ himpunan bagian. Untuk n = 100, angka itu jauh melampaui kemampuan semua komputer di dunia.
Apa yang dilakukan saat bertemu masalah NP-hard?
- Algoritma eksak untuk ukuran kecil, misalnya backtracking dengan pemangkasan atau DP pseudo-polinomial seperti knapsack.
- Algoritma aproksimasi yang menjamin hasil dalam faktor tertentu dari optimal.
- Heuristik, seperti greedy atau pencarian lokal, yang cepat dan sering cukup baik walaupun tanpa jaminan.
- Membatasi masalah ke kasus khusus yang punya algoritma polinomial, misalnya graf berbentuk pohon.
Kenapa penting bagi programmer
Mengenali bahwa sebuah masalah setara dengan masalah NP-complete menghemat banyak waktu: daripada mencari algoritma polinomial yang kemungkinan besar tidak ada, kamu bisa langsung memilih strategi aproksimasi atau heuristik yang tepat. Penjadwalan ujian dengan banyak batasan, misalnya, berkaitan erat dengan pewarnaan graf.
Cek pemahaman
Jika suatu hari terbukti ada algoritma polinomial untuk SAT, apa akibatnya?
Latihan
Aproksimasi untuk vertex cover
Vertex cover adalah himpunan simpul yang menyentuh setiap sisi graf. Mencari vertex cover terkecil adalah NP-hard. Implementasikan aproksimasi faktor 2: selama masih ada sisi yang belum tersentuh, ambil sisi itu dan masukkan kedua ujungnya. Bandingkan dengan solusi optimal hasil brute force.
Graf: A-B, A-C, B-C, B-D, C-E, D-E, D-F.
Pembahasan
1from itertools import combinations23sisi = [("A", "B"), ("A", "C"), ("B", "C"), ("B", "D"), ("C", "E"), ("D", "E"), ("D", "F")]4simpul = sorted({s for e in sisi for s in e})56cover = set()7for u, v in sisi:8 if u not in cover and v not in cover:9 cover.update([u, v])10print("Aproksimasi:", sorted(cover), "ukuran", len(cover))1112for r in range(1, len(simpul) + 1):13 optimal = next((set(c) for c in combinations(simpul, r)14 if all(u in c or v in c for u, v in sisi)), None)15 if optimal:16 break17print("Optimal:", sorted(optimal), "ukuran", len(optimal))Aproksimasi: ['A', 'B', 'C', 'D', 'E', 'F'] ukuran 6 Optimal: ['A', 'C', 'D'] ukuran 3
Sisi-sisi yang diambil aproksimasi tidak berbagi simpul, dan solusi optimal mana pun harus memuat minimal satu ujung dari setiap sisi itu. Karena aproksimasi mengambil dua ujung per sisi, hasilnya paling banyak dua kali optimal. Pada contoh ini tepat dua kali (6 dibanding 3).
Jalankan contoh kode di pelajaran ini tanpa instalasi lewat compiler Python online.