Bagaimana membuktikan algoritma serakah itu benar

Saya memiliki algoritma serakah yang saya duga mungkin benar, tetapi saya tidak yakin. Bagaimana saya memeriksa apakah itu benar? Apa teknik yang digunakan untuk membuktikan algoritma serakah yang benar? Apakah ada pola atau teknik yang umum?

^{Saya berharap ini akan menjadi pertanyaan referensi yang dapat digunakan untuk mengarahkan pemula; karenanya cakupannya lebih luas dari biasanya. Harap berhati-hati untuk memberikan jawaban umum, yang disajikan secara didaktis yang diilustrasikan oleh setidaknya satu contoh tetapi tetap mencakup banyak situasi. Terima kasih!}

Pada akhirnya, Anda akan membutuhkan bukti matematika dari kebenaran. Saya akan membahas beberapa teknik pembuktian di bawah ini, tetapi pertama-tama, sebelum menyelami itu, biarkan saya menghemat waktu: sebelum Anda mencari bukti, cobalah pengujian acak.

Pengujian acak

Sebagai langkah pertama, saya sarankan Anda menggunakan pengujian acak untuk menguji algoritma Anda. Sungguh menakjubkan betapa efektifnya ini: dalam pengalaman saya, untuk algoritma serakah, pengujian acak tampaknya sangat efektif. Luangkan 5 menit untuk mengkodekan algoritme Anda, dan Anda mungkin menghemat satu atau dua jam untuk mencoba memberikan bukti.

Ide dasarnya sederhana: terapkan algoritma Anda. Juga, terapkan algoritma referensi yang Anda tahu benar (mis., Yang secara menyeluruh mencoba semua kemungkinan dan mengambil yang terbaik). Tidak apa-apa jika algoritma referensi Anda tidak efisien secara asimptot, karena Anda hanya akan menjalankan ini pada contoh masalah kecil. Kemudian, buat secara acak satu juta contoh masalah kecil, jalankan kedua algoritma pada masing-masing, dan periksa apakah algoritma kandidat Anda memberikan jawaban yang benar dalam setiap kasus.

Secara empiris, jika calon algoritma serakah Anda salah, biasanya Anda akan sering menemukan ini selama pengujian acak. Jika tampaknya benar pada semua kasus uji, maka Anda harus beralih ke langkah berikutnya: datang dengan bukti matematika dari kebenaran.

Bukti matematis tentang kebenaran

OK, jadi kita perlu membuktikan algoritma serakah kita benar: bahwa ia menghasilkan solusi optimal (atau, jika ada beberapa solusi optimal yang sama-sama baik, bahwa itu menghasilkan salah satunya).

Prinsip dasarnya adalah prinsip intuitif:

Prinsip: Jika Anda tidak pernah membuat pilihan yang buruk, Anda akan baik-baik saja.

Algoritma serakah biasanya melibatkan urutan pilihan. Strategi bukti dasar adalah bahwa kita akan mencoba membuktikan bahwa algoritma tidak pernah membuat pilihan yang buruk. Algoritma serakah tidak dapat mundur - setelah mereka membuat pilihan, mereka berkomitmen dan tidak akan pernah membatalkan pilihan itu - jadi sangat penting bahwa mereka tidak pernah membuat pilihan yang buruk.

Apa yang akan dianggap sebagai pilihan yang baik? Jika ada satu solusi optimal, mudah untuk melihat apa yang merupakan pilihan yang baik: setiap pilihan yang identik dengan yang dibuat oleh solusi optimal. Dengan kata lain, kami akan mencoba membuktikan bahwa, pada setiap tahap dalam pelaksanaan algoritma serakah, urutan pilihan yang dibuat oleh algoritma sejauh ini sama persis dengan beberapa awalan dari solusi optimal. Jika ada beberapa solusi optimal yang sama baiknya, pilihan yang baik adalah yang konsisten dengan setidaknya satu optima. Dengan kata lain, jika urutan algoritme pilihan sejauh ini cocok dengan awalan salah satu solusi optimal, semuanya baik-baik saja sejauh ini (belum ada yang salah).

