Come individuare un algoritmo "avido"?

Question

Sto leggendo un tutorial sugli algoritmi "greedy" ma ho difficoltà a individuarli risolvendo problemi reali di "Top Coder".

Se I sa che un determinato problema può essere risolto con un algoritmo "greedy" è piuttosto semplice codificare la soluzione. Tuttavia, se non mi è stato detto che questo problema è "avido", non riesco a riconoscerlo.

Quali sono le proprietà e gli schemi comuni dei problemi risolti con algoritmi "grezzi"? Posso ridurli a uno dei noti problemi "avidi" (ad es. MST)?

Answer 1

Formalmente, dovresti provare la proprietà del matroide, naturalmente. Tuttavia, presumo che in termini di topcoder tu voglia piuttosto scoprire rapidamente se un problema può essere affrontato avidamente o no.

In tal caso, il punto più importante è lo optimal sub-structure property. Per questo, devi essere in grado di individuare che il problema può essere scomposto in sotto-problemi e che la loro soluzione ottimale è parte della soluzione ottimale dell'intero problema.

Naturalmente, i problemi golosi sono così diversi che è quasi impossibile offrire una risposta generale corretta alla tua domanda. Il mio miglior consiglio sarebbe quindi pensare da qualche parte lungo queste linee:

• Ho una scelta tra diverse alternative ad un certo punto?
• Questa scelta si traduce in problemi secondari che possono essere risolti individualmente?
• Potrò utilizzare la soluzione del sotto-problema per ricavare una soluzione per il problema generale?

Insieme a carichi e carichi di esperienza (dovevamo solo dirlo), questo dovrebbe aiutarti a individuare rapidamente problemi avidi. Naturalmente, alla fine si può classificare un problema come avido, il che non lo è. In tal caso, puoi solo sperare di realizzarlo prima di lavorare sul codice per troppo tempo.

(Anche in questo caso, per riferimento, suppongo un contesto TopCoder .. per qualcosa di più realistico e di conseguenza pratica mi consiglia vivamente di verificare in realtà la struttura matroide prima di selezionare un algoritmo greedy.)

Answer 2

Una parte del problema può essere causato dal pensare a "problemi avidi". Ci sono algoritmi e problemi avidi in cui c'è un algoritmo avido, che porta a una soluzione ottimale. Ci sono altri problemi difficili che possono essere risolti anche da algoritmi avidi, ma il risultato non sarà necessariamente ottimale.

Ad esempio, per il problema dell'imballaggio del contenitore, ci sono molti algoritmi avidi tutti con una complessità molto migliore dell'algoritmo esponenziale, ma si può essere certi che si otterrà una soluzione inferiore a una certa soglia rispetto a alla soluzione ottimale.

Solo per quanto riguarda i problemi in cui gli algoritmi grezzi porteranno a una soluzione ottimale, la mia ipotesi sarebbe che una prova di correttezza induttiva sia totalmente naturale e facile. Per ognuno dei tuoi avidi passaggi, è abbastanza chiaro che questa era la cosa migliore da fare.

In genere i problemi con soluzioni ottimali e avide sono comunque facili, e altri ti costringeranno a escogitare un'euristica golosa, a causa dei limiti di complessità. Di solito una riduzione significativa mostrerebbe che il tuo problema è in realtà almeno NP-hard e quindi sai che dovrai trovare un euristico. Per questi problemi, sono un grande fan di provare.Implementa il tuo algoritmo e prova a scoprire se le soluzioni sono "abbastanza buone" (ideale se hai anche un algoritmo lento ma corretto puoi confrontare i risultati, altrimenti potresti aver bisogno di verità terrestri create manualmente). Solo se hai qualcosa che funziona bene, prova a pensare perché e forse anche provare a trovare una prova di limiti. Forse funziona, forse vedrai casi di confine dove non funziona e ha bisogno di raffinatezza.

Answer 3

"Termine utilizzato per descrivere una famiglia di algoritmi.La maggior parte degli algoritmi tenta di raggiungere una configurazione" buona "da una configurazione iniziale, effettuando solo mosse legali. Vi è spesso una misura della" bontà "della soluzione (assumendo una L'algoritmo ingordo cerca sempre di eseguire la migliore mossa legale possibile. Si noti che questo criterio è locale: l'algoritmo greedy non "pensa al futuro", accettando di eseguire una mossa mediocre ora, che consentirà

Ad esempio, l'algoritmo greedy per le frazioni egiziane sta cercando di trovare una rappresentazione con piccoli denominatori: invece di cercare una rappresentazione in cui l'ultimo denominatore è piccolo, ad ogni passaggio prende il più piccolo den ominator. In generale, ciò porta a denominatori molto grandi nelle fasi successive.

Il principale vantaggio dell'algoritmo greedy è solitamente la semplicità di analisi. Di solito è anche molto facile da programmare. Sfortunatamente, è spesso non ottimale. " --- ariels (http://www.everything2.com/title/greedy+algorithm?searchy=search)