Reverse algoritmi greedy - noto anche come algoritmi Rgreedy - non sono la "inversa" degli algoritmi golosi. Sono anche algoritmi greedy, ma funzionano in direzione inversa. Solitamente un algoritmo Rgreedy risolve un problema nella direzione opposta o utilizza una soluzione opposta rispetto alla soluzione classica algoritmo greedy. Un algoritmo greedy è uno che prende quello che sembra il passo più vantaggiosa in ogni punto in un processo. Algoritmi Greedy non sempre funziona, ma sono quasi sempre il modo più semplice di scrivere un algoritmo.

istruzione

1 Inizia con l'algoritmo greedy. Se non esiste una soluzione algoritmo greedy standard per un problema, il problema di trovare l'algoritmo inverso è discutibile. Non è possibile trovare l'inverso del tipico modo di fare qualcosa se non vi è alcun modo tipico. Un buon esempio di un algoritmo greedy è il "albero ricoprente minimo di un grafico" problema. Un grafico è un insieme di punti collegati da linee dove le linee sono etichettati con i numeri. L'albero ricoprente minimo è un insieme connesso di linee che collega tutti i punti.

2 Cercare la procedura nella algoritmo greedy che può essere invertito. Tipicamente sarà il processo che controlla l'algoritmo; il processo che, quando esaurito, provoca l'algoritmo di fermarsi. L'algoritmo greedy classico per trovare l'albero di copertura minima è di iniziare con i punti e le linee di collegamento. Ad ogni passo, aggiungere la riga più piccolo tra due punti qualsiasi. Continuare il processo fino a quando tutti i punti sono collegati.

3 Trovare qualcosa per invertire se si vuole costruire un algoritmo Rgreedy. L'algoritmo Rgreedy per trovare l'albero ricoprente minimo inizia con la mappa e tutte le linee. Ad ogni passo, rimuovere la riga con la più grande etichetta che lascerà i punti collegati. Continuare questo processo fino a quando non più linee possono essere rimossi.

4 Controllare l'algoritmo Rgreedy per assicurarsi che risolve il problema. In realtà non è un algoritmo se non risolve il problema. Talvolta invertire un processo di controllo può introdurre una situazione in cui l'algoritmo non affronta tutti gli elementi del problema o non termina l'algoritmo correttamente. .

Consigli e avvertenze

• Nel minima spanning problema dell'albero, se i punti sono città, le etichette possono essere le distanze tra le città. Se i punti rappresentano sottostazioni di una società via cavo, le etichette possono essere il costo di posa di un cavo tra due sottostazioni. L'albero di copertura minimo è un insieme di linee che sono collegati gli uni agli altri e che collegano tutti i punti. Entrambi gli algoritmi sono avidi, ma l'algoritmo greedy aggiunge le linee e l'algoritmo Rgreedy sottrae linee.
• Non tutti gli algoritmi greedy hanno un contrappunto Rgreedy. Anche se lo fa, non vi è alcun motivo di sospettare che funzionerà meglio l'algoritmo greedy. Alcuni problemi non sono risolvibili da algoritmi greedy. Ad esempio, risolvere il cubo di Rubik con un algoritmo greedy che sceglie sempre la mossa che aumenta il numero di colori corretti - o diminuisce il numero di colori non corretti - è destinato a fallire. Alcuni problemi richiedono soluzioni più globali.