Untuk menyederhanakan kehidupan dan menghilangkan gangguan, mari kita fokus pada kasus di mana tidak ada ikatan: ada solusi optimal tunggal yang unik. Semua mesin akan terbawa ke kasus di mana ada beberapa optima yang sama baiknya tanpa perubahan mendasar, tetapi Anda harus sedikit lebih berhati-hati tentang detail teknis. Mulailah dengan mengabaikan detail tersebut dan berfokus pada kasus di mana solusi optimal adalah unik; itu akan membantu Anda fokus pada apa yang penting.

Ada pola bukti yang sangat umum yang kami gunakan. Kami akan bekerja keras untuk membuktikan properti algoritma berikut:

Klaim: Misalkan adalah solusi keluaran oleh algoritma dan O menjadi solusi optimal. Jika S adalah berbeda dari O , maka kita dapat men-tweak O untuk mendapatkan solusi lain O * yang berbeda dari O dan ketat lebih baik dari O .$S$$O$$S$$O$$O$$O^*$$O$$O$

Perhatikan mengapa ini berguna. Jika klaim itu benar, berarti algoritma tersebut benar. Ini pada dasarnya adalah bukti oleh kontradiksi. Baik sama dengan O atau berbeda. Jika berbeda, maka kita dapat menemukan solusi lain O ∗ yang benar-benar lebih baik daripada O - tetapi itu kontradiksi, karena kami mendefinisikan O sebagai solusi optimal dan tidak mungkin ada solusi yang lebih baik dari itu. Jadi kami terpaksa menyimpulkan bahwa S tidak bisa berbeda dari O ; S harus selalu sama dengan $S$$O$$O^*$$O$$O$$S$$O$$S$$O$, yaitu, algoritma serakah selalu menghasilkan solusi yang benar. Jika kami dapat membuktikan klaim di atas, maka kami telah membuktikan algoritma kami benar.

Baik. Jadi bagaimana kita membuktikan klaim itu? Kami menganggap solusi sebagai vektor ( S 1 , ... , S n ) yang sesuai dengan urutan pilihan n yang dibuat oleh algoritma, dan kami juga memikirkan solusi optimal O sebagai vektor ( O 1 , ... , O n ) sesuai dengan urutan pilihan yang akan menyebabkan O . Jika S berbeda dari O , harus ada beberapa indeks i di mana S i$S$$(S_1,\dots,S_n)$$n$$O$$(O_1,\dots,O_n)$$O$$S$$O$$i$ ; kami akan fokus pada i seperti terkecil. Kemudian, kita akan men-tweak O dengan mengubah O sedikit di i posisi th pertandingan S i , yaitu, kita akan men-tweak solusi optimal O dengan mengubah i th pilihan dengan yang dipilih oleh algoritma serakah, dan kemudian kami akan menunjukkan bahwa ini mengarah ke solusi yang lebih baik. Secara khusus, kami akan mendefinisikan O ∗ menjadi sesuatu seperti$S_i \ne O_i$$i$$O$$O$$i$$S_i$$O$$i$$O^*$

kecuali yang sering kita harus memodifikasi bagian sedikit untuk menjaga konsistensi global. Bagian dari strategi pembuktian melibatkan beberapa kepintaran dalam mendefinisikan O ∗ dengan tepat. Kemudian, daging bukti akan di entah bagaimana menggunakan fakta-fakta tentang algoritma dan masalah untuk menunjukkan bahwa O * ketat baik dari $O_{i+1},O_{i+2},\dots,O_n$$O^*$$O^*$$O$; di situlah Anda membutuhkan wawasan khusus masalah. Pada titik tertentu, Anda perlu menyelami rincian masalah spesifik Anda. Tapi ini memberi Anda rasa struktur bukti khas kebenaran untuk algoritma serakah.

