Tugas ALPRO

Translate 892-905

Oleh:

Muhammad Hudzaifah / 21120111130024

PROGRAM STUDI SISTEM KOMPUTERFAKULTAS TEKNIK

UNIVERSITAS DIPONEGORO

SEMARANG

2014Empat bagian pertama bab ini menyajikan beberapa contoh algoritma polynomial-time approximation untuk masalah NP - lengkap , dan bagian kelima menyajikan sepenuhnya Skema pendekatan polinomial - waktu . Bagian 35.1 dimulai dengan studi tentang masalah vertex cover, masalah minimisasi NP - lengkap yang memiliki algoritma pendekatan dengan rasio perkiraan 2 . Bagian 35.2 menyajikan algoritma pendekatan dengan rasio perkiraan 2 untuk kasus masalah traveling salesman - di mana biaya fungsi memenuhi ketidaksamaan segitiga . Hal ini juga menunjukkan bahwa tanpa ketidaksamaan segitiga , untuk setiap konstan 1 , algoritma - pendekatan tidak dapat diapaki kecuali P = NP . Dalam Bagian 35.3 , kami menunjukkan bagaimana metode greedy dapat digunakan sebagai algoritma pendekatan yang efektif untuk masalah set- covering , mendapatkan cover yang biaya paling buruk merupakan faktor logaritmik yang lebih besar dari biaya yang optimal . Bagian 35.4 menyajikan dua algoritma pendekatan lagi. pertama-tama kita mempelajari versi optimasi dari 3 - CNF satisfiability dan memberikan algoritma acak sederhana yang menghasilkan solusi dengan rasio perkiraan yang diharapkan dari 8/7 . kemudian kita memeriksa bermacam bobot masalah pada vertex -cover dan menunjukkan bagaimana menggunakan pemrograman linear untuk mengembangkan algoritma 2 - approximatation . Akhirnya , Bagian 35.5 menyajikan sepenuhnya skema pendekatan polinomial - waktu untuk masalah subset-sum .35.1 Masalah vertex -cover

Masalah vertex -cover didefinisikan dan terbukti NP - lengkap dalam Bagian 34.5.2 . Sebuah vertex cover yang diarahkan graf G = ( V , E ) adalah subset V ' ? V sedemikian sehingga jika ( u , v ) adalah tepi G , maka baik u ? V ' atau v ? V ' ( atau keduanya ) . Ukuran vertex cover adalah jumlah simpul di itu .

Masalah vertex -cover adalah untuk menemukan vertex cover dari ukuran minimum dalam diarahkan diberikan graph . Kami menyebutnya seperti COVER simpul VERTEX COVER optimal . Masalah ini adalah optimasi versi masalah keputusan NP - lengkap .

Meskipun mungkin sulit untuk menemukan vertex cover optimal dalam grafik G , itu tidak terlalu sulit untuk menemukan vertex cover yang mendekati optimal . Algoritma pendekatan berikut mengambil sebagai masukan sebuah grafik diarahkan G dan mengembalikan vertex cover yang ukurannya dijamin tidak lebih dari dua kali ukuran vertex cover optimal .

