BerandaComputers and TechnologyDesain Algoritma Fungsional, Bagian 1: Algoritma Greedy

Desain Algoritma Fungsional, Bagian 1: Algoritma Greedy

Ini adalah bagian tengah dari artikel tiga bagian yang menjelaskan pendekatan yang Richard Bird dan saya mulai menggunakan pemrograman fungsional untuk desain algoritme dalam buku terbaru kami Desain Algoritme dengan Haskell .

Bagian 0 membandingkan pengembangan algoritme di a gaya fungsional dengan aktivitas terkait menggunakan bahasa imperatif. Pada bagian ini, kita melihat bagaimana pendekatan fungsional dapat diterapkan pada kelas algoritma rakus : ini dapat digunakan jika karakteristik suatu masalah memungkinkan tercapainya solusi optimal secara global dengan membuat serangkaian langkah optimal secara lokal. Algoritme serakah sering kali sangat sederhana, tetapi bukti bahwa algoritme tersebut benar-benar menghasilkan solusi yang optimal secara global bisa sangat rumit. Bagian terakhir 2 menyajikan kebaruan utama buku ini: langkah di luar murni FP untuk mengakui penggunaan fungsi nondeterministik yang hati-hati dan terbatas, yang mengubah perlu untuk situasi tipikal ketika pemesanan solusi yang dioptimalkan mengakui hubungan.

Algoritme serakah

Mari kita lihat algoritme serakah sebagai contoh yang lebih menarik. Kami akan mempertimbangkan algoritma yang membangun satu kandidat optimal dari kumpulan komponen . Contoh termasuk pengkodean Huffman (pengkodean terpendek yang dibuat dari yang diberikan simbol ), pemutusan garis (paling tidak boros paragraf dibangun dari yang diberikan kata-kata ), pohon rentang biaya minimum lagi (yang paling ringan pohon rentang dibangun dari tepi yang diberikan ), dan membuat perubahan (sedikit segenggam koin dibangun dari denominasi yang diberikan ).

Pendekatan serakah mengumpulkan kandidat yang optimal selangkah demi selangkah dari komponen yang diberikan, mempertahankan hanya satu parsial kandidat di seluruh: “berpikir global, bertindak secara lokal”. Ini biasanya mengarah pada algoritme sederhana, tetapi sering kali algoritme dengan bukti kebenaran yang rumit.

Masalahnya dapat ditentukan saat menghitung kandidat biaya minimum dari komponen yang diberikan:

 displaystyle  begin {array} {@ { } l}  mathit {mcc} :: [mathit{Component}]  rightarrow  mathit {Kandidat} \  mathit {mcc}= mathit {minWith} ;  mathit {cost}  cdot  mathit {kandidat}  end { larik}

Di sini, {mathit{minWith}} memilih dari daftar yang tidak kosong elemen minimal (paling kiri) menurut fungsi biaya yang diberikan:

 displaystyle  begin {array} {@ { } l}  mathit {minWith} ::  mathit {Ord} ;  beta  Rightarrow ( alpha  rightarrow  beta)  rightarrow [alpha]  rightarrow  alpha \  mathit {minWith} ; f= mathit {foldr1} ; ( mathit {minBy ; f}) \  quad  mathbf {di mana} ;  mathit {minBy} ; f ; a ; b= mathbf {if} ; f ; a  le f ; b ;  mathbf {lalu} ; a ;  mathbf {else} ; b  end {larik}

({mathit{foldr1}} adalah fungsi Haskell standar untuk menggabungkan daftar yang tidak kosong). Kami akan menganggap bahwa {mathit{candidates}} dapat ditulis sebagai turunan dari {mathit{foldr}}:

 displaystyle  begin {array} {@ { } l}  mathit {kandidat} :: [mathit{Component}]  rightarrow [mathit{Candidate}] \  mathit {kandidat}= mathit {foldr} ;  mathit {step} ; c_0 \  quad  mathbf { di mana} ;  mathit {step} ; a ; c= mathit {concat} ; ( mathit {map} ; ( mathit {extended} ; a) ; c)  end {array}

menyusun daftar calon tidak kosong yang terbatas, dimulai dengan calon awal yang sepele {c_0 :: mathit{Candidate}}, dan menggunakan fungsi { mathit { memperpanjang} ::  mathit {Komponen}  rightarrow  mathit {Kandidat}  rightarrow [mathit{Candidate}]} bahwa memperluas kandidat tunggal dengan satu komponen dalam semua cara yang memungkinkan. (Buku ini juga mempertimbangkan masalah di mana {mathit{candidates}} menggunakan pola rekursi yang berbeda.)