Contoh sederhana: Subset dengan jumlah maksimal

Ini mungkin lebih mudah dipahami dengan bekerja melalui contoh sederhana secara rinci. Mari kita pertimbangkan masalah berikut ini:

Input: Sebuah set bilangan bulat, integer k Output: Sebuah set S ⊆ U ukuran k yang jumlahnya adalah sebagai besar mungkin$U$$k$
$S \subseteq U$$k$

Ada algoritma serakah alami untuk masalah ini:

1. Set .$S := \emptyset$
2. Untuk : $i := 1,2,\dots,k$
   • Biarkan menjadi angka terbesar di U yang belum diambil (yaitu, angka terbesar ke- i di U ). Add x i ke S .$x_i$$U$$i$$U$$x_i$$S$

Pengujian acak menunjukkan ini selalu memberikan solusi optimal, jadi mari kita secara formal membuktikan bahwa algoritma ini benar. Perhatikan bahwa solusi optimal adalah unik, jadi kami tidak perlu khawatir tentang ikatan. Mari kita buktikan klaim yang diuraikan di atas:

Klaim: Misalkan adalah solusi keluaran oleh algoritma ini pada input U , k , dan O solusi optimal. Jika S ≠ O , maka kita dapat membangun solusi lain O * yang jumlahnya bahkan lebih besar dari O .$S$$U,k$$O$$S \ne O$$O^*$$O$

Bukti. Asumsikan , dan membiarkan saya menjadi indeks pertama iterasi mana x i ∉ O . (Indeks seperti itu saya harus ada, karena kita telah mengasumsikan S ≠ O dan oleh definisi algoritma kita memiliki S = { x 1 , ... , x k } .) Karena (dengan asumsi) saya minimal, kita harus memiliki x 1 , … , x i - 1 ∈ O , dan khususnya,$S \ne O$$i$$x_i \notin O$$i$$S \ne O$$S=\{x_1,\dots,x_k\}$$i$$x_1,\dots,x_{i-1} \in O$ memiliki bentuk O = { x 1 , x 2 , ... , x i - 1 , x ′ i , x ′ i + 1 , ... , x ′ n } , di mana angka x 1 , ... , x i - 1 , x ′ i , … , x ′ $O$$O=\{x_1,x_2,\dots,x_{i-1},x'_i,x'_{i+1},\dots,x'_n\}$$x_1,\dots,x_{i-1},x'_i,\dots,x'_n$terdaftar dalam urutan menurun. Melihat bagaimana algoritma memilih , kita melihat bahwa kita harus memiliki x i > x ′ j untuk semua j ≥ i . Secara khusus, x i > x ′ i . Jadi, tentukan O = O ∪ { x i } ∖ { x ′ i } , yaitu, kita memperoleh O ∗ dengan menghapus angka ke- i di $x_1,\dots,x_i$$x_i > x'_j$$j\ge i$$x_i > x'_i$$O^ = O \cup \{x_i\} \setminus \{x'_i\}$$O^*$$i$$O$dan menambahkan . Sekarang jumlah unsur O * adalah jumlah dari unsur O ditambah x i - x ' i , dan x i - x ' i > 0 , sehingga O * 's sum ketat lebih besar dari O ' sum s. Ini membuktikan klaim. $x_i$$O^*$$O$$x_i-x'_i$$x_i-x'_i>0$$O^*$$O$$\blacksquare$

Intuisi di sini adalah bahwa jika algoritma serakah pernah membuat pilihan yang tidak konsisten dengan , maka kita dapat membuktikan O bisa lebih baik jika dimodifikasi untuk memasukkan elemen yang dipilih oleh algoritma serakah pada tahap itu. Karena O adalah optimal, tidak mungkin ada cara untuk membuatnya lebih baik (itu akan menjadi kontradiksi), jadi satu-satunya kemungkinan yang tersisa adalah asumsi kami salah: dengan kata lain, algoritma serakah tidak akan pernah membuat pilihan yang tidak sesuai dengan O .$O$$O$$O$$O$

