Qual è la differenza tra i metodi avidi e hamiltoniani?

4

Dato T = {CTAGC, GAGCG, AGCGG, CGGAG} , utilizzando un algoritmo avido , la superstringa S sarà CTAGCGGAGCG .

Da S , la combinazione di terzine sarà data come s = {CTA, TAG, AGC , GCG , CGG, GGA, GAG, AGC , GCG } .

Entrambi GCG e AGC vengono ripetuti.

Se si utilizza s per recuperare la superstringa usando il metodo Hamiltoniano, le parole ripetute saranno usate o omesse?

Se la parola ripetuta viene omessa, allora CTA , TAG , AGC , GCG , CGG , GGA e GAG costruiti indietro diventeranno GTAGCGGAGC .

Quindi, alla fine, sia il metodo goloso che il metodo hamiltoniano forniranno risultati diversi nella superstringa.

Perché sono diversi? Nella mia ricerca, tutti gli esempi che ho trovato hanno mostrato che non ci sono parole ripetute nella combinazione, quindi se ricostruisco la superstringa usando il metodo Hamiltoniano, il risultato dei metodi avidi e Hamiltoniani sarà lo stesso. Ma per quanto riguarda le parole ripetute?

    
posta worse 11.10.2011 - 11:13
fonte

1 risposta

2

Non conoscevo l'algoritmo esatto che esprime la stringa Super S dal set T Tuttavia, ecco una breve risposta alla tua domanda.

Fondamentalmente, l'algoritmo avido di ottimizzazione (o ricerca) restituisce algoritmi dopo aver trovato il minimo iniziale. Quindi, sono abbastanza dipendenti dal punto di partenza e dalla natura della funzione. D'altra parte, Gli algoritmi di ottimizzazione globale tendono a cercare l'intero spazio possibile per trovare i minimi attraverso lo spazio. Quando lo spazio di ricerca è minimo, o convesso per natura, il risultato di entrambi il tipo di algoritmo è lo stesso perché c'è solo 1 minimo. Tuttavia, se ci sono molti minimi locali, l'algoritmo di ottimizzazione globale cercherà quello corretto, mentre l'algoritmo greedy potrebbe produrre un risultato non ottimale.

    
risposta data 22.12.2011 - 20:02
fonte

Leggi altre domande sui tag