Algoritma Greedy

Algoritma greedy membangun solusi secara bertahap dengan berulang kali membuat pilihan yang terlihat terbaik pada langkah saat ini, dan tepatnya benar ketika pilihan optimal lokal tersebut terbukti mengarah pada solusi optimal global.

Definition

Algoritma greedy membangun solusi melalui urutan pilihan, masing-masing dipilih untuk mengoptimalkan kriteria lokal tertentu, tidak pernah meninjau kembali pilihan sebelumnya; algoritma ini benar hanya ketika pilihan optimal lokal menghasilkan hasil optimal global.

Scope

Topik ini mencakup paradigma greedy: properti pilihan greedy dan substruktur optimal yang membenarkannya, teknik pembuktian standar (argumen pertukaran dan kerangka kerja matroid), serta algoritma greedy kanonis termasuk pengkodean Huffman, pohon rentang minimum (Kruskal dan Prim), jalur terpendek Dijkstra, dan penjadwalan interval. Ini juga membahas kapan strategi greedy hanya berfungsi sebagai heuristik perkiraan daripada metode yang tepat.

Core questions

• Apa itu properti pilihan greedy, dan bagaimana properti tersebut dibuktikan untuk masalah tertentu?
• Bagaimana argumen pertukaran menunjukkan bahwa pilihan greedy aman?
• Masalah mana yang memiliki struktur matroid yang menjamin optimalitas greedy?
• Kapan metode greedy hanya merupakan perkiraan daripada algoritma yang tepat?
• Bagaimana greedy dibandingkan dengan pemrograman dinamis untuk masalah yang sama?

Key concepts

• properti pilihan greedy
• substruktur optimal
• argumen pertukaran
• matroid
• pengkodean Huffman
• pohon rentang minimum
• penjadwalan interval
• knapsack fraksional

Key theories

Properti pilihan greedy dan argumen pertukaran

Suatu masalah memungkinkan solusi greedy ketika solusi optimal global selalu dapat dimodifikasi agar sesuai dengan pilihan pertama greedy tanpa kehilangan optimalitas; argumen pertukaran (atau 'greedy tetap unggul') memformalkan hal ini.

Matroid dan optimalitas greedy

Ketika solusi yang layak membentuk himpunan independen dari matroid berbobot, algoritma greedy selalu menemukan himpunan independen dengan bobot maksimum; ini menyatukan hasil seperti optimalitas algoritma pohon rentang minimum Kruskal.

Clinical relevance

Algoritma greedy menggerakkan sistem yang banyak digunakan: pengkodean Huffman dalam format kompresi data, algoritma pohon rentang minimum dalam desain jaringan, algoritma Dijkstra dalam perutean dan navigasi, serta penjadwalan greedy dan heuristik set-cover dalam sistem operasi dan alokasi sumber daya.

History

Penalaran greedy muncul dalam hasil klasik seperti algoritma pohon rentang minimum Kruskal (1956) dan Prim (1957), kode prefiks optimal Huffman (1952), dan algoritma jalur terpendek Dijkstra (1959). Penjelasan teoretis matroid tentang kapan metode greedy berhasil dikembangkan oleh Edmonds dan lainnya pada tahun 1960-an dan 1970-an.

Key figures

• David A. Huffman
• Joseph Kruskal
• Robert Prim
• Edsger W. Dijkstra

Seminal works

• dijkstra1959
• cormen2009

Frequently asked questions

Mengapa greedy berfungsi untuk knapsack fraksional tetapi tidak untuk knapsack 0/1?

Dalam knapsack fraksional, item dapat dibagi, sehingga mengambil item dengan nilai per bobot tertinggi terlebih dahulu selalu aman dan terbukti optimal. Dalam knapsack 0/1, item tidak dapat dibagi, pilihan greedy dapat menghalangi kombinasi yang lebih baik, dan pemrograman dinamis diperlukan untuk optimum yang tepat.

Bagaimana cara membuktikan bahwa algoritma greedy benar?

Dua teknik standar adalah argumen pertukaran, yang mengubah solusi optimal apa pun menjadi solusi greedy tanpa memperburuknya, dan argumen 'greedy tetap unggul', yang menunjukkan bahwa solusi parsial greedy setidaknya sama baiknya dengan solusi lain pada setiap langkah. Teori matroid memberikan kondisi yang cukup umum.