APPROX-VERTEX-COVER( G " >

1 C

2 E ' E [ G ]

3 while E '

4 do let ( u , v ) be an arbitrary edge of E 5 C C ? { u , v }

6 remove from E every edge incident on either u or v7 return C

Gambar 35.1 mengilustrasikan operasi APPROX-VERTEX-COVER. Variabel C berisi VERTEX COVER sedang dibangun . Baris 1 menginisialisasi C ke set kosong . Baris 2 set E ' menjadi salinan himpunan sisi E [ G ] grafik. Loop pada baris 3-6 berulang kali mengambil tepi ( u , v ) dari E ' , menambahkan titik ujungnya u dan v ke C , dan menghapus semua sisi di E ' yang meliputi baik u atau v Waktu berjalan dari algoritma ini adalah O ( V + E ) , menggunakan daftar adjacency untuk mewakili E ' .

Gambar 35.1 : Operasi APPROX-VERTEX-COVER. ( a) masukan graf G , yang memiliki 7 simpul dan 8 tepi . ( b ) Tepi ( b , c ) , menunjukkan berat , adalah tepi pertama yang dipilih oleh APPROX-VERTEX-COVER. Simpul b dan c , yang ditunjukkan ringan berbayang , ditambahkan ke set C mengandung VERTEX COVER yang diciptakan . Tepi (a , b ) , ( c , e ) , dan ( c , d ) , ditampilkan berlari , adalah dihapus karena mereka sekarang ditutupi oleh beberapa titik di C. ( c ) Ujung ( e , f ) dipilih ; simpul e dan f ditambahkan ke C. ( d ) Ujung ( d , g ) dipilih , simpul d dan g ditambahkan ke C. ( e ) Set C , yang merupakan VERTEX COVER diproduksi oleh KIRA-KIRA - VERTEX - COVER, berisi enam simpul b , c , d , e , f , g . ( f) titik COVER optimal untuk masalah ini hanya berisi tiga simpul : b , d , dan e .

teorema 35.1

APPROX-VERTEX-COVERadalah polinomial - waktu algoritma 2 - pendekatan .

Buktinya Kami telah menunjukkan bahwa APPROX-VERTEX-COVERberjalan dalam waktu polinomial .

Set C simpul yang dikembalikan oleh APPROX-VERTEX-COVER adalah VERTEX COVER , karena algoritma loop sampai setiap tepi dalam E [ G ] telah tertutup oleh beberapa titik di C.

Untuk melihat bahwa APPROX-VERTEX-COVER mengembalikan COVER titik yang paling dua kali ukuran dari cover optimal , misalkan A melambangkan himpunan tepi yang diambil sejalan 4 dari APPROXVERTEX - COVER . Dalam rangka untuk menutupi tepi di A , setiap vertex menutup- khususnya, COVER C optimal * - harus menyertakan setidaknya satu titik akhir dari setiap sisi di A. ada dua sisi di A berbagi titik akhir , karena sekali keunggulan diambil sejalan 4 , semua sisi lain yang insiden pada titik ujungnya akan dihapus dari E ' sejalan 6 . Dengan demikian , tidak ada dua sisi di A tercakup dalam yang sama vertex dari C * , dan kami memiliki batas bawah

(35.2) pada ukuran COVER titik optimal. Setiap pelaksanaan baris 4 mengambil keunggulan yang tak satu pun dari titik ujungnya sudah di C, menghasilkan batas atas (yang tepat batas atas, di Bahkan) pada ukuran VERTEX COVER kembali:

(35.3) Menggabungkan persamaan (35.2) dan (35.3), kita memperoleh

|C| = 2|A|

2|C*|,sehingga membuktikan teorema .

Mari kita merenungkan bukti ini . Pada awalnya orang mungkin bertanya-tanya bagaimana mungkin untuk membuktikan bahwa ukuran VERTEX COVER dikembalikan oleh APPROX-VERTEX-COVERadalah paling banyak dua kali ukuran dari VERTEX COVER optimal , karena kita tidak tahu apa ukuran VERTEX COVER optimal . itu Jawabannya adalah bahwa kita menggunakan batas bawah pada COVER titik optimal . Sebagai Latihan 35,1-2 meminta Anda untuk menunjukkan , himpunan A dari tepi yang diambil sejalan 4 dari APPROX - VERTEX - COVER adalah sebenarnya cocok maksimal dalam grafik G. ( A matching maksimal adalah pencocokan yang bukan bagian yang tepat dari setiap pencocokan lainnya . ) Ukuran pencocokan maksimal adalah , seperti yang kita berdebat di bukti Teorema 35.1 , lebih rendah terikat pada ukuran COVER titik optimal . algoritma mengembalikan COVER simpul yang ukurannya paling dua kali ukuran pencocokan maksimal A. Dengan terkait ukuran dari solusi kembali ke batas bawah , kita memperoleh perkiraan kami rasio . Kami akan menggunakan metodologi ini dalam bagian berikutnya juga.latihan 35,1-1

Berikan contoh dari grafik yang APPROX-VERTEX-COVERselalu menghasilkan solusi suboptimal .latihan 35,1-2

Biarkan A melambangkan himpunan tepi yang diambil sejalan 4 dari APPROX - VERTEX - COVER . Buktikan bahwa himpunan A adalah matching maksimal pada graf G.Latihan 35,1-3 : Profesor Nixon mengusulkan heuristik berikut untuk memecahkan masalah vertex -cover . Berulang kali memilih vertex dari tingkat tertinggi , dan menghapus semua tepi insiden tersebut . Berikan contoh untuk menunjukkan bahwa heuristik profesor tidak memiliki rasio perkiraan 2 . ( Petunjuk : Cobalah graf bipartit dengan simpul dari derajat yang seragam di sebelah kiri dan simpul dari berbagai derajat di sebelah kanan . )latihan 35,1-4

Berikan sebuah algoritma greedy efisien yang menemukan sebuah titik COVER optimal untuk pohon dalam waktu linier .

latihan 35,1-5

Dari bukti Teorema 34.12 , kita tahu bahwa masalah vertex -cover dan Npcomplete Masalah clique saling melengkapi dalam arti bahwa COVER titik optimal adalah melengkapi dari clique maksimum ukuran dalam grafik pelengkap . Apakah hubungan ini menyiratkan bahwa ada algoritma pendekatan polinomial - waktu dengan rasio pendekatan konstan untuk masalah clique ? Membenarkan jawaban Anda .

35.2 Masalah traveling - salesman

Dalam masalah traveling - salesman diperkenalkan dalam Bagian 34.5.4 , kita diberi lengkap graf tak berarah G = ( V , E ) yang memiliki nonnegatif biaya bilangan bulat c ( u , v ) yang terkait dengan setiap edge ( u , v ) ? E , dan kita harus menemukan siklus Hamiltonian ( tur ) dari G dengan biaya minimum . sebagai perluasan notasi kita, marilah c ( A ) menunjukkan total biaya tepi dalam subset A ? E :

Dalam banyak situasi praktis , selalu termurah untuk pergi langsung dari tempat u ke tempat w; akan dengan cara apapun antara berhenti v tidak bisa lebih murah . Puting itu cara lain , memotong berhenti menengah tidak meningkatkan biaya . Kami meresmikan gagasan ini dengan mengatakan bahwa fungsi biaya c memenuhi ketidaksamaan segitiga jika untuk semua simpul u , v , w ? V ,

c ( u , w ) c ( u , v ) + c ( v , w ) .

Segitiga ketidaksetaraan adalah satu alam , dan dalam banyak aplikasi maka secara otomatis puas . Sebagai contoh, jika simpul dari grafik adalah poin dalam pesawat dan biaya perjalanan antara dua simpul adalah jarak euclidean biasa di antara mereka , maka segitiga ketidaksetaraan puas . ( Ada banyak fungsi biaya selain jarak euclidean yang memenuhi ketidaksamaan segitiga . )

Sebagai Latihan 35,2-2 menunjukkan , masalah traveling - salesman adalah NP - lengkap bahkan jika kita membutuhkan bahwa fungsi biaya memenuhi ketidaksamaan segitiga . Dengan demikian , tidak mungkin bahwa kita dapat menemukan algoritma polinomial - waktu untuk memecahkan masalah ini persis . Oleh karena itu kita melihat sebaliknya untuk algoritma pendekatan yang baik .

Dalam Bagian 35.2.1 , kita memeriksa algoritma 2 - pendekatan untuk bepergian salesman masalah dengan ketidaksetaraan segitiga . Dalam Bagian 35.2.2 , kami menunjukkan bahwa tanpa segitiga ketimpangan , algoritma aproksimasi polinomial - waktu dengan rasio pendekatan konstan tidak ada kecuali P = NP .

35.2.1 Masalah traveling- salesman dengan ketidaksetaraan segitiga

Menerapkan metodologi bagian sebelumnya , pertama-tama kita akan menghitung struktur a spanning minimum pohon yang berat badannya batas bawah pada panjang sebuah perjalanan optimal tour salesman . Kami kemudian akan menggunakan pohon rentang minimum untuk membuat tur yang biayanya tidak lebih dari dua kali lipat dari berat pohon rentang minimum itu , asalkan fungsi biaya memenuhi ketidaksamaan segitiga . Algoritma berikut mengimplementasikan pendekatan ini , memanggil algoritma minimum spanning - tree MST - PRIM dari Bagian 23.2 sebagai sebuah sub rutin .

KIRA-KIRA - TSP - TOUR ( G , c " >

1 pilih simpul r ? V [ G ] untuk menjadi " root" simpul

2 menghitung rentang T tree minimum untuk G dari akar r

menggunakan MST - PRIM ( G , c , r )

3 membiarkan L menjadi daftar simpul dikunjungi di pohon preorder berjalan dari T

4 mengembalikan H siklus Hamiltonian yang mengunjungi simpul dalam urutan L

Ingat dari Bagian 12.1 bahwa pohon preorder berjalan secara rekursif mengunjungi setiap simpul di pohon , daftar simpul ketika pertama kali bertemu , sebelum anak-anak yang dikunjungi .

Gambar 35.2 mengilustrasikan operasi KIRA-KIRA - TSP - TOUR . Bagian ( a) dari angka menunjukkan diberikan seperangkat simpul , dan bagian ( b ) menunjukkan minimum spanning tree T tumbuh dari akar vertex dengan MST - PRIM . Bagian ( c ) menunjukkan bagaimana simpul dikunjungi oleh preorder berjalan dari T , dan bagian ( d ) menampilkan tur yang sesuai , yang merupakan tur dikembalikan oleh KIRA-KIRA - TSP - TOUR . Bagian ( e ) menampilkan tur optimal , yaitu sekitar 23 % lebih pendek .

Gambar 35.2 : Operasi KIRA-KIRA - TSP - TOUR . ( a) Himpunan diberikan poin , yang terletak di simpul dari grid integer. Sebagai contoh, f adalah satu unit ke kanan dan dua unit naik dari h . itu jarak euclidean biasa digunakan sebagai fungsi biaya antara dua titik . ( b ) minimum A spanning tree T dari titik-titik ini , seperti yang dihitung dengan MST - PRIM . Vertex adalah simpul akar . itu simpul terjadi dilabel sedemikian rupa sehingga mereka ditambahkan ke pohon utama dengan MSTPRIM dalam urutan abjad . ( c ) Berjalan dari T , mulai pada . Berjalan-jalan penuh pohon mengunjungi simpul dalam urutan a, b , c , b , h, b, a , d , e , f , e , g , e , d , a . Sebuah preorder berjalan dari T daftar vertex a hanya ketika pertama kali bertemu , seperti yang ditunjukkan oleh titik di samping setiap vertex , yang menghasilkan memesan a, b , c , h, d , e , f , g . ( d ) Sebuah tur simpul diperoleh dengan mengunjungi simpul dalam perintah yang diberikan oleh preorder berjalan . Ini adalah H tour dikembalikan oleh KIRA-KIRA - TSP - TOUR . nya total biaya adalah sekitar 19,074 . ( e ) Sebuah tur H * optimal untuk himpunan simpul . nya total biaya adalah sekitar 14,715 .

Dengan Latihan 23,2-2 , bahkan dengan implementasi sederhana dari MST - PRIM , waktu berjalan dari KIRA-KIRA - TSP - TOUR adalah 0398 ( V2 ) . Kita sekarang menunjukkan bahwa jika fungsi biaya untuk contoh masalah traveling - salesman memenuhi ketidaksamaan segitiga , maka APPROX - TSP TOUR mengembalikan tur yang biaya tidak lebih dari dua kali biaya tur yang optimal . teorema 35.2

KIRA-KIRA - TSP - TOUR adalah polinomial - waktu algoritma 2 - pendekatan untuk travelingsalesman yang masalah dengan ketidaksetaraan segitiga .

Buktinya Kami telah menunjukkan bahwa KIRA-KIRA - TSP - TOUR berjalan dalam waktu polinomial .

Biarkan H * menunjukkan tur optimal untuk himpunan simpul . Karena kita mendapatkan spanning tree oleh menghapus setiap tepi dari tur , berat minimum spanning tree T adalah terikat pada rendah biaya tur yang optimal , yaitu,

( 35,4 ) Berjalan penuh T daftar simpul ketika mereka pertama kali mengunjungi dan juga setiap kali mereka kembali ke setelah kunjungan ke subtree . Mari kita sebut ini berjalan W . Berjalan penuh contoh kita memberi perintah

a, b , c , b , h, b, a , d , e , f , e , g , e , d , a .

Karena berjalan penuh melintasi setiap tepi T persis dua kali , kami telah ( memperluas definisi kita dari c biaya dengan cara alami untuk menangani multisets dari tepi )

( 35.5 ) Persamaan ( 35.4 ) dan ( 35.5 ) menyiratkan bahwa

( 35,6 ) dan sehingga biaya W adalah dalam faktor 2 dari biaya tur yang optimal .

Sayangnya , W umumnya tidak tur , karena mengunjungi beberapa simpul lebih dari sekali . oleh segitiga ketidaksetaraan , bagaimanapun , kita dapat menghapus kunjungan ke simpul apapun dari W dan biaya tidak meningkat. ( Jika simpul v dihapus dari W antara kunjungan ke u dan w , pemesanan yang dihasilkan menentukan akan langsung dari u ke w . ) Dengan berulang kali menerapkan operasi ini , kita dapat menghapus dari W semua tapi kunjungan pertama ke setiap sudut . Dalam contoh kita , ini daun pengurutan

a, b , c , h, d , e , f , g .

Pemesanan ini adalah sama dengan yang diperoleh oleh preorder berjalan dari pohon T. Misalkan H menjadi siklus sesuai dengan preorder ini berjalan . Ini adalah siklus Hamiltonian , karena setiap simpul dikunjungi tepat satu kali , dan pada kenyataannya itu adalah siklus dihitung dengan KIRA-KIRA - TSP - TOUR . Sejak H adalah diperoleh dengan menghapus simpul dari penuh berjalan W , kita harus

( 35,7 ) Menggabungkan ketidaksetaraan ( 35,6 ) dan ( 35,7 ) menunjukkan bahwa c ( H ) 2c ( H * ) , yang melengkapi bukti .

Meskipun rasio pendekatan yang bagus yang disediakan oleh Teorema 35.2 , APPROX - TSP - TOUR adalah biasanya bukan pilihan praktis terbaik untuk masalah ini . Ada pendekatan lain algoritma yang biasanya tampil lebih baik dalam praktek . Lihat referensi di akhir ini bab .

35.2.2 Masalah traveling - salesman umum

Jika kita drop asumsi bahwa fungsi biaya c memenuhi ketidaksamaan segitiga , baik Tur perkiraan tidak dapat ditemukan dalam waktu polinomial kecuali P = NP .

teorema 35.3

Jika P NP , maka untuk setiap konstan 1 , tidak ada algoritma pendekatan polinomial waktu dengan pendekatan rasio untuk masalah traveling - salesman umum .

Bukti Buktinya adalah dengan kontradiksi . Misalkan yang bertentangan bahwa untuk beberapa nomor 1 , ada polinomial - waktu algoritma pendekatan A dengan pendekatan rasio . tanpa kehilangan umum , kita berasumsi bahwa adalah bilangan bulat , dengan pembulatan ke atas jika diperlukan . Kami akan kemudian menunjukkan bagaimana menggunakan A untuk memecahkan kasus masalah siklus Hamiltonian (didefinisikan dalam Bagian 34,2 ) dalam waktu polinomial . Karena masalah siklus Hamiltonian adalah NP - lengkap , oleh Teorema 34.13 , pemecahan itu dalam waktu polinomial menunjukkan bahwa P = NP , menurut Teorema 34.4 .

Misalkan G = ( V , E ) merupakan contoh dari masalah siklus Hamiltonian . Kami ingin menentukan efisien apakah G mengandung siklus Hamiltonian dengan memanfaatkan hipotesis yang Algoritma pendekatan A. Kami mengubah G menjadi contoh masalah traveling - salesman sebagai berikut . Mari G ' = ( V , E ' ) adalah graf lengkap tentang V , yaitu , E ' = { ( u , v ) : u , v ? V dan u v } .

Menetapkan biaya integer ke setiap sisi di E ' sebagai berikut :

Representasi dari G ' dan c dapat dibuat dari representasi G dalam waktu polinomial di

| V | dan | E | .

Sekarang , mempertimbangkan masalah traveling - salesman ( G ' , c ) . Jika grafik asli G memiliki Hamilton siklus H , maka fungsi biaya c memberikan untuk setiap tepi H biaya 1 , dan sebagainya ( G ' , c ) berisi tur biaya | V | . Di sisi lain , jika G tidak mengandung Hamiltonian a siklus , maka setiap tur G ' harus menggunakan beberapa tepi tidak di E. Tetapi setiap tur yang menggunakan kelebihan tidak E memiliki biaya minimal

( | V | + 1 ) + ( | V | - 1 ) = | V | + | V |Karena tepi tidak di G begitu mahal , ada kesenjangan setidaknya | V | antara biaya tur yang merupakan siklus Hamiltonian dalam G ( biaya | V | ) dan biaya tur lain ( biaya setidaknya | V | + | V | ) .

Apa yang terjadi jika kita menerapkan pendekatan algoritma A untuk masalah traveling salesman ( G ' , c ) ? Karena A dijamin untuk kembali tur biaya tidak lebih dari kali biaya yang Tur optimal , jika G mengandung siklus Hamiltonian , maka A harus mengembalikannya . Jika G tidak memiliki siklus Hamiltonian , maka A kembali tur biaya lebih dari | V | . Oleh karena itu, kita dapat menggunakan A untuk memecahkan Masalah siklus Hamiltonian dalam waktu polinomial .

Bukti dari Teorema 35.3 adalah contoh dari teknik umum untuk membuktikan bahwa masalah tidak dapat didekati dengan baik . Misalkan diberikan masalah X NP - keras , kita dapat menghasilkan masalah minimisasi Y sedemikian rupa sehingga " ya" contoh X sesuai dengan contoh Y dengan nilai paling banyak k ( untuk beberapa k ) , tetapi bahwa "tidak ada " contoh X sesuai dengan contoh Y dengan nilai lebih besar dari k . Kemudian kami telah menunjukkan bahwa , kecuali P = NP , tidak ada pendekatan algoritma untuk masalah Y.

latihan 35,2-1

Misalkan sebuah grafik diarahkan lengkap G = ( V , E ) dengan setidaknya 3 simpul memiliki biaya fungsi c yang memenuhi ketidaksamaan segitiga . Buktikan bahwa c ( u , v ) 0 untuk semua u , v ? V.

latihan 35,2-2

Tunjukkan bagaimana dalam waktu polinomial kita dapat mengubah satu contoh dari perjalanan salesman masalah menjadi contoh lain yang fungsinya biaya memenuhi ketidaksamaan segitiga . kedua contoh harus memiliki set yang sama tur optimal . Jelaskan mengapa seperti polinomial waktu transformasi tidak bertentangan Teorema 35.3 , dengan asumsi bahwa P NP .

latihan 35,2-3

Pertimbangkan hal berikut paling dekat - titik heuristik untuk membangun perkiraan traveling salesman tour . Mulailah dengan siklus sepele yang terdiri dari satu titik sewenang-wenang dipilih . Pada setiap langkah , mengidentifikasi u vertex yang tidak pada siklus tetapi yang jarak ke titik manapun pada siklus ini minimum . Misalkan titik pada siklus yang u terdekat adalah vertex v Memperpanjang siklus untuk memasukkan u dengan memasukkan u setelah v Ulangi sampai semua simpul pada siklus . Buktikan bahwa ini heuristik kembali tur yang total biaya tidak lebih dari dua kali biaya tur yang optimal .

latihan 35,2-4

Hambatan masalah traveling - salesman adalah masalah menemukan siklus Hamiltonian sehingga biaya tepi paling mahal dalam siklus diminimalkan . Dengan asumsi bahwa biaya fungsi memenuhi ketidaksamaan segitiga , menunjukkan bahwa ada algoritma polynomial-time approximation dengan rasio pendekatan 3 untuk masalah ini . ( Petunjuk : Tampilkan rekursif bahwa kita bisa mengunjungi semua node dalam pohon bottleneck spanning , seperti yang dibahas pada Soal 23-3 , tepat sekali dengan mengambil jalan penuh pohon dan melewatkan node , tapi tanpa melewatkan lebih dari dua node intermediate berturut-turut . Tunjukkan bahwa tepi termahal di kemacetan pohon rentang memiliki biaya yang paling biaya tepi termahal di kemacetan siklus Hamiltonian . )

latihan 35,2-5

Misalkan simpul untuk contoh masalah traveling - salesman adalah poin dalam pesawat dan bahwa biaya c ( u , v ) adalah jarak euclidean antara titik u dan v Tunjukkan bahwa suatu Tur optimal pernah terlintas sendiri .

35,3 Set- meliputi masalah

Set -covering masalah adalah masalah optimasi yang model banyak sumber daya seleksi masalah . Its masalah keputusan yang sesuai generalisasi NP - lengkap vertex cover masalah dan karena itu juga NP-hard . Algoritma pendekatan yang dikembangkan untuk menangani masalah vertex -cover tidak berlaku di sini , bagaimanapun, dan jadi kita perlu mencoba pendekatan lain . Kita akan memeriksa heuristik greedy sederhana dengan rasio pendekatan logaritmik . Artinya, sebagai ukuran contoh akan lebih besar , ukuran solusi perkiraan dapat tumbuh , relatif terhadap ukuran solusi optimal . Karena fungsi logaritma tumbuh agak lambat , namun, algoritma pendekatan ini tetap dapat memberikan hasil yang bermanfaat . Sebuah contoh (X,F ) dari set -covering masalah terdiri dari satu set X terbatas dan keluarga himpunan bagian dari X , sehingga setiap elemen X milik setidaknya satu bagian dalam :

Kita mengatakan bahwa subset mencakup unsur-unsurnya . Masalahnya adalah untuk menemukan minimum ukuran bagian anggota yang mencakup semua X :

( 35,8 ) Kami mengatakan bahwa setiap persamaan memuaskan ( 35,8 ) meliputi X. Gambar 35.3 menggambarkan set covering masalah . Ukuran didefinisikan sebagai jumlah set yang dikandungnya, bukan jumlah elemen individu dalam perangkat ini . Pada Gambar 35.3 , minimum menutup set memiliki ukuran 3 .

Gambar 35.3 : Sebuah contoh ( X , ) dari set -covering problem , di mana X terdiri dari 12 hitam poin dan . Satu set minimum ukuran cover . Algoritma greedy menghasilkan sampul ukuran 4 dengan memilih set S1 , S4 , S5 , dan S3 dalam urutan .

Set -covering masalah adalah sebuah abstraksi dari banyak umumnya timbul kombinatorial masalah . Sebagai contoh sederhana , misalkan X merupakan seperangkat keterampilan yang diperlukan untuk memecahkan masalah dan bahwa kita memiliki himpunan orang yang tersedia untuk bekerja pada masalah . kami ingin membentuk sebuah komite , yang mengandung sebagai beberapa orang mungkin, sehingga untuk setiap diperlukan keterampilan dalam X , ada anggota komite yang memiliki keahlian itu . Dalam versi keputusan set- meliputi masalah , kita bertanya apakah atau tidak meliputi itu ada dengan ukuran paling k , di mana k adalah parameter tambahan yang ditentukan dalam contoh masalah . Versi Keputusan masalah adalah NP - lengkap, seperti Latihan 35,3-2 meminta Anda untuk menunjukkan .

Algoritma greedy approximationMetode greedy bekerja dengan memilih , pada setiap tahap , himpunan S yang mencakup jumlah terbesar

unsur-unsur yang ditemukan yang tersisa .

GREEDY - SET - COVER ( X , )

1 U X

2

3 while U

4 jangan pilih yang memaksimalkan | S ? U |

5 U U - S

6

7 returnPada contoh Gambar 35.3 , GREEDY - SET - COVER menambah set S1 , S4 , S5 , dan S3 , di urutan.

Algoritma ini bekerja sebagai berikut . Set U berisi, pada setiap tahap , set tersisa unsur ditemukan . Set berisi COVER sedang dibangun . Jalur 4 adalah greedy langkah pengambilan keputusan . Sebuah subset S dipilih yang mencakup banyak elemen terungkap sebagai mungkin ( dengan ikatan rusak sewenang-wenang ) . Setelah S dipilih, unsur-unsurnya akan dihapus dari U , dan S ditempatkan di . Bila algoritma berakhir , set berisi subfamili yang meliputi X.

Algoritma GREEDY - SET - COVER dapat dengan mudah diimplementasikan untuk berjalan dalam waktu polinomial in | X | dan | | . Karena jumlah iterasi loop pada baris 3-6 dibatasi dari atas dengan min ( | X | , | | ) , dan tubuh loop dapat diimplementasikan untuk berjalan dalam waktu O ( | X | | | ) , ada implementasi yang berjalan dalam waktu O ( | X | | | min ( | X | , | | ) ) . Latihan 35,3-3 meminta lineartime a algoritma .

AnalisaKami sekarang menunjukkan bahwa algoritma greedy mengembalikan cover set yang tidak terlalu jauh lebih besar daripada cover set optimal . Untuk kenyamanan , dalam bab ini kita menunjukkan jumlah harmonik dth ( lihat Bagian A.1 ) oleh H ( d ) . Sebagai syarat batas , kita mendefinisikan H ( 0 ) = 0 .

teorema 35.4

GREEDY - SET - COVER adalah polinomial - waktu algoritma ( n ) - pendekatan , di mana

Bukti Kami telah menunjukkan bahwa GREEDY - SET - COVER berjalan dalam waktu polinomial .

Untuk menunjukkan bahwa GREEDY - SET - COVER adalah (n ) - pendekatan algoritma , kita menetapkan biaya 1 masing-masing set yang dipilih oleh algoritma , mendistribusikan biaya ini atas elemen tertutup untuk pertama kalinya , dan kemudian menggunakan biaya ini untuk mendapatkan hubungan yang diinginkan antara ukuran sebuah set optimal cover dan ukuran cover set dikembalikan oleh algoritma . Biarkan Si menyatakan engan subset yang dipilih oleh GREEDY - SET - COVER , algoritma menimbulkan biaya 1 ketika itu menambah Si untuk . Kami menyebar biaya ini memilih Si merata di antara unsur-unsur yang dicakup untuk pertama waktu dengan Si . Biarkan cx menunjukkan biaya yang dialokasikan untuk elemen x , untuk setiap x ? X. Setiap elemen adalah ditugaskan biaya hanya sekali , ketika tertutup untuk pertama kalinya . Jika x tertutup untuk pertama kalinya oleh Si , maka

Pada setiap langkah algoritma, 1 unit biaya diberikan , dan sebagainya

Biaya ditugaskan untuk COVER optimal adalah

dan karena masing-masing x ? X dalam setidaknya satu set , kita memiliki

Menggabungkan dua ketidaksamaan sebelumnya , kita mendapati bahwa( 35,9 ) Sisa pembuktian terletak pada ketidaksetaraan kunci berikut , yang akan kita buktikan lama . Untuk setiap set S milik keluarga ,

( 35.10 ) Dari kesenjangan ( 35,9 ) dan ( 35,10 ) , berarti

sehingga membuktikan teorema . Semua yang tersisa adalah untuk membuktikan ketidaksetaraan ( 35.10 ) . Pertimbangkan setiap set dan i = 1 , 2 , ... , | | , dan

mari

ui = | S - ( S1 ; ? ? S2 ; Si ) |

menjadi jumlah elemen dalam S yang tersisa terungkap setelah S1 , S2 , ... , Si telah dipilih oleh algoritma . Kami mendefinisikan u0 = | S | menjadi jumlah elemen dari S , yang semua awalnya ditemukan . Misalkan k menjadi indeks paling sehingga uk = 0 , sehingga setiap elemen dalam S ditutupi oleh di Setidaknya satu set S1 , S2 , ... , Sk . Kemudian , ui - 1 ui , dan - ui 1 - unsur ui dari S ditutupi untuk pertama kali oleh Si , untuk i = 1 , 2 , ... , k . Dengan demikian ,

Perhatikan bahwa

| Si - ( S1 S2 Si - 1 ?) | | S - ( S1 S2 Si - 1 ?) |

= Ui - 1 ,

karena pilihan rakus Si menjamin bahwa S tidak dapat menutupi elemen yang lebih baru daripada Si tidak ( jika tidak, S akan dipilih sebagai pengganti Si ) . Akibatnya, kita memperoleh

Kita sekarang terikat kuantitas ini sebagai berikut :

yang melengkapi bukti ketidaksetaraan (35.10).

Corollary 35.5

GREEDY-SET-COVER adalah polinomial-waktu (ln | + 1 | X) algoritma-pendekatan.

Bukti Gunakan ketidaksetaraan (A.14) dan Teorema 35.4.

Dalam beberapa aplikasi, adalah konstanta kecil, sehingga solusinya dikembalikan oleh GREEDY-SET-COVER adalah paling banyak waktu konstan kecil lebih besar dari optimal. salah satu seperti aplikasi terjadi ketika heuristik ini digunakan untuk mendapatkan titik COVER perkiraan untuk graph yang simpul memiliki gelar paling banyak 3. Dalam hal ini, solusinya ditemukan oleh GREEDYSET- COVER tidak lebih dari H (3) = 11/6 kali lebih besar sebagai solusi yang optimal, jaminan kinerja yang sedikit lebih baik daripada KIRA-KIRA-VERTEX-COVER.

latihan 35,3-1

Pertimbangkan setiap kata-kata berikut sebagai satu set huruf: {gersang, dash, tiriskan, mendengar, hilang, hidung, shun, batu tulis, snare, benang}. Tampilkan yang mengatur COVER GREEDY-SET COVER menghasilkan ketika ikatan yang rusak demi kata yang muncul pertama kali dalam kamus.

latihan 35,3-2

Tunjukkan bahwa versi keputusan set -covering masalah adalah NP - lengkap dengan reduksi dari masalah vertex -cover .latihan 35,3-3

Tampilkan bagaimana menerapkan GREEDY - SET - COVER sedemikian rupa sehingga berjalan dalam waktu

latihan 35,3-4

Tunjukkan bahwa mengikuti bentuk yang lebih lemah dari Teorema 35.4 adalah sepele benar:

latihan 35,3-5

GREEDY - SET - COVER dapat kembali sejumlah solusi yang berbeda , tergantung pada bagaimana kita memutuskan hubungan di baris 4 . Berikan prosedur BAD - SET - COVER- Instance ( n ) yang mengembalikan sebuah nelement contoh dari set -covering masalah yang , tergantung bagaimana hubungan yang rusak di baris 4 , GREEDY - SET - COVER dapat kembali sejumlah solusi yang berbeda yang eksponensial n .

35.4 Pengacakan dan pemrograman linear

Pada bagian ini , kita mempelajari dua teknik yang berguna dalam merancang pendekatan algoritma : pengacakan dan pemrograman linear . Kami akan memberikan secara acak sederhana algoritma untuk versi optimasi dari 3 - CNF satisfiability , dan kemudian kita akan menggunakan linear pemrograman untuk membantu merancang algoritma pendekatan untuk versi tertimbang vertexcover yang masalah . Bagian ini hanya goresan permukaan dari kedua teknik yang kuat . itu Catatan bab memberikan referensi untuk studi lebih lanjut dari bidang ini . Algoritma pendekatan acak untuk MAX - 3 - CNF satisfiability Sama seperti ada algoritma acak yang menghitung solusi yang tepat , ada acak algoritma yang menghitung perkiraan solusi . Kita mengatakan bahwa algoritma acak untuk masalah memiliki rasio perkiraan ( n ) jika , untuk masukan apapun dari ukuran n , biaya C diharapkan solusi yang dihasilkan oleh algoritma acak adalah dalam faktor (n) dari biaya C * dari solusi optimal: