Che materia stai cercando?

Ricerca operativa - algoritmo di Prim Appunti scolastici Premium

Appunto relativo all'esame di ricerca operativa del professor Giuseppe Bruno. L'argomento trattato è l'algoritmo di Prim, sviscerato in ogni sua variante, che serve a risolvere il problema di come portare la corrente o l'adsl a costo minimo a tutti gli abitanti di una città.

Esame di Ricerca Operativa docente Prof. G. Bruno

Anteprima

ESTRATTO DOCUMENTO

Figure 1: Parametri ultizzati nella analisi della Rete

Una generica rete da analizzare presenta n-nodi, si ha allora che V = n;

n−2

per “A. Cayley(1889)” per una rete con n-nodi si possono avere n -alberi

di supporto ad n 1-lati, come viene mostrato nella fig.2.

Figure 2: Alberi di Supporto e Lati per V = n = 3

Si puó operare l’analisi di una rete scandendo in passi la procedura di

Prim, in particolare quando il fine dell’analisi é trovare un percorso tra tutti

i nodi della rete che sia a costo minimo; si puó suddividere la procedura

dell’algoritmo nei seguenti passi:

{0},

Step0: Inizialmente S = non ci sono nodi appartenenti ad S, ne tan-

tomeno esiste un taglio; visto che l’origine non é predefinita, se ne

{r},

sceglie una per esempio r e si produce l’assegnazione r : S = si

ottiene cosı́ un primo taglio per la rete e un primo componente per

0

N . 0

Step1: Ottenuto il primo taglio, si valutano i costi degli archi uscenti da N di-

00

retti ai k-nodi di N ; si applica il criterio di scelta min c , che com-

k S ,k

i

porta la scelta fra i vari archi di quello a costo minimo e l’inclusione in

S del k−simo nodo terminale, relativo all’arco scelto, con l’assegazione

k : S = k. Attualmente il taglio si é ampliato, si é ampliato S e ovvi-

0 −

amente N , che contengono rispettivamente due nodi. V S diviene

V 2 visto che l’albero di supporto é composto da due nodi della rete,

0

si prevedono al piú altre V 2 iterazioni. Il costo totale rispetto a N

viene calcolato mediante la relazione c = c + min c .

0

tot. k S ,k

N i

2


PAGINE

4

PESO

184.63 KB

AUTORE

Menzo

PUBBLICATO

+1 anno fa


DETTAGLI
Corso di laurea: Corso di laurea in ingegneria informatica
SSD:
A.A.: 2013-2014

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher Menzo di informazioni apprese con la frequenza delle lezioni di Ricerca Operativa e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Napoli Federico II - Unina o del prof Bruno Giuseppe.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Ricerca operativa

Ricerca operativa - esercitazione 2004
Esercitazione
Tecnologie Sistemi Automazione e Controllo – PLC
Dispensa
Sistemi operativi - domande esame
Appunto
Elementi di Automazione – elenco programmi
Dispensa