Newsgroup: it.scienza.informatica
Titolo: ricerca del percorso più breve tra due punti

Salve a tutti,
desidererei sapere quali sono gli algoritmi tutt'ora conosciuti per la
ricerca del percorso più breve tra due punti (pensate ad una mappa
topografica) e la loro complessità.
Io ho sviluppato un algoritmo che ha complessita  O(n) dove n è il numero di
nodi del grafo che descrive le varie  strade con i relativi incroci e vicoli
ciechi  (non so se mi sono spiegato), ma non so se ho inventato qualcosa di
gìà esistente oppure no.
Ciao,
Fabio Alemagna

Fabio Alemagna wrote:

Forse ho capito male, ma mi spieghi come e' possibile che
la complessita' non dipenda dal peso e dal numero degli spigoli
(ovvero le strade che congiungono due vertici)!!!!!!
Dario
--
--------------------------------------------------------------------
Il mio indirizzo e' volontariamente errato per eliminare pubblicita'
non gradita. Se volete contattarmi l'indirizzo corretto e' :
 
mart...@cipciop.mat.uniroma3.it
eliminando cip dall'indirizzo

(ovvero le strade che congiungono due vertici)!!!!!!
Mi associo al dubbio: un algoritmo deterministico deve almeno leggere
i suoi dati in input, che nel caso di un grafo completo sono O(n^2).
Ho dei seri dubbi che la cosa si possa fare in O(n).
In certi casi, tipicamante se il grafo e' aciclico, ce la si fa'
in O(m), dove m e' il numero di archi del grafo. Se i pesi degli archi
(lunghezze, diciamo) sono >= 0, la miglior complessita' nota e'
O(m + n * lg(n) ).
                                             Saluti
                                             Antonio
Antonio Frangioni                      Research Associate  |  I have gained ...
Dip. di Informatica - Corso Italia 40 - 56125 Pisa, Italy  |  the colour of the
Ph +039-50-887216                
www.di.unipi.it/~frangio
  |  corn.   [Exupery]

(ovvero le strade che congiungono due vertici)!!!!!!
Uhmmm, non credo di essermi sbagliato dicendo quello che ho detto... cmq,
l'algoritmo non l'ho sviluppato usando dei grafi, ho usato questo termine
poichè mi sembra che il caso in cui l'ho studiato sia direttamente
conducibile a dei grafi. E' ovvio che il peso degli archi dei grafi
(tipicamente la lunghezza della strada)  ha un suo effetto sull'algoritmo,
ma non mi pare che questo incida sulla complessità.
L'algoritmo è nato come soluzione a questo problema:
Trovare il percorso più breve tra l'entrata in un labirinto e la sua uscita.
Il labirinto è rappresentato da una matrice quadrata di dimensioni
arbitrarie, dove i muri sono rappresentati da delle caselle settate con un
determinato codice (ovviamente arbitrario), e anche l'uscita.
Nel labirinto si può procedere solo verso desta, sinistra, alto e basso, non
diagonalmente.
Di primo acchitto si penserebbe di procedere usando un'algoritmo ricorsivo,
di complessità (correggetemi se sbaglio) O(3^n), dove n è il numero di
caselle rappresentanti il percorso. Dopo un po' di lavoro mentale, però,
sono riuscito a sviluppare un'algoritmo, non ricorsivo, di complessità, nel
caso peggiore, O(n), dove n è sempre il numero di caselle rappresentanti il
percorso.
Da qui mi è venuto spontaneo ipotizzare che si potesse generalizzare
l'algoritmo anche al caso dei grafi, ovviamente assegnando un peso agli
archi congiungenti i vari nodi, dove i nodi non sono altro che gli incroci,
e gli archi sono la strade che uniscono gli incroci e, ovviamente, il peso
degli archi altro non è che la lunghezza di queste strade.
La teoria dei grafi non è proprio il mio forte, ma spero di essermi spiegato
bene per quanto riguarda l'origine del mio algoritmo.
Non vi spiego com'è fatto il mio algoritmo solo perchè potrebbe non essere
stato ancora inventato (non sono presuntuoso, il fatto è che non conosco le
teorie già esistenti a riguardo), anche se ne dubito fortemente :)
Aspetto vostre delucidazioni,
Fabio Alemagna

degli archi altro non è che la lunghezza di queste strade.
Questo in parte rende piu' comprensibile il risultato che dici di aver
ottenuto, visto che il numero di archi per nodo e' O(1) = 4, quindi
O(m) = O(n).
Pero' il grafo che hai non e' aciclico, quindi il miglior algoritmo che
conosco io e' sempre O(n * lg(n)). A meno che tu non abbia qualche ipotesi
forte su come sono fatti i pesi sugli archi. Sono stati proposti algoritmi
che hanno complessita' tipo O( m + n * Sqrt( C ) ) (o qualcosa del genere,
dovrei controllare) dove C e' la massima lunghezza degli archi: tali
algoritmi sono detti "pseudopolinomiali" perche' la complessita cresce
con C, ma la rappresentazione di C prende solo log2( C ) bits.
Quindi, se tu assumi che C sia una costante (es 1) ottieni un O(m), che
nel caso tuo diventa O(n). Questo e' tutto quello che so immaginare.
Se la cosa funziona per il caso generale e' bellina.


nel caso tuo diventa O(n). Questo e' tutto quello che so immaginare.
Ma la lunghezza degli archi non può essere costante, poichè gli archi sono
le strade congiungenti gli incroci.
Cmq, la complessità, una volta applicato l'algoritmo ai grafi, potrebbe
dipendere dalla lunghezza degli archi, ma penso di essere in grado anche di
modificare l'algoritmo in modo che dalla lunghezza degli archi non dipenda
(lo dico così ad occhio e croce, ho già  in mente qualcosa, ma devo metterla
meglio a fuoco).
Nel caso il mio algoritmo risultasse essere davvero della complessità di cui
ti ho parlato, potrebbe avere una qualche applicazione?
Ti spiacerebbe spegarmi come funzionano questi algoritmi di cui parli tu?
Oppure indicarmi dove posso avere maggiori informazioni.
ti ringrazio,
Fabio Alemagna

Oppure indicarmi dove posso avere maggiori informazioni.
Per esempio nel libro "Network Flows" di Ahuja, Magnanti & Orlin.
Lo trovi nelle biblioteche di molti dipartimenti di informatica, matematica
e/o ingegneria.
                                       Ciao
