Apakah mungkin untuk membuktikan bahwa, untuk masalah tertentu, tidak ada algoritma serakah yang optimal ada?

Serakah adalah istilah non-formal, tetapi bisa jadi (tidak yakin, itu sebabnya saya bertanya) bahwa untuk masalah tertentu, kerakusan dapat dirumuskan secara matematis dan dengan demikian terbukti bahwa tidak ada algoritma serakah yang optimal ada. Apakah ini mungkin?

Hal paling sederhana untuk dilakukan adalah mengatur algoritma serakah untuk masalah tersebut, dan kemudian mencari contoh tandingan. Jika Anda menemukannya, Anda sudah mendapat jawaban. Kalau tidak, ada banyak cara untuk membuktikan bahwa ketamakan itu berhasil . Ada beberapa masalah dengan ini, tentu saja (seperti bagaimana secara khusus merumuskan algoritma serakah). Sedangkan untuk mengkarakterisasi masalah mana yang bisa dan masalah mana yang tidak bisa diselesaikan dengan rakus, ada jawaban umum untuk itu juga.

Bahkan, dalam makalah mereka "An Exact Characterization of Greedy Structures" ( SIAM J. Discrete Math . 6 , hlm. 274-283), Helman, Moret dan Shapiro memberikan deskripsi formal tentang hal ini (disebut embedding matroid , yang menggeneralisasi baik matroid dan greedoid). Dari abstrak: "Para penulis menyajikan karakterisasi tepat struktur di mana algoritma serakah menghasilkan solusi optimal."

Secara umum, algoritma serakah dapat dirumuskan dalam hal sistem set tertimbang . Anda memiliki himpunan (misalnya, bagian tepinya, dalam hal pohon rentang minimum), dan Anda memiliki himpunan himpunan bagian dari (pikirkan hutan yang mencakup sebagian, untuk masalah pohon merentang minimum). merupakan solusi yang parsial valid dibangun dengan menggabungkan elemen-elemen dari . Ada juga fungsi bobot, , yang memberi Anda bobot atau biaya elemen apa pun di . Kami biasanya menganggap ini linear — yaitu, setiap elemen dalamE F ⊆ 2 E E F E w F$(E,\mathcal{F},w)$$E$$\mathcal{F}\subseteq 2^E$$E$$\mathcal{F}$$E$$w$$\mathcal{F}$$E$memiliki bobot, dan bobot dari solusi (parsial) hanyalah jumlah dari bobot elemen. (Sebagai contoh, berat pohon spanning adalah jumlah dari bobot ujungnya.) Dalam konteks ini, Helman et al. menunjukkan bahwa yang berikut ini setara:

1. Untuk setiap fungsi objektif linier, memiliki basis optimal.$(E,\mathcal{F})$

2. $(E,\mathcal{F})$ adalah penyematan matroid.

3. Untuk setiap fungsi objektif linier, basis serakah adalah basis optimalnya.$(E,\mathcal{F})$

Dengan kata lain: Untuk struktur seperti ini (yang pada dasarnya mewujudkan jenis struktur yang biasanya dipikirkan ketika bekerja dengan keserakahan), tepatnya rangkaian hiasan matroid dapat diselesaikan dengan rakus.

Definisi embedding matroid tidak terlalu sulit, jadi membuktikan bahwa masalah yang diberikan adalah atau tidak embedding matroid tentu layak. The entri Wikipedia memberikan definisi cukup jelas. (Memahami bukti mengapa ini adalah struktur yang tepat dipecahkan oleh keserakahan — itu masalah lain sepenuhnya ...)

Jika masalah Anda dapat dirumuskan dalam hal pemilihan dari sistem set tertimbang dengan fungsi objektif linier, dan jika Anda dapat menunjukkan bahwa itu bukan embedded matroid, maka Anda telah menunjukkan bahwa itu tidak dapat diselesaikan dengan rakus, bahkan jika Anda belum Saya tidak dapat menemukan contoh tandingan. (Meskipun saya menduga menemukan contoh tandingan akan sedikit lebih mudah.)

Pendekatan ini bukan sepenuhnya tanpa masalah, saya kira. Seperti yang Anda katakan, gagasan umum tentang keserakahan agak informal, dan mungkin mungkin untuk menyesuaikannya sedemikian rupa sehingga formalisme sistem himpunan linear tidak berlaku.

Ya, ada pekerjaan seperti itu. Allan Borodin bersama rekan penulis mengembangkan teori di mana mereka memformalkan gagasan tentang keserakahan dan mendapatkan hasil yang dapat dicapai dengan rasio perkiraan. Mereka memperkenalkan kelas algoritma prioritas, yang menggeneralisasi algoritma serakah. Karya pertama mereka pada topik ini adalah makalah " (Incremental) Algoritma Prioritas ".

PS Paragraf sebelumnya menjawab pertanyaan yang berbeda: Apakah mungkin untuk membuktikan bahwa, untuk masalah yang diberikan, tidak ada algoritma serakah ada dengan rasio perkiraan kurang dari beberapa ? Apa yang menyangkut pertanyaan saya kira diasumsikan ada yang optimal berarti tepat sehingga pertanyaan terkait dengan masalah dalam P (Saya menganggap algoritma serakah memiliki kompleksitas polinomial meskipun saya kira ini tidak perlu) yang dikenal memiliki solusi dengan metode lain daripada yang serakah . Dan saya tidak tahu jawabannya.$1+\epsilon$

Untuk ivotron: jika Anda tidak mengartikan interpretasi pertama saya, saya akan menghapus jawaban ini.

Lihat ini juga: http://en.wikipedia.org/wiki/Greedoid