Misalnya, pertimbangkan untuk mengurutkan string: komponennya adalah karakter, dan kandidat adalah string, permutasi dari komponen tersebut. Kandidat awal yang sepele {c_0=mbox{``,''}} adalah string kosong, dan diperpanjang oleh setiap komponen secara bergantian dengan semua cara yang memungkinkan:

 displaystyle  mathit {memperpanjang} ; x ; c=[ c_1 mathbin{{+}!!!{+}} [x]  mathbin {{+} ! ! ! {+}} c_2  mid n  leftarrow [0 .. mathit{length};c],  mathbf {let} ; (c_1, c_2)= mathit {splitAt} ; n ; c]

Jadi { mathit {expand} ;  mbox {. Biaya yang diminimalkan adalah hitungan inversi , jumlah pasangan rusak dalam permutasi:

 displaystyle  mathit {ic} ; c= mathit {length} ; [(x,y) mid x:c' leftarrow mathit{tails};c, y:c'' leftarrow mathit{tails};c', x>y ] ” src=”http://s0.wp.com/latex.php?latex=%5Cdisplaystyle+%5Cmathit%7Bic%7D%5C%3Bc+%3D+%5Cmathit%7Blength%7D%5C%3B%5B%28x%2Cy%29+%5Cmid+x%3Ac%27+%5Cleftarrow+%5Cmathit%7Btails%7D%5C%3Bc%2C+y%3Ac%27%27+%5Cleftarrow+%5Cmathit%7Btails%7D%5C%3Bc%27%2C+x%3Ey+%5D+&bg=ffffff&fg=000000&s=0″ title=”  displaystyle  mathit {ic} ; c= mathit { panjang} ; [(x,y) mid x:c’ leftarrow mathit{tails};c, y:c” leftarrow mathit{tails};c’, x>y ] “></p>
</blockquote>
<h2> Menghitung algoritma serakah </h2>
<p> Kita dapat menghitung algoritma rakus untuk menghitung kandidat biaya-minimum dengan menggabungkan pilihan <img alt= dengan generasi {mathit{candidates}}, sehingga kami hanya mempertahankan satu kandidat di setiap langkah. Karena proses pembuatan merupakan turunan dari {mathit{foldr}}, kami menggunakan hukum fusi:

displaystyle h cdot mathit{foldr};f;e=mathit{foldr};f';e' quadLeftarrowquad h;(f;a;b)=f';a;(h;b) land h;e=e'

Sekarang {h} adalah {mathit{minWith};mathit{cost}}, {f} adalah {mathit{step}}, {e} adalah {[c_0]}, {e'} adalah {c_0}, dan kami harus membuat fungsi {mathit{gstep}}, “langkah serakah”, untuk memainkan peran {f'} – yaitu, untuk memuaskan

displaystyle mathit{minWith};mathit{cost};(mathit{step};x;cs)=mathit{gstep};x;(mathit{minWith};mathit{cost};cs)

Kami menghitung:

displaystyle begin{array}{@{}l} quad mathit{minWith};mathit{cost};(mathit{step};x;mathit{cs}) \=qquad { mbox{definition of }mathit{step} } \ quad mathit{minWith};mathit{cost};(mathit{concat};(mathit{map};(mathit{extend};x);mathit{cs})) \=qquad { mbox{distributive law} } \ quad mathit{minWith};mathit{cost};(mathit{map};(mathit{minWith};mathit{cost});(mathit{map};(mathit{extend};x);mathit{cs})) \=qquad { mathit{map}mbox{ distributes over composition} } \ quad mathit{minWith};mathit{cost};(mathit{map};(mathit{minWith};mathit{cost} cdot mathit{extend};x);mathit{cs}) \=qquad { mbox{define }mathit{gstep};x=mathit{minWith};mathit{cost} cdot mathit{extend};x } \ quad mathit{minWith};mathit{cost};(mathit{map};(mathit{gstep};x);mathit{cs}) \=qquad { mbox{greedy condition} } \ quad mathit{gstep};x;(mathit{minWith};mathit{cost};mathit{cs}) end{array}

Langkah pertama adalah mengungkap definisi fungsi {mathit{step}}. Langkah kedua adalah “hukum pembukuan”: untuk menggabungkan koleksi koleksi, baik menggabungkannya menjadi satu koleksi besar untuk digabungkan, atau menggabungkan setiap subkoleksi dan menggabungkan hasil antara. Langkah ketiga menggabungkan dua peta yang berurutan menjadi satu. Langkah keempat hanya memberi nama subterm {mathit{minWith};mathit{cost} cdot mathit{extend};x}. Langkah kelima

displaystyle mathit{minWith};mathit{cost};(mathit{map};(mathit{gstep};x);mathit{cs})=mathit{gstep};x;(mathit{minWith};mathit{cost};mathit{cs})

adalah angan-angan: bahwa mengambil kandidat terakhir terbaik yang diperoleh dengan membuat langkah serakah dari masing-masing kumpulan kandidat awal memberikan hasil yang sama seperti mengambil langkah serakah dari satu inisial terbaik kandidat. Sebutlah angan-angan ini sebagai kondisi serakah .

Intinya adalah bahwa kondisi serakah saja sudah cukup untuk memenuhi premis hukum fusi; setiap langkah lain dalam kalkulasi valid secara universal. Jika kondisi greedy terpenuhi, maka kita memiliki algoritma greedy

displaystyle mathit{mcc}=mathit{foldr};mathit{gstep};c_0 quad mathbf{where};mathit{gstep};x=mathit{minWith};mathit{cost} cdot mathit{extend};x

untuk menemukan kandidat biaya minimum. Dengan kata lain, dari kandidat yang kosong {c_0}, buat satu langkah serakah dengan setiap komponen {x} gantinya. Satu langkah serakah terdiri dari mempertimbangkan setiap cara yang mungkin untuk memperluas kandidat saat ini, dan mengambil yang terbaik (secara lokal) dari mereka.

Penyortiran serakah

Jadi, apakah kondisi rakus berlaku untuk penyortiran? Sayangnya, tidak demikian. Pertimbangkan dua kandidat parsial “eabc” dan “cbae” (dalam urutan itu), masing-masing dengan hitungan inversi 3, dan anggaplah bahwa komponen berikutnya adalah ‘d’. Karena kedua kandidat ini terikat pada hitungan inversi, ini adalah pilihan sewenang-wenang yang ‘minimal’; kami {mathit{minWith}} kebetulan memilih elemen minimal paling kiri, yaitu “eabc”. Namun extension terbaik dari “eabc” dengan ‘d’ adalah “eabcd”, dengan inversion count 4, sedangkan extension terbaik dari “cbae” dengan ‘d’ adalah “cbade”, dengan inversion count 3. Kandidat awal terbaik tunggal “ eabc ”tidak mengarah ke kandidat final terbaik.

Inti dari kendala tersebut adalah bahwa pengurutan dengan hitungan inversi tidaklah linier, karena tidak antisimetris: dua permutasi yang berbeda dapat memiliki hitungan inversi yang sama. Saya dapat memikirkan tiga kemungkinan perbaikan.

Perbaikan pertama adalah terkadang hubungan semacam ini tidak dapat terjadi dalam konteks. Secara khusus, untuk pengurutan, selalu ada permutasi biaya minimal yang unik, yaitu permutasi yang diurutkan (setidaknya, unik ketika elemennya sendiri diurutkan secara linier). Meskipun “eabc” dan “cbae” terikat, mereka dan semua permutasi lainnya kalah dari “abce”. Seseorang dapat menyempurnakan kalkulasi algoritme rakus untuk mempertimbangkan konteks ini, yang akan mengatasi hambatan untuk penyortiran. Namun, perbaikan ini tidak berfungsi untuk semua algoritme serakah.

Perbaikan kedua adalah mengubah fungsi biaya. Dalam hal penyortiran, kami dapat beralih dari {mathit{ic}} ke – tidak ada yang mengatakan bahwa ‘biaya’ harus berupa angka. Ini memperbaiki masalah dengan satu pukulan! Masalahnya adalah menemukan permutasi terkecil secara leksikal (yaitu, permutasi yang diurutkan), yang juga akan menjadi permutasi dengan jumlah inversi minimal (yaitu nol). Secara umum, urutan diperhalus menjadi urutan linier, seringkali dengan menambahkan dimensi ke fungsi biaya. Namun, saya pikir ini benar-benar curang: mengurangi spesifikasi dalam penerapan yang dimaksudkan.

Perbaikan ketiga, dan yang diambil dalam buku ini, adalah mengizinkan fungsi nondeterministik di beberapa tempat yang dikontrol dengan cermat. Secara khusus, ketika ada seri, kami menganggap semua sebagian optimal calon, bukan salah satu dari mereka. Perbaikan ketiga ini dijelaskan di Bagian 2 artikel.

Bio : Jeremy Gibbons adalah Profesor Komputasi di Universitas Oxford, di mana dia memimpin kelompok penelitian Aljabar Pemrograman dan mantan Wakil Kepala Departemen. Dia menjabat sebagai Wakil Ketua kemudian Wakil Ketua ACM SIGPLAN , dengan fokus khusus pada Akses Terbuka. Dia juga Pemimpin Redaksi Jurnal Pemrograman Fungsional , Ketua SC ICFP , di Dewan Penasihat PACMPL , editor Komposisi , dan mantan Ketua
Kelompok Kerja IFIP 2.1 tentang Bahasa dan Kalkulus Algoritmik .

Penafian: Ini posting ditulis oleh kontributor individu untuk berbagi pemikiran mereka di blog SIGPLAN untuk kepentingan komunitas. Setiap pandangan atau opini yang diwakili dalam blog ini bersifat pribadi, hanya milik penulis blog dan tidak mewakili ACM SIGPLAN atau organisasi induknya, ACM.

Read More

RELATED ARTICLES

LEAVE A REPLY

Please enter your comment!
Please enter your name here

Most Popular

Recent Comments