Argumen ini sering disebut argumen pertukaran atau pertukaran lemma . Kami menemukan tempat pertama di mana solusi optimal berbeda dari solusi serakah dan kami membayangkan menukar elemen untuk pilihan serakah yang sesuai (ditukar x ′ i untuk x i ). Beberapa analisis menunjukkan bahwa pertukaran ini hanya dapat meningkatkan solusi optimal - tetapi menurut definisi, solusi optimal tidak dapat ditingkatkan. Jadi satu-satunya kesimpulan adalah bahwa tidak boleh ada tempat di mana solusi optimal berbeda dari solusi serakah. Jika Anda memiliki masalah yang berbeda, cari peluang untuk menerapkan prinsip pertukaran ini dalam situasi spesifik Anda.$O$$x'_i$$x_i$

Saya akan menggunakan algoritma pengurutan sederhana sebagai contoh:

repeat:
  if there are adjacent items in the wrong order:
     pick one such pair and swap
  else
     break

Untuk membuktikan kebenarannya saya menggunakan dua langkah.

• Pertama saya tunjukkan bahwa algoritma selalu berakhir.
• Lalu saya tunjukkan bahwa solusi di mana ia berakhir adalah yang saya inginkan.

Untuk poin pertama, saya memilih fungsi biaya yang cocok yang saya dapat menunjukkan bahwa algoritma meningkatkannya di setiap langkah.

Untuk contoh ini saya memilih jumlah inversi dalam daftar input. Pembalikan dalam daftar adalah sepasang entri A [ i ] , A [ j ] sedemikian rupa sehingga A [ i ] > A [ j ] tetapi saya < j . Jumlah inversi selalu non-negatif dan daftar yang diurutkan memiliki 0 inversi.$A$$A[i]$$A[j]$$A[i] > A[j]$$i<j$

Menukar dua item yang berdekatan dengan jelas , A [ i + 1 ] yang berada di urutan yang salah menghilangkan inversi A [ i ] , A [ i + 1 ] tetapi membiarkan inversi lainnya tidak terpengaruh. Karenanya jumlah inversi berkurang di setiap iterasi.$A[i]$$A[i+1]$$A[i],A[i+1]$

Ini membuktikan bahwa algoritma akhirnya berakhir.

Jumlah inversi dalam daftar yang diurutkan adalah 0. Jika semuanya berjalan dengan baik, algoritma akan mengurangi jumlah inversi menjadi 0. Kita hanya perlu menunjukkan bahwa inversinya tidak terjebak dalam minimum lokal.

Saya biasanya membuktikan ini dengan kontradiksi. Saya berasumsi bahwa algoritma berhenti, tetapi solusinya tidak benar. Dalam contoh ini, artinya daftar tersebut belum diurutkan, tetapi tidak ada item yang berdekatan dalam urutan yang salah.

Jika daftar tidak diurutkan, setidaknya harus ada dua item yang tidak dalam posisi yang benar. Misalkan dan A [ j ] , i < j , A [ i ] > A [ j ] adalah dua item tersebut, perbedaan antara i dan j adalah minimal. Karena algoritma tidak berhenti, mereka tidak berdekatan, jadi saya + 1 < j . Karena kami mengasumsikan minimal, A [ i ] < A $A[i]$$A[j]$$i<j$$A[i]>A[j]$$i$$j$$i+1 < j$ dan A [ i + 1 ] < A [ j ] , tetapi kemudian A [ i ] < A [ j ] dan kami memiliki kontradiksi.$A[i]<A[i+1]$$A[i+1]<A[j]$$A[i]<A[j]$

Ini membuktikan bahwa algoritma hanya berhenti ketika daftar diurutkan. Dan karenanya kita sudah selesai.