| [Anggota (365WT)]jawaban [Cina ] | Waktu :2017-11-24 | Semua algoritma masalah NP-hard yang diketahui memiliki runtimes eksponensial. Namun, algoritma polinomial terkadang ada jika kita mencari solusi "bagus" daripada solusi optimal.
Dengan adanya masalah minimisasi dan algoritma aproksimasi, kami mengevaluasi algoritma sebagai berikut: Pertama, berikan batas bawah solusi optimal, lalu bandingkan hasil algoritma dengan batas bawah.
Sebagai perbandingan. Untuk masalah maksimalisasi, berikan batas atas terlebih dahulu lalu bandingkan hasil running dari algoritma dengan upper bound.
Algoritma perkiraan meliputi: cakupan simpul minimum, masalah salesman perjalanan, cakupan yang ditetapkan dan sebagainya.
Sampai saat ini, semua masalah NP-complete tidak memiliki algoritma waktu-polinomial.
Untuk masalah seperti itu, biasanya strategi berikut bisa ditempuh.
(1) Selesaikan hanya beberapa kasus spesifik dari masalah
(2) menggunakan pemrograman dinamis atau metode branch and bound untuk dipecahkan
(3) selesaikan dengan algoritma probabilitas
(4) Hanya perkiraan solusi
(5) Gunakan metode heuristik untuk memecahkannya
Jika nilai optimal dari masalah optimasi adalah c *, perkiraan nilai fungsi tujuan dari perkiraan solusi optimal yang diperoleh oleh algoritma perkiraan untuk memecahkan masalah adalah c,
Rasio kinerja algoritma aproksimasi ini didefinisikan sebagai maks (c / c *, c * / c). Secara umum, rasio kinerja ini adalah fungsi dari ukuran input masalah n
ρ (n), yaitu, maks (c / c *, c * / c) ＜= ρ (n).
Kesalahan relatif dari algoritma aproksimasi didefinisikan sebagai Abs [(c-c *) / c *]. Jika n ukuran input dari suatu masalah memiliki fungsi ε (n) sedemikian rupa sehingga Abs [(c-c *) / c *] ＜= ε (n), maka ε (n) adalah batas kesalahan relatif dari algoritma aproksimasi. Rasio kinerja perkiraan antara ρ (n) dan batas kesalahan relatif ε (n) jelas adalah sebagai berikut
Hubungan: ε (n) ≤ρ (n) -1. |
|
