Mungkin, setiap orang dihadapkan pada kenyataan bahwa mereka harus menghadapi tugas yang sulit, solusinya tidak dapat ditemukan, tidak hanya saat itu juga - tetapi bahkan setelah jam kerja atau hari yang panjang dan keras kepala. Hari ini kita akan berbicara tentang salah satu kelas dari masalah tersebut - NP-complete.
Secara umum, apakah realistis untuk memenuhi tugas seperti itu dalam kehidupan sehari-hari? Faktanya, mereka muncul dalam sejumlah besar kasus: kombinatorik, grafik dan jaringan, eksekusi rumus logis, bekerja dengan peta, pemuatan optimal, peta, masalah pengoptimalan diskrit, menemukan urutan terpanjang, menemukan jumlah yang sama, dan banyak masalah yang ditetapkan! Dan ini bukan daftar lengkap.
Di bawah potongan adalah panduan informal - bagaimana memahami bahwa Anda mungkin memiliki masalah NP di depan Anda dan apa yang harus dilakukan jika ternyata memang seperti ini. Hari ini kami menyerang masalah ini dari sisi praktis.
,
, NP- ? -, — NP- - , — .
, :
- , n exp(n)
- n — ()
- () ( ).
- , .
- Parameter n - panjang solusi atau ruang itu sendiri tidak memiliki nilai tetap, yaitu, kita tidak berbicara tentang papan catur 8 x 8 yang selalu tetap, tetapi tentang bentuk umum dari masalah N-by-N.
Baca lebih lanjut tentang properti masalah NP-complete di sini dan di sini .
Contoh pekerjaan di daftar ini
Mari berikan contoh sederhana tentang masalah yang baru-baru ini disetujui sebagai NP-complete!
Berdasarkan materi artikel. Anda perlu menempatkan N queens di papan ukuran N kali N, asalkan sudah K <= N ditempatkan di papan (gambar dari artikel ilmiah asli)
Pertama, perhatikan bahwa masalah yang sangat mirip dengan NP kotak Latin yang dibatasi sebagian telah selesai.
Dan kemudian kita melihat daftarnya:
- Anda perlu mencari N queens dari space exp (N) (= N ^ 2 * (N ^ 2-1) * ....).
- Solusi ratu N diperiksa dengan mudah - untuk setiap ratu, Anda perlu memeriksa garis diagonal, vertikal dan horizontal.
- Menetapkan satu membuat pilihan sejumlah lainnya tidak valid - mis. ada ketergantungan antara elemen solusi (Anda tidak dapat mengatur ratu secara mandiri).
- Di sini Anda dapat menyelesaikan masalah dengan kekerasan untuk papan yang dipilih secara sewenang-wenang di exp (N) - kami meletakkan yang pertama di posisi pertama pada (i, j), yang kedua di papan yang tidak dihuni lainnya, dan seterusnya. Backtracking dijamin akan menemukan solusi.
- Masalahnya tidak memiliki parameter tetap - yaitu, ia diformulasikan dalam bentuk umum dan seiring dengan bertambahnya N, begitu pula kompleksitasnya.
Perhatikan bahwa salah satu item di daftar gagal jika papan diketahui selalu bersih dan tugas menjadi sepele.
Selain itu, ini adalah pendekatan praktis bersyarat - heuristik untuk mendeteksi masalah NP-complete (dengan semua pro dan kontra).
Percampuran
Sumber
Mengapa, memiliki masalah yang sama, tidak mudah untuk memahami secara formal bahwa kita memiliki masalah NP? Kita benar-benar perlu menyoroti masalah NP kita, lalu kita akan tahu pasti bahwa masalah kita adalah NP-hard! Dan jika kami dapat mensimulasikannya, seperti pada daftar di atas, maka itu lengkap - yaitu, setidaknya NP dan tidak lebih dari NP, sebenarnya “yang paling sulit di antara masalah NP” (seperti NP-complete yang lain).
Oke, apakah kita membutuhkannya? Tidak juga, jika Anda terus terang, setelah semua pemeriksaan, bahwa Anda menghadapi masalah NP, maka Anda tidak perlu membuktikan apa pun jika Anda tidak menulis artikel ilmiah.
Dan Anda membutuhkan keduanya (kita akan membicarakannya di bawah):
- simulasikan tugas Anda menggunakan sistem yang menyelesaikan tugas tersebut;
- temukan solusi yang bekerja cukup cepat dalam kasus Anda;
- temukan solusi perkiraan yang akan memuaskan kami.
Jangan menyerah!
Yang paling penting adalah mengevaluasi dimensi-parameter dan skenario realistis!
xkcd.com/287
Misalnya, Anda tahu bahwa meskipun nilai parameter tidak tetap, N <100 bersyarat tidak diterapkan di semua skenario praktis, yang berarti bahwa enumerasi bersyarat mungkin merupakan solusi nyata untuk Anda.
Anda perlu menentukan sendiri: apa nilai sebenarnya dari parameter yang mungkin dan benar-benar masuk ke sistem, apa distribusi umum dan fitur datanya, apa yang nyata dan apa yang tidak? Apakah kita membutuhkan solusi yang paling optimal? Mari kita bahas poin-poin ini.
Distribusi data masukan
Atau terlepas dari kenyataan bahwa, dalam kasus umum, data masukan dapat berupa apa saja, tetapi sekali lagi menggunakan contoh ratu - biasanya satu ratu tetap atau bahkan tidak sama sekali. Ini berarti bahwa 90% dari waktu Anda dapat menggunakan solusi yang sangat sederhana dan hanya memanggil yang kompleks dalam kasus yang ekstrim.
Contoh ketika, rata-rata, semua kombinasi biasa sederhana: masalah ratu pelengkap - kita tahu bahwa heuristik DFS + bersyarat dalam banyak kasus dapat menemukan solusi dengan sangat cepat, dan hanya dalam situasi yang sangat non-standar bisa sangat sulit.
Berikut adalah contoh bagaimana solusi untuk masalah petak NP-complete yang sangat terspesialisasi dievaluasi terhadap metode umum untuk memodelkan seluruh kelas dari masalah tersebut menggunakan teknik pemrograman logika:
(dari artikel Faktorisasi Data Relasional (Paramonov, Sergey; van Leeuwen, Matthijs; De Raedt, Luc: Faktorisasi data relasional, Pembelajaran Mesin, volume 106))
Pertama, kecepatan solusi LTM-k khusus dan metode umum berbeda secara signifikan. Dengan demikian, solusi untuk jenis masalah ini menggunakan heuristik dapat sepenuhnya menyelesaikan masalah ini.
Kedua, dengan mengorbankan kualitas solusi, metode pendekatan umum memberikan kecepatan yang sangat mirip.
Heuristik dan aproksimasi
Alat terakhir dan paling kuat adalah dengan menggunakan sistem pemodelan masalah NP-complete seperti Answer Set Programming .
Lebih lanjut tentang bahasa pemrograman logis.
Misalnya, solusi untuk masalah penempatan ratu akan terlihat seperti ini:
% domain
row(1..n).
column(1..n).
% alldifferent: guess a solution
1 { queen(X,Y) : column(Y) } 1 :- row(X).
1 { queen(X,Y) : row(X) } 1 :- column(Y).
% remove conflicting answers: check this solution
:- queen(X1,Y1), queen(X2,Y2), X1 < X2, Y1 == Y2.
:- queen(X1,Y1), queen(X2,Y2), X1 < X2, Y1 + X1 == Y2 + X2.
:- queen(X1,Y1), queen(X2,Y2), X1 < X2, Y1 - X1 == Y2 - X2.
Setelah melakukan percobaan sederhana untuk menemukan solusi untuk jumlah ratu N yang berbeda, kami mendapatkan yang berikut: sepanjang sumbu X - ratu, sepanjang Y - waktu per detik untuk menemukan solusi:
Kami melihat bahwa terlepas dari kenyataan bahwa pertumbuhan waktu jelas tidak polinomial (yang logis), kami melakukan pekerjaan yang baik dengan jumlah ratu dan ukuran papan yang memadai.
Kemudian, jika kita mengetahui dimensi papan yang nyata bagi kita, kita dapat memahami bagaimana solusi yang tepat ini dapat diterima oleh kita dalam sistem nyata.
kesimpulan
Mari kita bahas ide dari artikel dalam bentuk daftar periksa
- Tentukan bahwa Anda benar-benar memiliki masalah NP.
- Pahami apa itu nilai parameter realistis dan distribusi data.
- Cobalah untuk menulis (urutannya tergantung pada pengembang dan / atau tugas):
- Solusi heuristik yang akurat (berdasarkan analisis kami) - apakah cukup cepat?
- — ?
- NP- — ? , CPU ? .
- : , .
- — , — . !
:
