Algoritma pendekatan yang digunakan dalam algoritma yang tepat

Algoritme pendekatan dapat memberikan output hingga beberapa faktor konstan. Ini sedikit kurang memuaskan daripada algoritma yang tepat.

Namun, faktor konstan diabaikan dalam kompleksitas waktu.

Jadi saya bertanya-tanya apakah trik berikut ini mungkin atau digunakan, untuk menyelesaikan beberapa masalah :$B \circ A$

1. Gunakan algoritme penyelesaian pemecahan masalah untuk mendapatkan solusi S dalam faktor konstan;$A$$S$
2. Gunakan algoritma yang tepat, menyelesaikan masalah , yang runtime tergantung pada bobot S tetapi berfungsi selama S adalah solusi yang benar.$B$$S$$S$

Dengan cara ini aproksimasi adalah "sub-prosedur" dari suatu algoritma yang tepat, dan faktor konstan yang hilang pada langkah 1 ditelan dalam langkah 2.

Contoh dari kompleksitas parameter adalah kernelisasi untuk masalah penutup verteks menggunakan teorema Nemhauser dan Trotter.

Dalam masalah vertex cover minimum, kita diberi grafik G yang tidak diarahkan, dan kita perlu menemukan vertex cover G dengan ukuran minimum. Penutup vertex dari grafik yang tidak diarahkan adalah subset verteks yang menyentuh semua tepi.

Berikut ini adalah algoritma yang tepat yang menggunakan pendekatan pada fase pertama.

Fase 1: Mengatur formulasi pemrograman linier bilangan bulat dari masalah penutup simpul minimum . Diketahui (atau mudah ditunjukkan) bahwa solusi optimal dasar relaksasi pemrograman linier adalah setengah integral (yaitu, setiap koordinat adalah 0, 1, atau 1/2). Solusi optimal dasar seperti itu dapat ditemukan oleh algoritma waktu polinomial biasa untuk pemrograman linier (atau dalam kasus khusus ini, kita dapat merumuskannya sebagai masalah aliran jaringan, sehingga kita dapat menyelesaikannya secara kombinatorial dalam waktu polinomial). Memiliki solusi optimal dasar seperti itu, kami mengumpulkannya untuk mendapatkan solusi yang layak untuk masalah pemrograman linear integer asli. Misalkan S adalah subset vertex yang sesuai. Baik untuk dicatat bahwa S adalah 2-perkiraan dari contoh titik simpul minimum yang diberikan.

Fase 2: Temukan penutup vertex minimum dalam subgraph yang disebabkan oleh S (misalnya dengan pencarian lengkap). Teorema oleh Nemhauser dan Trotter menyatakan bahwa subgraph ini berisi solusi optimal dari grafik input asli. Jadi, kebenaran dari pendekatan ini mengikuti.

Anda dapat membaca buku oleh Niedermeier tentang algoritma parameter-tetap untuk algoritma ini.

Salah satu contoh terkait dengan dekomposisi pohon dan grafik pohon kecil.

$B$

$B$$A$

$A$$A$$A$$A$$B$

$B$$A$

$B$$A$$A$$B$

Contoh dari algoritma pendekatan yang menyatu dengan solusi yang tepat adalah algoritma Ellipsoid untuk menyelesaikan piringan hitam - jika koefisiennya rasional, maka seseorang dapat menghitung jarak minimum antara dua simpul dari polytope yang layak. Sekarang, algoritma ellipsoid menghitung berulang kali elliposoid yang lebih kecil dan lebih kecil yang harus mengandung solusi optimal. Setelah elliposoid cukup kecil untuk mengandung hanya satu simpul tunggal, Anda pada dasarnya menemukan simpul optimal. Inilah sebabnya mengapa LP polinomialnya lemah.

$k$

Akhirnya, pergi lebih jauh bidang - banyak algoritma yang mengikuti teknik perubahan (mengambil sampel acak - dan kemudian melakukan beberapa perbaikan untuk mendapatkan apa yang Anda inginkan) termasuk dalam kerangka kerja seperti itu. Salah satu contoh lucu adalah algoritma untuk menghitung median menggunakan random sampling (lihat buku oleh Motwani dan Raghavan). Ada banyak contoh seperti itu - bisa dibilang banyak dari algoritma inkremental acak dalam Komputasi Geometri termasuk dalam kerangka ini.

Banyak algoritma yang peka terhadap hasil menggunakan teknik ini. Sebagai contoh, berikut adalah masalah sederhana yang dapat digunakan teknik ini:

Soal . Anda diberi larik A [1 .. n ] di mana setiap elemen berada pada posisi k paling jauh dari posisi yang seharusnya berada jika A diurutkan.

Sebagai contoh, A [1..7] yang ditunjukkan di bawah ini bisa menjadi larik input untuk k = 2.

Sumber Masalah: Arsip Algo Muse .