Viene proposto un algoritmo distribuito per determinare un insieme di indipendenza massimale per un grafo non diretto. Tale algoritmo è determinato da da un algoritmo centralizzato basato su sequenze di reti neurali di Hopfield. Faremo riferimento al modello sincronizzato del calcolo distribuito nel qualce la topogia è descritta da un grafo. Daremo un limite superiore al numero di messaggi inviati durante la computazione. Per testare l'algoritmo, abbiamo sperimentalmente comparato l'algoritmo con un'euristica probabilistica derivata dal modello di ottimizzazione chiamato 'Ant colony' e con l'algoritmo greedy standard.
A Distributed Algorithm for Max Independent Set Problem Based on Hopfield Networks
POSENATO, Roberto
2002-01-01
Abstract
Viene proposto un algoritmo distribuito per determinare un insieme di indipendenza massimale per un grafo non diretto. Tale algoritmo è determinato da da un algoritmo centralizzato basato su sequenze di reti neurali di Hopfield. Faremo riferimento al modello sincronizzato del calcolo distribuito nel qualce la topogia è descritta da un grafo. Daremo un limite superiore al numero di messaggi inviati durante la computazione. Per testare l'algoritmo, abbiamo sperimentalmente comparato l'algoritmo con un'euristica probabilistica derivata dal modello di ottimizzazione chiamato 'Ant colony' e con l'algoritmo greedy standard.
File in questo prodotto:
Non ci sono file associati a questo prodotto.
I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
