Ciao a tutti
che voi sappiate, è possibile applicare una modifica a Dijkstra (o ad un altro algoritmo) per avere tutti i percorsi possibili che mi portano da un nodo ad un'altro?
In pratica a me interessano tutti i percorsi validi, non solo l'ottimale.
"durante i primi 5 miuti di pioggia nel bosco c'è ancora asciutto, poi quando smetterà di piovere nel bosco cadranno gocce per 5 minuti.....la natura ha un'ottima memoria..."
http://www.kumbe.it
pensando ad un grafo, se devi andare da un nodo sorgente ad un nodo destinazione, potresti trovare il percorso minimo ed eliminare/marcare la connessione tra il nodo destinazione e il nodo subito prima.
cioe' se questo fosse il percorso minimo tra sorgente e destinazione
sorgente-->O1-->O2--> ... -->On-->destinazione
una volta che lo modifichi cosi':
sorgente-->O1-->O2--> ... -->On (arco eliminato) destinazione
basta cercare sul nuovo grafo il cammino minimo, eliminare l'ultimo arco del cammino e continuare finche' non ci sono piu' cammini tra i due nodi.
La mia e' solo un'idea ma non so quale sia la tua struttura dati, non so nemmeno se hai un grafo aciclico o no... insomma occhio che se cerchi tutte le strade per andare da un punto ad un altro cerchi anche la strada piu' lunga che non si' puo' determinare perche' si puo' passare dal brasile per andare dalla sala al bagno :P
Quanti programmatori sono necessari per cambiare una lampadina?
Nessuno, e' un problema hardware.
mmm
non è proprio quello che mi serve... però mi hai dato un'idea!
faccio girare l'algoritmo due volte (supponiamo di voler andare da A a D):
la prima volta da A a tutti i nodi raggiungibili
la seconda volta da ogni nodo raggiungibile a D.
"durante i primi 5 miuti di pioggia nel bosco c'è ancora asciutto, poi quando smetterà di piovere nel bosco cadranno gocce per 5 minuti.....la natura ha un'ottima memoria..."
http://www.kumbe.it
L'algoritmo di Dijkstra che ho studiato in ricerca operativa trovava tutti i percorsi partendo da quello minimo, la precondizione è solo di non avere archi negativi!!!
o forse io ho studiato una variante, anche se non penso perchè comunque devi etichettare tutti i nodi e nel farlo ne escono diversi alberi spanning!
oppure oggi pensavo ad un'altro approccio...
ho fatto dei test e sembrerebbe funzionare:
faccio girare l'algoritmo molte volte, e ogni volta cambio il peso sugli archi mettendone uno random.
La cosa sembra funzionare! dopo un po di esecuzioni si ottengono i vari percorsi validi.
Non so però quanto sia valida questa cosa in reti con qualche migliaio di nodi, bisognerebbe fare un calcolo delle probabilità e vedere cosa ne esce fuori...
"durante i primi 5 miuti di pioggia nel bosco c'è ancora asciutto, poi quando smetterà di piovere nel bosco cadranno gocce per 5 minuti.....la natura ha un'ottima memoria..."
http://www.kumbe.it
Permessi di invio
Rispondi quotando