Cum respingi un algoritm greedy cu un contraexemplu
Verifică alegerea locală înainte să o numești optimă. Monedele 1, 3 și 4 arată de ce cea mai mare alegere disponibilă poate produce un rezultat mai slab.
În acest material
Un algoritm greedy, numit și lacom, face la fiecare pas o alegere locală considerată favorabilă și continuă fără să exploreze toate alternativele. Pentru unele probleme este optim. Pentru altele, alegerea aparent naturală poate bloca un rezultat mai bun.
Monedele oferă un test clar
Ai monede de valori 1,3,4, fiecare disponibilă de oricâte ori, și vrei suma 6 cu un număr minim de monede. Alegerea repetată a celei mai mari monede care încape produce 4+1+1, adică trei monede.
Soluția 3+3 folosește numai două monede. Prin urmare, regula greedy propusă nu este corectă pentru toate sistemele de valori. Un singur contraexemplu valid este suficient pentru a respinge afirmația de corectitudine generală.
Testele reușite nu sunt o demonstrație
Aceeași regulă funcționează pentru multe sume mici și pentru anumite sisteme de monede. Aceste reușite nu demonstrează că funcționează pentru orice set de valori. Trebuie să distingi proprietățile datelor din enunț de proprietățile observate în câteva exemple.
Când cineva propune o alegere locală, întreabă ce se pierde prin ea. În exemplu, alegerea lui 4 lasă restul 2, care cere două monede de 1. Alegerea inițială puțin mai mică, 3, permite completarea cu o singură monedă.
Cu monedele 1,3,4 și suma 6, alegerea greedy produce 4+1+1, trei monede. Soluția 3+3 folosește două monede și este mai bună.Mărește schema ↗
Cum cauți un contraexemplu
Începe cu intrări mici, unde poți enumera soluțiile. Construiește cazuri în care alegerea mare lasă un rest dificil, iar două alegeri medii se potrivesc exact. Compară rezultatul algoritmului cu un rezultat verificat independent.
Nu modifica regulile după fiecare test fără să formulezi noul algoritm precis. O colecție de excepții locale poate ascunde aceeași problemă de fond: lipsa unei proprietăți care să lege alegerea locală de un optim global.
Ce ar trebui să demonstrezi
O justificare greedy poate arăta că există întotdeauna o soluție optimă care începe cu alegerea propusă. Apoi problema rămasă trebuie să aibă aceeași structură. Acest tip de argument este mai puternic decât impresia că alegerea „pare cea mai bună”.
Dacă proprietatea nu există, programarea dinamică poate compara subproblemele relevante, în limitele permise. Alegerea metodei pornește de la cerință, limite și dovadă, nu de la faptul că un cod greedy ar fi mai scurt.
Continuă cu metoda greedy, programarea dinamică și complexitatea.
Întrebări frecvente
Ce înseamnă un algoritm greedy?
Un algoritm care face succesiv alegeri locale și continuă fără să exploreze toate alternativele. Faptul că alegerea pare bună pe moment nu demonstrează că rezultatul final este optim.
Alegerea celei mai mari monede dă mereu numărul minim de monede?
Nu pentru orice sistem de valori. Cu monede 1, 3 și 4 și suma 6, alegerea greedy dă 4+1+1, dar 3+3 folosește numai două monede.
Cum verific dacă o strategie greedy este corectă?
Caută întâi contraexemple mici, apoi construiește o demonstrație că alegerea locală poate aparține unei soluții optime. Trecerea câtorva exemple nu înlocuiește demonstrația.