ricerca esaustiva alberi

[mistermars]

come ho scritto nell'altro post, sto realizzando un progetto sul problema del multicast packing.

dovrei effettuare dei test per verificare se la soluzione del mio progetto è ottima oppure si avvicina a quella ottima.

A tale proposito mi servirebbe un algoritmo in c o c++ che mi permetta di effettuare una ricerca esaustiva di tutti gli alberi possibili per il collegamento della sorgente con tutti i destinatari


Grazie

[cionci]

Non ho ben capito come vuoi far funzionare il tutto...cosa c'è sui nodi dell'albero ?

[mistermars]

Originariamente inviato da cionci
Non ho ben capito come vuoi far funzionare il tutto...cosa c'è sui nodi dell'albero ?


Dunque la sorgente trasmette un unico flusso di dati, come nel caso del broadcast, ma le informazioni giungono esclusivamente al gruppo limitato dei destinatari iscritti al gruppo. Ogni qual volta si rende necessaria una diramazione del percorso per raggiungere tutti i destinatari, i router duplichano i dati su più interfacce, ma solo quelle indispensabili a completare la distribuzione delle informazioni.
In questo modo si evita di immettere sulla rete un numero eccessivo di pacchetti, ma soprattutto siamo in grado di individuare dei percorsi comuni su cui far viaggiare i dati senza intasare la rete. In particolare i nodi e i collegamenti utilizzati per la consegna dei dati fra i membri del gruppo realizzano una topologia nota come albero di distribuzione. L’efficienza della trasmissione multicast dipenderà proprio dal modo con cui si costruisce tale albero, che può assumere diverse configurazioni per la stessa trasmissione a seconda del protocollo di instradamento utilizzato dai router e dalle specifiche richieste per il tipo di applicazione.

quello che sto realizzando io è una soluzione sub-ottima alla costruzione degli alberi, in quanto la ricerca dell'albero ottimo richiede un tempo molto maggiore .
Quindi ciò che sevirebbe a me è un algoritmo che mi permetta di trovare l'albero ottimo, in modo da verificare se l'albero trovato da me si discosta molto da quello ottimo.
L'unico modo per avere l'albero ottimo è quello di trovare tutti possibili alberi , quindi fare una ricerca esaustiva, e vedere quale tra questi a costo minimo .

[cionci]

Se mi ricordo ancora qualcosa da Ricerca Operativa...potresti utilizzare l'algoritmo Branch and Bound...

[mistermars]

hai il codice c o c++?

[cionci]

No... Non l'ho mai usato in un programma...prova a ricercare con Google...