Apakah setiap algoritma serakah memiliki struktur matroid?

Hal ini juga ditetapkan bahwa untuk setiap matroid $M$ dan fungsi berat badan $w$ , ada keluar algoritma $\mbox{GreedyBasis}(M,w)$ yang mengembalikan secara berat maksimum $M$ . Jadi, apakah arah sebaliknya juga benar? Artinya, jika ada beberapa algoritma serakah, maka harus ada beberapa struktur matroid juga.

Algoritma serakah bukanlah konsep yang didefinisikan secara formal. Ada berbagai model yang mencoba menangkap gagasan intuitif ini tetapi tidak ada konsensus tentang apa yang dimaksud dengan algoritma serakah. Kecuali Anda menentukan definisi formal tentang apa yang Anda maksud dengan algoritma serakah, pertanyaan tidak dapat dijawab sebagai ya atau tidak.

Ada generalisasi dari matroid yang disebut greedoid yang terinspirasi oleh algoritma serakah yang mungkin ingin Anda lihat.

Sebenarnya, deskripsi lengkap dan umum dari masalah yang dapat diselesaikan dengan algoritma serakah adalah embedding matroid , yang menggeneralisasi baik konsep matroid maupun greedoid . Jawabannya adalah tidak - masalah yang dipecahkan oleh algoritma serakah tidak perlu memiliki struktur matroid, tetapi akan memiliki struktur embedding matroid (yang, sayangnya, jauh lebih rumit).

Model mental untuk beberapa hal ini mungkin menemukan pohon rentang minimum. Struktur yang digunakan oleh algoritma Kruskal adalah matroid, tetapi yang digunakan oleh algoritma Prim (yang membutuhkan simpul awal) tidak. (Namun demikian, ini adalah greedoid — dan embrio matroid.)

$(S,\mathcal{C})$$S$$\mathcal{C}$$S$ $f:2^S\rightarrow\mathbb{R}$$S$

Algoritma serakah, didefinisikan dalam istilah formalisme ini, cukup sederhana: Anda mulai dengan set kosong, dan berturut-turut menambahkan satu elemen hingga Anda mencapai basis, selalu memastikan bahwa (i) set Anda layak pada setiap langkah, dan ( ii) elemen yang Anda tambahkan memaksimalkan fungsi objektif dari hasil yang dihasilkan, wrt. semua elemen alternatif yang bisa Anda tambahkan. (Yaitu, secara konseptual, Anda mencoba menambahkan semua alternatif yang layak, dan memilih yang menghasilkan nilai objektif tertinggi.)

Anda bisa, mungkin, berpendapat bahwa mungkin ada bentuk lain dari algoritma serakah, tetapi ada beberapa buku teks pada algoritma dan optimasi kombinatorial yang menggambarkan set-sistem algoritma berbasis sebagai yang algoritma serakah. Itu tidak menghalangi Anda untuk menggambarkan sesuatu yang tidak cocok, tetapi masih bisa disebut serakah, saya kira. (Namun, ini tidak mencakup apa pun yang berpotensi memiliki struktur matroid, misalnya, meskipun jauh lebih umum.)

Apa Helman et al. lakukan adalah mereka menggambarkan kapan algoritma ini akan bekerja. Lebih spesifik:

1. Mereka menunjukkan bahwa untuk fungsi objektif linier (di mana nilai obyektif adalah jumlah bobot elemen), algoritma serakah akan bekerja tepat pada struktur yang mereka definisikan sebagai penanaman matroid;

2. Mereka memberikan karakterisasi yang sama untuk apa yang disebut tujuan bottleneck (di mana nilai obyektif set adalah sama dengan minimum di atas bobot elemen individu); dan

3. Mereka memberikan karakterisasi yang tepat dari fungsi tujuan mana (di luar yang linier) dioptimalkan oleh algoritma serakah pada pernikahan matroid.

Pertimbangkan masalah-masalah berikut: EURO-CHAIN-CHAINING: Dengan jumlah tak terbatas 1,2,5,10 euro, bayar X euro menggunakan sesedikit mungkin note. Ini dapat diatasi dengan menggunakan algoritma serakah, yang mengambil catatan sebesar mungkin. Tetapi tidak ada struktur matroid dalam masalah ini.

CAKUPAN LUBANG: Ada lubang di posisi x_1, x_2, ..., x_n. Anda memiliki panjang 10 cm. Menambal lubang menggunakan patch sesedikit mungkin. Sekali lagi ini dapat diselesaikan dengan cara serakah (cukup tambal sulam setepat mungkin), tetapi tidak ada struktur matroid.