Newsgroup: it.comp.lang.visual-basic
Titolo: [?][Lungo] Calcolo percorsi...

OK, getto la spugna, non ci dormo più e ammetto le mie carenze.
Ho la necessità di calcolare tutti i possibili percorsi (anche quelli
lunghi, assurdi e senza senso pratico, ma comunque possibili) fra tutti i
punti di una mappa virtuale, non necessariamente stradale. No, non è una
mappa geografica reale, è puramente virtuale, solo buttata giù come idea.
Non voglio fare un vero "generatore di percorsi su mappa geografica", ma il
principio e gli scopi, salvo ottimizzazioni successive, sono esattamente gli
stessi.
Per favorire e limitare al minimo il lavoro dell'operatore che dovrà
descrivere il "territorio" di interesse, ho ipotizzato questa semplice
struttura:
-Archivio in un vettore a due dimensioni v(1 To 2, 1 To n) e a "n" elementi
_solo_ i contatti fra un punto e un altro. Questo è il solo lavoro di
preparazione da parte dell'operatore.
-Diciamo, per semplicità, che ogni punto è "descritto" da un numero
assolutamente univoco.
-La seconda dimensione v(..., 1 To n) indica il numero della coppia di punti
(è chiaramente seconda per poter usare la Redim Preserve all'aumentare delle
coppie)
-La prima dimensione v(1 To 2, ...) i punti della coppia relativa:
nell'elemento v(1,...) metto uno dei due punti, nell'elemento v(2,...)
l'altro.
-Non mi importa, allo stato, dover evitare o, se necessario, inserire (o
generare) le coppie simili, ovvero il contatto fra due punti anche nel senso
opposto.
Una "mappa" d'esempio (che non disegno perchè verrebbe uno schifo) delle
varie coppie di punti in contatto fra loro può essere questa (riporto un
solo senso di "marcia", ma, ripeto, non è assolutamente un problema
prevedere anche il senso opposto):
Coppia: Dal punto-Al punto:
1: 1-2, 2: 1-4, 3: 1:8, 4: 2-3, 5: 2-5, 6: 2-6, 7: 3-4, 8: 3-8, 9: 4-5, 10:
4-6, 11: 4-7
Potete, se volete, disegnarla su un pezzo di carta: Segnate (state larghi)
gli 8 punti dove volete e poi congiungeteli con le sole "strade" indicate
per ogni coppia di punti. Se le linee si intrecciano, evidenziate un
cavalcavia...
Ed ora il quesito: Come posso determinare _tutti_ i possibili percorsi
(anche quelli che per andare da Lodi a Milano ti fanno passare per Timbuctù)
da un punto di partenza a un punto d'arrivo, ipotizzando ovviamente che in
ogni diversa "sessione di lavoro" il punto di partenza e/o il punto di
arrivo possano cambiare?
Mi sono arenato sul fatto che, pur appoggiandomi a vettori che indichino i
percorsi già ottenuti, le coppie già considerate, etc, in caso di
"svincolo", ovvero un punto dal quale si diparte più di un percorso
(nell'esempio fatto, tutti i punti tranne il 7 che ha come unico sfogo il 4)
rischia di non essere più considerato nell'iterazione successiva che
porterebbe a un percorso diverso. Il percorso, inoltre, non deve andare in
loop, ovvero se vado da 1 a 2, non devo (nel tratto immediatamente seguente)
poter andare da 2 a 1, se no mi arrestano per vagabondaggio o per
favoreggiamento della prostituzione.
Inutile dire che (salvo funzioni previste in VB e/o API, queste ultime non
simpaticissime) non mi interessa un OCX o una DLL chiusi, il codice lo devo
poter vedere e manipolare, senza spendere un euro. Ovvio che il codice del
prodotto definitivo, se il WM del SC lo riterrà, verrà pubblicato.
Pur non considerando assolutamente le prestazioni, nè il fatto che a regime
il vettore sarà un database, potete darmi una dritta (tenendo conto degli
ostacoli che la mia limitata mente ha già incontrato)? Grazie.
PS: Se può interessare, quello che segue è il codice che prepara il vettore
corrispondente alla "mappa" prima esemplificata. C'è un terzo elemento, la
distanza fra due punti, ma per ora assolutamente ininfluente:
'------------------------
Dim elemento_max
Dim v()
Private Sub Form_Load()
'       Carica dati
'       Stringa contatti
"Partenza-Arrivo-Distanza,Partenza-Arrivo-Distanza,...,Partenza-Arrivo-Dista
nza"
'       Per semplicita' si inseriscono anche i doppioni andata-ritorno
'       Lo spazio dopo ogni virgola non e' necessario, e' solo per
leggibilita'
    contatti = ","
    contatti = contatti & "1-2-2, 1-4-14, 1-8-8,"
    contatti = contatti & "2-1-2, 2-3-3, 2-5-5, 2-6-6,"
    contatti = contatti & "3-2-3, 3-4-4, 3-8-8,"
    contatti = contatti & "4-1-14, 4-3-4, 4-5-5, 4-6-6, 4-7-7,"
    contatti = contatti & "5-2-5, 5-4-5,"
    contatti = contatti & "6-2-6, 6-4-6,"
    contatti = contatti & "7-4-7,"
    contatti = contatti & "8-1-8, 8-3-8,"
    ReDim v(1 To 3, 0 To 0) '1  Punto 1
    '                       '2  Punto 2
    '                       '3  Distanza
    ex_partenza = 1
    partenza = 1
    Do
        If partenza > Len(contatti) Then Exit Do
        virgola = InStr(partenza, contatti, ",")
        If virgola = 0 Then virgola = Len(contatti) + 1
        If partenza <> ex_partenza Then
            contatto = Trim(Mid(contatti, partenza, virgola - partenza))
            prima_linea = InStr(contatto, "-")
            seconda_linea = InStr(prima_linea + 1, contatto, "-")
            punto_partenza = Val(Left(contatto, prima_linea - 1))
            punto_arrivo = Val(Mid(contatto, prima_linea + 1,
seconda_linea - prima_linea - 1))
            distanza = Val(Mid(contatto, seconda_linea + 1))
            ReDim Preserve v(1 To 3, 0 To UBound(v, 2) + 1)
            v(1, UBound(v, 2)) = punto_partenza
            v(2, UBound(v, 2)) = punto_arrivo
            v(3, UBound(v, 2)) = distanza
        End If
        ex_partenza = partenza
        partenza = virgola + 1
    Loop
    elemento_max = UBound(v, 2)
End Sub

 mappa geografica reale, è puramente virtuale, solo buttata giù come idea.
Tempo fa avevo fatto un progetto stupidissimo che generava un labirinto e
cercava un percorso risolutivo.
Non credo possa servire al tuo caso, ma forse qualche idea potrebbe dartela.
D'altra parte credo che il tuo problema non sia molto diverso dalla classica
ricorsione delle directory che fa il dir /s.
Prova ad affrontare la cosa in questo modo.
Magari ti può venire in aiuto anche il semplice calcolo combinatorio.
Cioè ammesso di avere i punti A, B, C i percorsi validi sono semplici
disposizioni di questi:
ABC, ACB, CBA, BCA...
o permutazioni (a seconda di quello che vuoi ottenere)
AB, AC, ABC, ACB, BC, BCA...
Prova a cercare "combinazioni" sul Sito Comune.
Ciao
--
Math Parser : 
http://www.neodatatype.net
Sito Comune : 
http://www.it-lang-vb.net

 Prova a cercare "combinazioni" sul Sito Comune.
Farò anche questo. Grazie

 da un punto di partenza a un punto d'arrivo
Ho letto gli altri messaggi... scoprirai che questo problema
porta ad una cosiddetta "esplosione combinatoria", cioè che
una ricerca esaustiva su tutti i percorsi, su 10 elementi è facile,
su 100 elementi è appena possibile, su 1000 magari richiede
un tempo di calcolo superiore alla vita presunta dell'universo. :-((
Spero dio sbagliarmi, ma se non ricordo male, il tempo di
calcolo è in rapporto fattoriale con il numero di punti.
Il problema del commesso viaggiatore, per assurdo, è più
semplice :-), perché richiede di trovare solo il percorso più
breve, e possibilmente visitando _tutti_ i punti _una sola_ volta.
Questo permette ad un algoritmo ottimizzante che utilizzi
metodi euristici di potare a priori alcuni rami dell'albero delle
possibilità, quindi di evitare di infognarsi nel calcolo di casi inutili.
Sto ancora cercando di inquadrare bene il problema, dimmi,
tu poni delle limitazioni di questo tipo, a livello logico ?
Se, per esempio, cerchi solo _un_ percorso possibile, a
prescindere dalla lunghezza, e con gli obblighi di non passare
più volte per lo stesso punto, e di passare per _tutti_ i punti,
la risposta è semplicissima ;-)))
basta usare lo stesso metodo dell'estrazione casuale di
numeri da una serie di cui si è riparlato pochi giorni fa.
***********
Ma se ti servono davvero _tutti_ i percorsi, devi prendere
tutti i punti di partenza possibili, e per ognuno scendere
tutti i rami dell'albero che si crea, per tutti gli altri punti...
e così via, ricorsivamente. Prova un approccio bottom-up
al problema, immagina per semplicità di lavorare con quattro
soli punti, A, B, C e D.
Da A puoi voler andare a B, a C, o a D, come punto di arrivo,
e per ognuno di questi puoi passare, in un'ordine qualunque,
dagli altri. Le combinazioni sono quindi:
Da A a B:
A-C-D-B
A-D-C-B
Da A a C:
A-B-D-C
A-D-B-C
Da A a D:
A-C-B-D
A-D-B-D
Da B ad A:
B-C-D-A
B-D-C-A
.......... e via dicendo. Con un programmino ad hoc, per
quattro punti ci vogliono pochi millisecondi, compreso
il tempo di visualizzazione. Ma per 100 punti, non ho fatto
conti, ma mi sa che ti serve già un Cray... e moolto tempo.
Bye, G.

 problema "mondiale" con molta documentazione. Cercherò qualcosa in VB, ma
Sì, ma il problema è un po' differente.
Come dice Paperino, il commesso viaggiatore deve toccare tutti i punti del
suo viaggio nel minor tempo possibile.
E' un problema di ottimizzazione.
E giustamente il tempo di calcolo dipende da cosa vuoi ottenere e da quanti
punti devi elaborare.


 suo viaggio nel minor tempo possibile.
Già. :-(

 un tempo di calcolo superiore alla vita presunta dell'universo. :-((
[post inutile]
    Appropo'... curiosità: sapevi che il nome di Google pare derivi
    proprio da questa storia ? E' modellato sul "Googol", un numero
    ipotetico che fosse più grande possibile, anche se finito.
 
http://www-users.cs.york.ac.uk/~susan/cyc/g/googol.htm
 
http://whatis.techtarget.com/definition/0,,sid9_gci809856,00.html
[/post inutile]
Bye, G.

 e così via, ricorsivamente.
Sapevo di averlo già visto... guardati il 3ad:
http://groups.google.com/groups?threadm=NYOG9.21127%24fa.699280%40news1.tin.it
Bye, G.

 conti, ma mi sa che ti serve già un Cray... e moolto tempo.
I miei pompieri non arriveranno mai... Sigh! ;-(


Premetto che avendo solo dato una letta (beh due "lette" per essere precisi
;-) al tuo post il rischio di non aver capito quello che cerchi di ottenere
e scrivere quindi adesso delle castronerie e' molto alto. :-)
Detto questo ho l'impressione che se stai cercando di fare un programma che
permette di trovare veramente *tutti* i percorsi possibili tra due punti in
una mappa con molti punti intermedi, stai sottovalutando i problemi
combinatori di un simile algoritmo.
Voglio dire che la realizzazione del codice per avere tutti i percorsi non
mi pare troppo difficile, sarebbe sufficiente una piccola funzione ricorsiva
con controllo dei tragitti inversi (per evitare loop infiniti) non troppo
difficile a realizzarsi.
Il problema e' che, IMHO, questa funzione non avrebbe alcuna utilita'
pratica perche' per essere eseguita su una mappa con un centinaio di punti
richiedere un tempo non accettabile.
I miei studi di probabilita' e calcolo combinatorio sono piuttosto lontani
nel tempo, per cui non vorrei sbagliare ma credo che il numero possibile di
percorsi tra N elmenti sia il fattoriale di N.
Ossia una cosa tipo (N-1) * (N-2) * (N-3) ... * 2
Il numero che si ottiene e' molto, molto, molto ... alto. :-/
Hai mai sentito quella storiella sulla scacchiera e i chicchi di riso? :-)
Non ricordo bene l'antefatto ma in sintesi era cosi'.
Un vecchio saggio aiuto' il proprio re a risolvere un problema (che non
ricordo) e il re chiese al saggio come volesse essere premiato.
Il saggio allora chiese "solamente" (sic) la quantita' di riso ottenuta
mettendo un chicco di riso sulla prima casella di una scacchiera (8x8) e poi
raddoppiando il numero casella dopo casella.
Il re penso' di essersela cavata con poco ("quanto potra' venire fuori alla
fine? Magari un paio di sacchi di riso. Bazzeccole" deve aver pensato :-) ma
alla fine, calcoli alla mano, il numero di tonnellate di riso che avrebbe
dovuto dare erano superiori a quelle di tutto il suo regno.
Considera che i programmi per la ricerca del percoso ottimale tra molti
punti intermedi sono veramente molto complessi e rientrano nel campo
dell'intelligenza artificile.
Non e' possibile infatti fare un lavoro esaustivo col calcolo di tutti i
possibili percorsi e semplice riscontro finale di quello piu' breve.
E' necessario usare un'analisi ad albero con una limitata ampiezza
orizzontale e verticale.
Ossia per ogni strato si prenderanno in considerazione solo le prime N
(numero limitato, magari 5 o 6) alternative che avvicinano di piu' secondo
il piano cartesiano (distanza tra due punti) al punto finale.
Ognuna di queste verra' analizzata cercando a sua volta i migliori N putni
che avvicinano di piu' al punto finale.
Tutto questo con frequenti "potature" dei rami che stanno perdendo troppi
punti rispetto alla migliore (cioe' minore) distanza finora trovata.
Insomma e' complicatuccio. :-/
Ma tanto per capirsi questi punti intermedi di una mappa quanti sarebbero in
media?
Nell'ordine delle unita', delle decine o delle centinaia?
Perche' se la mappa avesse solo qualche decina di punti forse sarebbe anche
possibile scandagliare tutti i percorsi con la forza bruta ma se il numero
e' piu' alto la vedo dura
ciao
Paolo B.

 destinazione, in una decina di secondi a selezionare il percorso migliore?
Non lo fa: nessuno ti assicura che quello sia il percorso migliore, anche
perche', se tentasse di fare un calcolo del genere, l'algoritmo potrebbe non
fermarsi mai.
In questo ambito non sempre il risultato č il migliore, ma solo una
approssimazione (a volte MOLTO approssimata) ottenuta in un tempo breve.
Lo stesso problema ce l'hanno i software che assegnano
tempo-risorse-persone, come i programmi che fanno gli orari scolastici o
quelli che organizzano aerei e piloti in un grande aeroporto.
Ciao
Luca

 non nel tempo) mi son sentito un grande cretino...
Rispolverando i miei neuroni, mi sono ricordato di aver studiato questo
genere di problemi in un corso di ricerca operativa; se non ho interpretato
male il problema che ti poni, questo dovrebbe essere una _variante_ del
"problema del commesso viaggiatore", per il quale, se ricordo bene, in
mancanza di ipotesi restrittive, gli algoritmi che portavano effettivamente
alle soluzioni ottimali erano tutti di tipo esaustivo.
Per questo genere di problemi di solito si pongono delle ipotesi restrittive
e si cerca di applicare algoritmi non esaustivi che garantiscano delle
soluzioni decenti in tempi accettabili, ove possibile.
-- 
Ale
E` in corso la CFV per per
*it.comp.programmare.dotnet*,
Si può leggere il manifesto su
_it.news.annunci_ o _it.news.votazioni_

Mi rendo conto di aver favorito qualche possibile equivoco, quindi,
ringraziando e rispondendo un po' a tutti, preciso a cosa dovrebbe servire
questa cosa, che sto facendo per volontariato e quindi gratis (ecco il
motivo di non voler spendere).
Questa è la realtà applicativa:
-Abbiamo una caserma di Vigili del Fuoco (Zanna, in quanto WM, in questi
giorni ne sa qualcosa, e anche Lord prima)
-La caserma risponde alle chiamate, nella quotidianità, per un territorio di
una ventina di comuni del circondario
-Arriva una chiamata perchè c'è un incendio al punto 15
-La caserma si trova al punto 1 (ma la tecnica dovrebbe esulare da questa
costante di partenza)
-Accendo la sirena e parto per il punto 15.
-Ma, per tutte le sirene canterine, che strada faccio per arrivare prima che
sia bruciato tutto?
Non c'è quasi altro da dire. Io ho ipotizzato (per ridurre al minimo il
lavoro di introduzione e, soprattutto, manutenzione delle informazioni di
"mappa") di archiviare tutte le coppie di vari punti collegati fra loro. Ho
ipotizzato centinaia di punti perchè ci sono, oltre ai comuni, anche le vie,
piazze, etc. e, dato il punto di partenza e quello di destinazione, fornire
(alla svelta perchè là sta bruciando un condominio pieno di gente)
all'autista il percorso migliore, semplicisticamente il più breve. Per
stabilire il più breve ho pensato, appunto, di ricavare tutti i percorsi
possibili e, banalmente confrontandoli, scegliere quello più adeguato.
Poi (ma solo poi), vi saranno delle informazioni di ottimizzazione, quali la
distanza, la dimensione delle strade, la presenza di ostacoli (fissi, come
sottopassi troppo bassi per il mezzo o temporanei, come dei lavori in corso)
che possono impedire o rallentare il passaggio del mezzo, la presenza
privilegiata di fonti idriche di approvvigionamento, i passaggi a livello,
un incidende appena accaduto, etc. Ma questo, tutto questo, non mi preoccupa
minimamente perchè, disponendo di tutti i percorsi possibili (ovvero
_percorribili con una strada da punto a punto_, sembra ovvio, ma va
specificato per escludere la combinazione di tutti i punti solo perchè
esistono) dal punto 1 al punto 15 li "critico" dopo, "percorrendoli" e
scartandoli (o mettendoli in subordine) se presentano "coefficienti di
rallentamento" tali da renderli sconsigliabili.
Grazie ancora a tutti.

     proprio da questa storia ? E' modellato sul "Googol"
Ho sempre pensato che derivasse da "googles", gli occhialoni da immersione.
Ciao

 fermarsi mai.
Mi hai aperto (anche se nulla serve al mio scopo) una finestra: Dici che
calcola il percorso _nei dintorni_ del punto corrente, basandosi
sull'orientamento del punto d'arrivo e in tempo reale lo adatta con
successivi ricalcoli cosě come quando faccio una strada diversa da quella
consigliata? E' comunque strano, perchč mi dice la distanza complessiva fin
dall'inizio...

 Ma per stabilire il più breve dovrà ben valurali tutti, no?!
Non necessariamente.
Potrebbe trovarne uno, poi tentare con un secondo e se questo diventa più
lungo del primo fermarsi a metà e iniziare il terzo.
Già questo ti farebbe risparmiare un mucchio di tempo.
E comunque non calcola tutti gli incroci possibili, ma solo quelli con
partenza e destinazione fissa (non inizierebbe mai il percorso da un punto
di mezzo).


 [/post inutile]
e sapevi che "googul" come nome e' stato dato dal figlio o nipote della
persona che ha "scoperto" l' uno con 1 milione di zeri dietro ?!?!?!
Vedi ? So sempre è inutile di te :p
PPS: da me e' scoppiata una "bufera di neve" e non sto scherzando, li' che
tempo fa ?
-- 
<Gigio2K>
Sito Comune
Nokia -> I.T.H.N. -> 
http://www.ithn.it/
VB -> I.C.L.VB -> 
http://www.it-lang-vb.net/

 Ho sempre pensato che derivasse da "googles", gli occhialoni da immersione.
Quelli non erano "goggles" ? 8-?
Bye, G.

 Ed ora il quesito: Come posso determinare _tutti_ i possibili percorsi
[cut]
Come ti hanno già detto questo è fattibile solo se i punti sono
veramente pochi. Quindi se il tuo scopo è (come presumo) trovare il
cammino migliore, l'approccio giusto non è questo. 
Per prima cosa devi utilizzare un grafo "pesato", ovvero ad ogni arco
che collega due punti deve essere associato un certo peso, poi
utilizzare un qualche algoritmo (ce no sono parecchi) per risolvere il
problema del cammino più breve. Tieni presente che pur chiamandosi così
non è detto che il peso di un arco debba essere per forza proporzionale
alla distanza, potrebbe rappresentare costi, unità di tempo, una qualche
indicazione sul traffico presente, ecc...
Considera inoltre che le prestazioni dei vari algoritmi sono dipendenti 
dal tipo di grafo, per cui la situazione non è molto semplice...
Se è in "ascolto" puoi chiedere a Gianni qualche consiglio, visto che
lui per la sua tesi aveva sviluppato proprio un programma che calcolasse
i percorsi migliori in una mappa stradale.
Ciao.
-- 
BSD is for UNIX lovers -- linux is for Windows haters.

 Quelli non erano "goggles" ? 8-?
Può darsi :)
E' che a volte i termini stranieri creano delle permutazioni di lettere
nella memoria e non è sempre facile trovare la parola corretta, ma solo
un'approssimazione :)


 Se è in "ascolto" puoi chiedere a Gianni qualche consiglio...
Gianni?

 (semplicisticamente) basandomi solo sulla distanza complessiva.
se passando per abc hai fatto 300Km e passando per axy hai fatto 100 imho
non dovresti processare + i rami "abc..." se in linea d'aria stai andando
dal lato opposto ... oh cavolo ma allora dovresti tenere anche conto della
direzione ? O_o meglio che smetta ti sto confondendo le idee ancora d+ !


*Lupo* che non trova la strada ...
http://snurl.com/yn5
Ecco il post che intendevo per il route planner


 fin dall'inizio
Non è che è solo la distanza in linea d'aria ? _Quella_ è facile :-))
P.S.: mi viene in mente ora: visto che il punto di partenza è
fisso (la caserma), sei sicuro che non ti convenga mantenere
una tabella delle strade consigliate fra i punti principali ?
Se crei una "rete" memorizzata di questi punti, per ipotesi:
incroci, svincoli e piazze principali, i tempi di calcolo ti si riducono
drasticamente. Per esempio, se devi andare dalla Caserma
fino ad una ipotetica Via Bologna, e sai che è nelle vicinanze
del Comune, memorizzi già la strada predefinita fino al Comune
poi da lì puoi far partire l'algoritmo che "si guarda in giro"...
dovendo cercare pochissimi punti. :-)
Bye, G.

 tempo fa ?
/me va a vedere...
    BRRRR !
/me rientra al calduccio, rabbrividendo.
    Nuvoloso, freddo e umido, ma con squarci di sereno da Nord.
Bye, G.

 un'approssimazione :)
ROTFLASTCOW ! insomma, la deriva dei 3ad ci ha riportato
al punto del post di partenza :-))) Questa sě che č ricorsione...
Bye, G.

 Gianni?
Rondinini...


 siccome i percorsi possono essere molti, come ottenerli _tutti_
allora dato che il punto di partenza e' fisso ed ha "un peso alto" non
rimane che trovare il punto con peso + alto VICINO al punto di arrivo
Mi spiego , diciamo che le strade sono tutte libere , ora se da A devi
andare a B dove B ha peso 2 devi trovare il punto + vicino a B che ha peso 1
cosi sai che se da Pescara(peso0=partenza) a Ostia(peso2) devi passare per
roma(peso1 citta' grossa)
quindi mi sa che non ti resta che pesare tutti i tronchi e dargli DIVERSI
pesi , 1peso per la distanza dalla partenza (esempio immagina una serie di
cerchi concentrici dove il centro e' la tua caserma ) , ora e' chiaro che le
strade vicino la caserma siano di peso + basso (vicoli e strade di citta'
con peso 4 diciamo ) e anche quelli vicino al punto di arrivo , pensala al
contrario , tu parti dal punto di arrivo X
X ha diverse informazioni come distanza in linea d'aria da A(caserma)
e su che tronco si trova
quindi puoi cominciare a scartare le strade che hanno come distanza in linea
d'aria maggiore di X +2 (poi ti spiego il +2)
poi vedi dove arriva il tronco dove si trova X , diciamo che arriva a X1 e
X2
X1 e' un nodo e leggendo le info vedi che ha una distanza in linea d'aria
maggiore di X2 e di X e quindi li scarti e accetti X2 come puntotemporaneo
Ora diciamo che sei partito da X e sei arrivato al punto X2 ora testi in
linea d'aria quei nodi che ricascano VERSO A e trovi X3 che ha lo stesso
peso di X2 o maggiore quindi ti stai avvicinando sempre d+ al centro
Ricorrendo dovresti avvicinarti fino ad arrivare al centro , immagina una
visione a Livelli dei centri dove il livello + alto sono le autostrade e
quindi hai i nodi che fanno capo solo alle autostrade , scendi e sei al
livello di SS e regionali , scendi ancora fino ad avere le strade di citta'
e i vicoli
in pratica vai su 
mappy.it
 e naviga sulla cartina , se aumenti lo zoom vedi
che per arrivare da nord a sud hai solo 5/6 nodi (le autostrade) quindi da
milano a roma vedi sono 2 punti
una volta tovato il nodo + breve scendi al livello inferiore (aumenti lo
zoom ) e vedrai che tra roma e una citta' + piccola ci sono solo una 10ina
di nodi , ritrovi la distanza + breve e zoommi fino ad arrivare in via XX
numero YY ^_^
Dimmi che hai capito la mia visione !


     Nuvoloso, freddo e umido, ma con squarci di sereno da Nord.
gia' bufera passata !


 dovendo cercare pochissimi punti. :-)
copione , ho risposto la stessa cosa 1 minuto prima di te :P solo che
conviene partire dal punto di arrivo e avvicinarsi AL PUNTO NOTO CASERMA !
^_^


 conviene partire dal punto di arrivo e avvicinarsi AL PUNTO NOTO CASERMA !
Ehmmm.. e la differenza quale sarebbe ? A parte il fatto che le
strade possono avere non solo un senso di percorribilità, ma
anche pesi (=velocità di scorrimento) diversi in diverse direzioni.
Mmmm... mi sa che non ho capito bene il tuo punto di vista.
Aspe', forse ci sono. Il peso di un determinato ramo viene
calcolato nella direzione "giusta", ma la ricerca dei nodi viene
fatta a ritroso, giusto ? Così ha un senso, anche se non ho
ancora capito dove sia il vantaggio. :-o
Bye, G.

 perche' non calcola TUTTI i percorsi , ma solo quelli migliori
Gigio, ti voglio bene e non ho mai nascosto le mie limitazioni mentali, ma,
per favore, te e tutti, porca pupattola zozza avvelenata, spiegatemi come
sia possibile:
<problema>
_stabilire se un percorso è migliore di un altro non disponendo di entrambi
i percorsi_
</problema
E, per rientrare nel motivo del mio topic, se i percorsi possibili sono 3, 5
o 10^1concentozeri, per stabilire il più breve (ammesso, e mi starebbe
superbene perchè allo stato _assolutamente_ ininfluente, che l'unica
discriminante sia la distanza) come posso confrontarli se non li ho _tutti_?
Puff, pant, 'a marò e tutti li santi, ora faccio mago-magò e (*scherzo,
neh?!*) il mio non-problema diventa automaticamente un vostro reale
problema: un potenziale cliente vi darà 10^64 euro (non ne hanno stampati
tanti) se gli fate un elenco dei percorsi da via Pippo a via Pluto che
distano 20 metri in linea d'aria. Ci sono due traverse e una piazzetta.
Saranno 4 o 5, ma li vuole tutti. Lui continuerà a percorrere il suo
preferito, magari il più lungo perchè passando di là c'è la fruttivendola
che lo ingrippa, ma li vuole e vi paga. E' pazzo, ma vi paga.
Ecchecazzo, possibile che nell'era informatica non ci sia un modo che
risolva prima della prossima glaciazione?
;-) ^ googol. Scusate lo sfogo, ma temo, sempre più, di non riuscire a
spiegarmi. E' certo l'età...

 ancora capito dove sia il vantaggio. :-o
Ari-Pork, mi sa che stiamo dicendo la stessa cosa in due modi
diversi. Ti spiego quello che intendevo io, seguimi (se riesco a
spiegarmi bene) e correggimi se necessario.
Per capirci, prendiamo dei punti di riferimento noti: partenza,
qui :-), arrivo, tanto per dire, in Via Bologna. iniziamo:
_DA_ Via Bologna, quali sono i "nodi principali" più vicini ?
Proviamo: in linea d'aria, un raggio di 50 metri, nessun risultato.
100 metri (attenzione che raddoppiando il raggio...), ancora
niente, 125, niente, 150, niente, 175... trovato, c'è il Comune.
Da qui al Comune la strada è nota, o perlomeno ci saranno
due o tre alternative, che magari hanno determinati vantaggi
a seconda dell'ora del giorno, per esempio; valutiamo queste
alternative e memorizziamo la migliore. Adesso, _dal_ Comune
a Via Bologna, al massimo ci sarà qualche decina di possibilità,
anche facendo una ricerca esaustiva, perché ci limitiamo ai
punti che sono nel raggio di 175 metri _dal_ Comune, e
particolarmente a quelli che sono nella direzione generica
di Via Bologna. Giusto ? Quindi in pochi tentativi potremo
trovare una via possibile, e sicuramente "buona", se non altro
perché per il tratto maggiore, cioè quello da qui al Comune,
abbiamo già scelto in precedenza quello ottimizzato.
A questo punto, per sicurezza, potremmo tornare a Via Bologna,
allargare il raggio di ricerca a 200 o 250 metri, e valutare
altri possibili "nodi principali", e rieseguire il resto della procedura...
Nturalmente, se il tragitto dal punto di partenza al secondo "nodo"
è più lungo della prima soluzione trovata, è inutile andare avanti,
e allo stesso modo possiamo abortire la ricerca anche al
"secondo livello", quello della ricerca dal nodo a Via Bologna,
se troviamo che il percorso attuale è più lungo del migliore
precedente. Ma al massimo troveremo pochi percorsi fra i quali
scegliere il migliore, in termini di tempo di percorrenza.
In ogni caso, il punto che Lupo dovrebbe notare è che non
c'è bisogno di valutare tutti i percorsi possibili fra i due punti,
perche l'ottimizzazione è fatta dinamicamente nei vari livelli.
Anche se non c'è la garanzia che, magari allargandosi di un
altro centinaio di metri, non si trovi per esempio l'uscita
di una circonvallazione che ci porterebbe ad accorciare
drasticamente il tempo del primo, e più lungo, tratto...
Io consiglierei a Lupo di permettere anche la scelta manuale
del nodo principale più vicino al punto di arrivo, se l'operatore
si accorge di una macroscopica incongruenza...
P.S.: E' arrivata la neve anche qui... E' appena entrato
Carlo, tutto bianco :-)))
Bye, G.

 dovendo cercare pochissimi punti. :-)
Sì, ma (a parte quanto dicevo poco sopra) mi sono gasato e volevo fare
qualcosa di "dinamico": Mappa semi-fissa, indicazioni fra due punti (e solo
una volta) variabili ora per ora, in funzioni delle notizie che pervengono
in caserma...

 Ehmmm.. e la differenza quale sarebbe ?
Nessuna, infatti., salvo i sensi unici (che tralasciamo perchè ci siamo già
accoltellati abbastanza).
Partire da un punto e arrivare a un altro è esattamente la stessa cosa che
partire dall'altro e arrivare all'uno.

</problema
[cut]
Prendiamo ad esempio la mappa che avevi postato in precedenza. Ora io
chiedo a te, se devi andare da 7 a 4 a cosa ti può interessare conoscere
come andare da 1 a 3?
Tu non hai bisogno di conoscere *tutti* i percorsi possibili in assoluto, 
ma volta per volta andrai a valutare i percorsi tra il punto di arrivo e
quello di partenza.
Consideriamo sempre la solita mappa rappresentata con una matrice di
adiacenza pesata (quindi con un peso al posto di un semplice 0-1), i
pesi li invento io.
0 1 0 3 0 0 0 1
1 0 1 0 3 3 0 0
0 1 0 1 0 0 0 5
3 0 1 0 1 3 4 0
0 3 0 1 0 0 0 0
0 3 0 3 0 0 0 0
0 0 0 4 0 0 0 0
1 0 5 0 0 0 0 0
Devo andare da 1 a 6 
vado in 2 (peso totale = 1)
vado in 6 (p.t. = 4)
vado in 2 (p.t. = 1)
vado in 3 (p.t. = 2)
vado in 4 (p.t. = 3)
vado in 6 (p.t. = 6) scarto
vado in 2 (p.t. = 1)
vado in 3 (p.t. = 2)
vado in 8 (p.t. = 7) scarto
vado in 2 (p.t. = 1)
vado in 5 (p.t. = 4) scarto
vado in 4 (p.t. = 3)
vado in 6 (p.t. = 6) scarto
vado in 8 (p.t. = 1)
vado in 3 (p.t. = 6) scarto
ecc...
Come vedi molti percorsi non vengono neppure valutati fino alla fine,
quindi conoscerli a priori non serve a nulla.
Spero di avere chiarito almeno in parte...


 rimane che trovare il punto con peso + alto VICINO al punto di arrivo
Taglio il resto e dico no: percorrere una strada lunga (non dico più veloce,
dico pure a velocità costante) che ti porta a un certo incrocio che ti
avvicina drasticamente alla destinazione, può essere più conveniente che
arrivare a destinazione tramite tratti più brevi, ma nella loro complessità,
più lunghi. Aggiungo, inoltre, che non dispongo del concetto di
orientamento, ovvero non so (nè mi sogno di sapere) se la destinazione è a
nord e quindi a un incrocio prediligo il nord, anche percè quel tratto
magari mi sta portando indietro, a Timbuctù, appunto.
Il concetto di "pesare" il nodo (io dico "tratto") ha senso solo per
valutarne gli specifici elementi di rallentamento o impossibilità, per
esempio ci sono lavori in corso, quindi tolgo "x" al suo intrinseco valore e
magari lo scarto scegliendo un altro tratto che si diparte da quello stesso
incrocio.

 vado in 6 (p.t. = 6) scarto
Mi fermo a questo. Non ho ben capito il concetto di peso: perchè
quest'ultimo me lo scarti? Magari è più corto del 2-6 diretto di prima. Ok,
non è più corto (supponendo che il peso possa corrispondere alla distanza),
ma il 2-6 è temporaneamente interrotto, è come se non ci fosse.
Quindi:
La domanda è sempre quella: per stabilire il percorso migliore (non mi
interessa in questa fase quali siano le discriminanti di confronto) li devo
avere tutti.
E, anzi, ti chiedo: come faresti a ottenere i vari percorsi che hai
elencato? Ovvero, quei "vado" che hai scritto, come si possono ottenere con
una qualsiasi logica informatica? Questo mi serve.

 Con la ricorsività ti assicuti di passare da tutte le strade possibili.
Non tutte, solo quelle che portano alla destinazione, non tutte.
Se ho ben capito, il problema del commesso viaggiatore è:
"Devo visitare questi 100 clienti. Tutti! Qual è il percorso migliore?"
Il mio problema è:
"Ho 100 clienti, ma devo andare dal cliente 1 al cliente 50. Solo da lui!
Qual è il percorso migliore?"

 spiegarmi. E' certo l'età...
No, ti sei spiegato, ma IMVVHO _non ne vale la pena_, tutto qui.
O meglio, ne vale la pena solo su piccola scala, una decina
di punti al massimo, e suddividere il problema in più sottoproblemi
che presi singolarmente, siano di dimensioni accessibili.
Bye, G.

 una qualsiasi logica informatica? Questo mi serve.
Provo a buttare giů un po' di pseudocodice. Pausa :-)
Bye, G.

 una qualsiasi logica informatica? Questo mi serve.
Questo è un po' troppo lungo, te lo spiego più tardi perché se non esco
in fretta stasera e domani non mangio...
Appena torno a casa cerco di spiegartelo semplicemente.


 che presi singolarmente, siano di dimensioni accessibili.
Ok. Mi metto la coda fra le gambe e mi rileggo il mio primo post... ;-(

 anche io, per caso un progetto di laboratorio all'univarsità di pisa?????
Veramente è un progetto fatto in 45 minuti come "test di valutazione" per un
nuovo posto di lavoro.
--
Math Parser : 
http://www.neodatatype.net
Sito Comune : 
http://www.it-lang-vb.net

 > ottenere con una qualsiasi logica informatica? Questo mi serve.
Allora, vediamo. Parto da zero, anche se avevi già fatto
nel primo post la prima parte. E sparo pseudo, _molto_
pseudo, ESTREMAMENTE pseudo, codice :-))).
Crei una matrice, che per ogni punto della mappa elenchi gli altri punti
raggiungibili da lì, ognuno con un peso (per semplicità la lunghezza,
come dicevi tu all'inizio, poi si vedrà), e un flag boolean per
memorizzare se il nodo è già stato visitato.
Dimensionamento variabili:
lunghezza del percorso attuale
lunghezza temporanea del percorso
lunghezza del percorso migliore trovato finora
distanza corrente
punto precedente
percorso corrente (elenco di punti trovati finora)
Punto di partenza = X
Arrivo nel punto = Destinazione
puntocorrente =X
do per ognuno di NumeroDiPuntiRaggiungibiliDal  puntocorrente
   punto in esame = questo punto
   if NON abbiamo già visitato questo punto
        aggiungi punto all'elenco del percorso corrente
        distanza corrente = distanza tra punto precedente e punto corrente
         if uno di questi punti è Destinazione ?
            Sì: abbiamo trovato un percorso possibile
                ce lo memorizziamo, insieme alla lunghezza, e andiamo avanti
         else
            No:
                lunghezza del percorso attuale = lunghezza temporanea del percorso + distanza corrente
                punto corrente = punto sotto esame
         end if
        lunghezza temporanea del percorso
        punto corrente = prossimo punto
    end if
loop
*********************************************
Maledetta la fretta, avrò scritto chissà quante castronerie, e non l'ho
neanche finita, ma mi hanno telefonato e mi aspettano a casa...
chiedo scusa Lupo, mando il post "a metà" giusto per dire che
ci stavo lavorando. :-)
Il concetto comunque è quello: una routine ricorsiva che analizza
una serie di possibilità. Nel caso prova a dare un'occhiata anche qui:
http://groups.google.com/groups?as_q=funzione%20ricorsiva&as_eq=dir%20dir%24&as_ugroup=it.comp.lang.visual-basic&as_scoring=d
cercando come autore Roby Piazzolla, mi pare abbia postato lui...
scappo, ci si rilegge domani sera.
Bye, G.

 via? Solo questo mi serve, solo ed esclusivamente questo!
Beh, qui potrebbe tornarti utile il progetto del labirinto.
In effetti esistono studi anche su questo problema (trovare la trada
d'uscita, cioč un tragitto valido per andare da A a B passando per N punti).
In pratica funziona cosě (ma magari esistono sistemi piů intelligenti di
questo che č tutto mio):
Poniamo di avere questo percorso
A ------- B --- C
\         \
 D --- E - F -- G
e devi andare da A a G.
1) Ti posizione in A
2) Scegli se provare con B o con D (consiglio di valutare i nodi possibili
sempre in senso orario iniziando quello che sta nella direzione del punto di
arrivo).
3) Ti posizioni in B
4) Scegli se provare con C o con F
5) Ti posizioni in C
6) Ti accorgi che questo percorso non č valido (non hai altre scelte e non
sei arrivato in G)
7) Torni indietro di uno e segni C come punto non valido, cioč ti posizioni
in B e C viene cancellato
8) Il prossimo punto valido per B č F
9) Ti posizioni in F
10) Il primo punto valido per F č G
11) Ti posizioni in G e hai un percorso.
In pratica:
- per ogni punto cerchi il primo punto successivo in senso orario.
- se non ha sbocchi torni al punto precedente e lo cancelli.
- ripeti l'operazione.
Cosě trovi il primo percorso.
Il secondo puň essere partendo dal secondo nodo valido di F (il penultimo
punto), tenendo presente che C continua a non esistere piů.
Tieni presente che conviene valutare il tempo di percorrenza di una strada e
non la sua distanza.
Inoltre se valutando il secondo ti accorgi che ci stai impiegando piů tempo
che per il primo interrompi la ricerca e inizi con il terzo.
Finchč hai esaurito i nodi validi.
Questo come principio, poi forse ci sono eccezioni.
Ciao


 OK, getto la spugna, non ci dormo ...
No, affatto! Non getto la spugna!
Non ci dormirņ, ma (incrociando le dita) credo d'aver trovato il metodo...
Come spesso accade in casi del genere, assolutamente, enormemente stupido,
eppur funzionante. ;-)

 ci stavo lavorando. :-)
GP, vai tranqui e non dannarti. Grazie.
Come ho scritto un attimo fa, credo d'aver trovato l'artificio...

 - ripeti l'operazione.
Sì, ho appena provato (sulla carta) un metodo e il concetto di base è quello
che hai descritto, ma, attenzione, senza cancellare niente (ma solo
confrontando sul percorso corrente, non su quelli già archiviati) perchè
devo poter passare nello stesso tratto al quale posso arrivare da più
punti...
Ora mi immergo nelle prove...

 Solo da lui! Qual è il percorso migliore?"
Proviamo a scavare ulteriormente tra i miei neuroni ;-)
La struttura dati che devi usare è un grafo i cui nodi sono le località ed i
cui archi sono le distanze tra le varie località. Se queste distanze sono
non negative (quindi nel nostro caso), per trovare i _cammini ottimi minimi_
tra un nodo dato e tutti gli altri si può utilizzare l'algoritmo di
Dijkstra.
L'idea alla base di questo algoritmo è quella di associare ad ogni nodo
(località) una variabile (si usano delle matrici) che al termine
dell'esecuzione dell'algoritmo conterrà la distanza associata fra il nodo
stesso ed il nodo iniziale. Quindi se esegui l'algoritmo una volta e ti
conservi la matrice ottenuta, avrai a disposizione tutte le distanze delle
varie località dalla località iniziale, a condizione che le distanze tra i
vari nodi (le lunghezze degli archi) non varino. Sinceramente non ricordo
l'algoritmo a memoria, ma mi ricordo che era semplice (iterativo e con un
solo ciclo while) e che graficamente lo svolgevo abbastanza semplicemente
(disegnando il grafo, i sottografi necessari e facendo i calcoli con carta e
penna). Probabilmente se provi a fare una ricerca su Google te lo ritrovi
già bello e codificato (prova anche a cercare Floyd-Warshall, dovrebbero
essere gli autori di una versione più complessa, valida anche per grafi con
archi di costo negativo).
-- 
Ale
E` in corso la CFV per per
*it.comp.programmare.dotnet*,
Si può leggere il manifesto su
_it.news.annunci_ o _it.news.votazioni_

 punti...
Infatti devi cancellare (o segnare, come preferisci) *solo* i punti che non
hanno più sbocchi, chioè quei punti che sono o vicoli ciechi o che hanno
collegamenti solo a punti già provati e che sono risultati invalidi (cioè
che a loro volta o erano ciechi o avevano strade già provate senza
successo).
Segui questo concetto: se il punto non ha più strade di sbocco va annullato.
Vedrai che per magia ti rimarranno solo le strade valide.
Per la seconda parte del problema (trovare una via alternativa) è
effettivamente molto più complesso e non sono ancora riuscito a trovare una
soluzione soddisfaciente.
Credo che la struttura minima del problema abbia questa forma base:
G------A
|     /|
|    / |
B---C  |
|  /|  |
| / |  |
D---E--F
E il problema sia arrivare da A a F (o da A in D) e scartare le strade già
percorse e quelle che durante il tragitto mi risultano più lunghe della
prima trovata.


 Dijkstra.
  Approvo, usato da me ( versione ottimizzata del sottoscritto ) in un
progetto alle Ferrovie dello Stato, per individuare il percorso migliore tra
due stazioni.
Ciao
--------------------------------
Inviato via 
http://usenet.libero.it

 Approvo, usato da me (versione ottimizzata del sottoscritto) ..
Una delle altre cose che ricordo è che per matrici dense l'algoritmo di
Dijkstra era O(n^3), ma che con determinate modifiche (c'entra l'algoritmo
di Prim?) si riusciva ad arrivare ad O(n^2), anche se in fondo nel caso
specifico con _molte_ località geografiche prese come nodi ci dovrebbero
essere molti zeri in giro, il che si potrebbe sfruttare per velocizzare il
calcolo. Mi sa che una ripassata dell'argomento non mi farebbe male ;-)
Hai mai letto Numerical Recipes in c?


 eppur funzionante. ;-)
Credo di esserci riuscito!
Per niente ottimizzato eppure velocissimo e senza consumare memoria.
Ora dovrò verificare...
C'è qualcosa che mi lascia perplesso:
dal 5 al 7 ... 186 percorsi, tutti diversi, tutti giusti (almeno ... presi e
verificati a campione)
dal 3 (che pure ha un contatto in più del 5) al 7 ... solo 45 ... boh!

 cosa che partire dall'altro e arrivare all'uno.
Eh eh , sono rientrato adesso mezzo fracico ( sia fuori che dentro ) quindi
cerco di spiegarmi mehlio , allora la caserma e' il centro di un macro
bersaglio di freccette avete presente ? Ora immaginate questo bersaglio
diviso in centri concentrici e in 12 raggi come le ore di un orologio bene ,
ora la distanza la calcolo dal punto X al CENTRO del bersaglio ( si paperino
i pesi li calcolo dal centro verso X senno' non passo per i sensi unici
^_^ )
ok quindi diciamo che X sia nel terzo cerchio che dista da 100 a 150km dal
centro e che sia nel settore 1 (come l'ora di un orologio) e che quindi
considereremo all'inizio solo il settore 1 e man mano che ci avviciniamo al
centro anche gli adiacenti , ho tentato di rappresentarlo qui :
http://members.lycos.co.uk/gigio2k/lupo1.jpg
 bene , ora la e' sensato
muoversi SOLO all'interno del settore 1 andando da X a A
diciamo che sei nel settore verde1 ci sono ingressi di autostrade (pesoalto)
?no , allora spostati nei nodi vicini sempre nella zona verde ...
Ci sono superstrade che dalle vicinanze di A arrivano a qualche nodo qiu ?
    si : ok prendila
    no : cerca le provinciali
se ti va bene dal verde con i pesi alti ti sposti al bianco del centro , con
le supestrade la distanza e' minore con le provinciali ancora meno
 
http://members.lycos.co.uk/gigio2k/lupo2.jpg
 qui vedi in sezione come
arrivare da X a A con i diversi pesi , i rettangoli alti hanno pesi maggiori
quelli bassi pesi minori
quindi diciamo che sia da A che da X hai i nodi delle autostrade + vicine
quindi essendo in cerchi diversi devi per forza testare prima i nodi delle
autostrade (1 rettangolo in alto)
quindi da ostia a chieti avrai che Ostia ha il casello di roma come nodo
vicino con peso maggiore e chieti avra' Pescara , ora cerchi TRAI POCHI NODI
DELLE AUTOSTRADE se puoi arrivare da Roma a Pescara , che culo c'e' una
strada allora sei arrivato da ostia a chieti
e se dalla provincia di chieti volessi arrivare a ostia ? Allora , il
paesino sfigato ha vicino chieti a 25km chieti ha peso 2, a 30Km ho Pescara
con peso 1 dove vado ? io andrei a Pescara perche' so che ha peso maggiore e
quindi do una priorita' a Pescara , poi da pescara riprendo la srtada di
prima per arrivare a roma , poi da roma scendo al rettangolo inferiore fino
a ostia , a ostia scendero' ancora fino ad arrivare al quartiere , via e num
...
io zanna e il papero e anche tu stiamo dicendo la stessa cosa , tu hai solo
il dubbio di come arrivarci ? Ripensa al "senso orario" che accennava Zanna
, 
http://members.lycos.co.uk/gigio2k/lupo3.jpg
 ora stampati questo in coccia
, Tu sei in X e la caserma e' A ,
i lati del tuo ottagono sono i nodi vicini , noti che hai la "A" che culo
sei arrivato , memorizza strada XA100Km vai avanti a testare gli altri nodi
vicini a X scopri C e segni XC50Km trovi che il nodo + vicino e' a 60Km ed
e' in Nodo B quindi segni XCB110Km hai cannato torna indietro e segna C con
il rosso , quindi in C non ci passerai per i test successivi , eravamo a
XB50km continui col secondo nodo di B che culo c'e' A , vediamo la distanza
XBA70Km bene , ora ovviamente hai 2 strade :
XA 100Km
XBA 70Km
ora Teoricamente prenderesti la strada XBA di 70Km ma vai a controllare il
peso e scopri che il ramo BA ha peso 5 ( strada sterrata di campagna) che
quindi abbassa la percorrenza al 50% in meno
quindi se vai a 100Km/h ci metti
XA 100Km 1h~
XBA 70Km 1h~
cavolo siamo ancora pari , allora controlla il numero dei nodi cosi da fare
la strada + dritta ! quindi vince XA !
NB: l'ordine dei controlli e' stato fatto a cavolo sei tu che devi scegliere
cosa testare per prima , se cercare di passare per prima per le autostrade o
cercare la strada con meno nodi !
Poi mi sta venendo un altro metodo in mente ma non te lo dico :p e' solo una
variante che ho visto su un poliziesco americano ... aspettiamo domani pero'
:p
-- 
<Gigio2K>
Sito Comune
Nokia -> I.T.H.N. -> 
http://www.ithn.it/
VB -> I.C.L.VB -> 
http://www.it-lang-vb.net/

 Insisto, li voglio tutti e poi (o durante) li critico.
eddaje , allora ti devo spiegare l'altra variante che avevo in mente ? ok
l'hai voluto tu :
Dividi TUTTA LA CARTINA in settori e dimentica i nodi , ogni macro settore
(citta') e' diviso in sottosettore(quartieri) e ancora in vie,  ora dato che
la partenza e' sempre nota calcolati prima Tutti i vari percorsi tra la tua
caserma e ogni Macro settore .
Es: la tua caserma sta nel macro settore Lazio , calcolati tutte le strade
migliori per arrivare nei Macro settori vicini Es:
Lazio Abruzzo avrai la A24 e la A25
LazioEmiliaromagna avrai un altre 3 4 strade e cosi via
ora passa da ogni macro quartiere a calcolare le sotto strade per esempio
nel Settore LAZIO arai molti sottosettori tipo ROMA-OSTIA ROMA-CERVETERI
ecc.. e continua cosi
ora hai un macrodatabase diviso in tutte le strade migliori gia' calcolate ,
ti arriva una chiamata in che settore e' ? settore LAZIO ok anche la caserma
e' nel settore Lazio allora sendiamo , siamo nella nostra sotto matrice in
cui la Caserma si trova nella casella A1 e la chiamata in C4 bene , tra le
celle hai gia' l'elenco delle strade e sai che tra A1 e C4 ci sono 30 strade
, quale di queste 30 finisce + vicino alla chiamata ? vedilo nel
sottosottosettore(quartiere) ok eccole ne hai trovate 5 sparale sul monitor
prima che bruci tutto .
Per calcolare le strade adotti un metodo brutale ma efficace , pensa ai
settori come a dei quadrati , ora se hai :
A1 A2 A3
B1 B2 B3
C1 C2 C3
per andare da A1 a A2 calcolerai SOLO le strade che hai nel lato Destro di
A1 e Sinistro di A2 e memorizza le distanze , diciamo che cosi hai che dal
centro del quadrato A1 al centro del quadrato A2 hai 10 strade migliori (le
hai calcolate tutte offline) e cosi via , dopo alcuni mesi avrai la lista di
tutte le strade possibili e quindi ad ogni interrogazione al db non farai
altro che testare tra le varie tabelle tra le strade + brevi gia' scremate
qual'e' il percorso migliore , in pratica e' come faresti tu se dalla
provincia di Firenze dovresti andare in provincia di Pescara cosa fa la tua
mente ?
Vede in che direzione e' Pescara e calcola l'autostrada da Firenze a Pescara
passando trai vari nodi , ecco , ci sono solo 3possibilita' per le
autostrade , Firenze>Roma>Pescara o Firenze>Bologna>Pescara
vedi ? hai gia' coperto una gran parte del tuo percorso scartando TUTTE LE
STRADINE che ti portano da Firenze a Pescara , ora prendi i due settori
PESCARA e FIRENZE , cosa fai ? dalla provincia di firenze cerchi l'ingresso
+ vicino , c'e' una superstrada ? no ok allora ti restano 300strade
possibili cosa fai ? vedi a mente quelle migliori e ne prendi una , entri in
autostrada e quando sei vicino all'uscita pescara chiami me o paperino e ti
diciamo la strada migliore per arrivare da noi e prenderci sto benedetto
caffe' ^_^


 Eh eh , sono rientrato adesso mezzo fracico ( sia fuori che dentro )
quindi
quindi sei ciucco? ;-)
A parte gli scherzi, Gigio, ho letto velocissimamente il tuo postone. Hai
fatto un lavoro del diavolo, grazie. Domani me lo rileggo meglio e con
attenzione.
Comunque, per farla breve, credo di aver risolto!
Dalla mappa iniziale (quella degli 8 punti) ricavo (come dicevo,
velocissimamente, 0.07 secondi, e senza sprechi di memoria), per esempio: Da
5 a 7, 186 percorsi, da 3 a 7, 45 e, udite-udite, da 7 a 8, ben 224. Tutti
diversi fra loro, tutti corretti, tutti possibili e senza mai andare avanti
e indietro nello stesso tratto. Bingo!!!
Ora la mia intenzione è questa, a grandi linee:
Ogni tratto (strada fra due soli punti) verrà descritto in tutte le sue
caratteristiche: distanza, dimensioni della strada, lavori, pasticci vari,
magari anche sensi unici, etc. A ciascuna di queste informazioni (che
tabellerò e per il programma non vogliono dire assolutamente niente di
"comprensibile", nè di cablato nel codice per garantire la massima
flessibilità e personalizzazione) l'operatore assegnerà "un coefficiente di
disturbo" che, nel corso del calcolo, determinerà (ridurrà o aumenterà)
l'entità della validità di quel tratto. Analizzando (anche durante la
determinazione dei vari percorsi) la somma dei "valori" dei vari tratti,
sarò in grado di decidere quale sia il percorso migliore. Quello
complessivamente migliore, non solo per la minor percorrenza. Può accadere,
ovviamente, che quello risulti impraticabile (magari per un'informazione che
non è stata inserita perchè fresca-fresca). Bene, un altro motivo per cui
volevo (ora li ho, perdindirindina!) tutti i possibili percorsi, è anche
quello di poter dare delle alternative, magari ordinate in funzioni di altre
variabili, come il più veloce, il più breve, il meno trafficato, quello con
meno curve, etc. Insomma, mi son fatto il navigatore. ;-)
Nei prossimi giorni, prima ancora di mettere il tutto nel vero applicativo
(ci vorrà del tempo), magari ordino e ottimizzo un po' e mando al WM.

 caffe' ^_^
Il caffè (e pure il bicchierino) lo beviamo il 29!!!
Facciamo una cosa, per oggi: andiamo a nanna, che è pure ora.
Stanotte dormirò come un bambino col giocattolo nuovo. ;-)

 mando al WM.
sarebbe il massimo, fin'ora ho solo sparato e azzardato su questo argomento
, finalmente vederlo all'opera e in vb e' come un vasetto di Pandora&Nutella
^_^
Notte !


 dal 3 (che pure ha un contatto in più del 5) al 7 ... solo 45 ...
boh!
Tralasciamo il fatto che vuoi riscoprire l'america: il problema dei
cammini minimi è notissimo in teoria dei grafi e ci sono algoritmi
collaudati per risolverlo (Dijkstra, Johnson, Bellman-Ford-Moore) che
risalgono agli anni 50.
Resta comunque un problema interessante e vale comunque la pena
analizzarlo da soli per farsi un'idea delle tecniche necessarie ad
affrontare problemi di questo tipo.
Non capisco perché ti ostini a voler trovare TUTTI i percorsi quando
molti hanno cercato di convincerti che si può potare l'albero di
ricerca. Per potarlo - dici tu - è necessario conoscere i rami! Non
sono d'accordo, ma andiamo avanti.
Se il grafo è quello del primo post, con 8 nodi e 11 archi, non mi
trovo neanche coi risulatati!
Ho scritto al volo un algoritmo esaustivo di visita, dieci righe che
posto sotto, ed ecco i 7 percorsi diversi per la tratta 5-7:
32147, 32547, 32647, 347,
3812547, 3812647, 38147
Solo 7! Se tu ne conti 45 allora stiamo parlando di un grafo diverso
oppure non ho capito come li conti!
Ecco l'algoritmo
Private Sub avanza(ByVal visitati As String, ByVal ultimo As Integer)
  Dim i As Integer, prossimo As String
  If ultimo = target Then
    Debug.Print visitati & CStr(ultimo)
    Exit Sub
  End If
  For i = 1 To UBound(ultimo)
    prossimo = CStr(adiacenti(ultimo)(i))
    If InStr(visitati, prossimo) = 0 Then
      avanza visitati & ultimo, prossimo
    End If
  Next i
End Sub
il grafo è questo (ho imposto "Option Base 1"):
adiacenti = Array(Array(2,4,8), Array(1,3,5,6), _
            Array(2,4,8), Array(1,3,5,6,7), _
            Array(2,4), Array(2,4), _
            Array(4), Array(1, 3))
Per esempio, adiacenti(2)(3)=5 perché il terzo nodo raggiungibile da 2
è 5.
La chiamata principale è
target = 7
avanza "", 3
--
Ciao, Silv:o)

 oppure non ho capito come li conti!
Esatto. da 3 a 7 ci sono solo 7 percorsi possibili (e non 45) e la cosa
può essere controllata facilmente anche a mano (finché si tratta di un
grafo così piccolo) e per la tratta 5-7 ancora meno (5).
Io credo che abbia ottenuto questi numeri perché (e non ne capisco il
motivo) vuole permettere ad un percorso di ripassare più volte per uno
stesso punto, come per esempio nei percorsi (che *non* devono essere 
presi in considerazione) 5-4-3-2-6-4-7 o nel 5-2-6-4-1-2-3-4-7.
Ciao


 dall'inizio...
Sinceramente non saprei dirti come funziona, io so che non puo' essere
perfetto perche' e' uno dei tipici esempi che fanno i libri quando si parla
del Problema dell'Arresto.
Pero', so anche che concentrarsi solo sui punti vicini o sulla direzione non
è quasi mai la strada giusta per la risoluzione: nel caso in questione, per
esempio, potresti voler fare molti chilometri in direzione opposta della tua
destizione per imboccare un'autostrada o un'altra strada di grande
scorrimento per accorciare il percorso.
Non so esattamente quale 'trucco' (approssimazione) l'algoritmo usa per
calcolare questo particolare risultato, so che spesso si usa una tecnica
detta Annealing, mutuata dalla Termodinamica (e che alcuni vorrebbero
integrare con la meccanica quantistica).
Una cosa simile è il problema che affrontano le formiche per trovare la
fonte di cibo piu' vicina: per risolverlo loro usano molti operai
esploratori e la caratteristica volatilità dei loro feromoni, mi pare che ci
siano esperimenti per 'computerizzare' questo metodo, ma non so a che punto
siano.
Ciao
Luca

*H.P.L.* ha scritto:

Sì, posso passare più volte dallo stesso punto se questo ha diverse
diramazioni.
Scusate la lunghezza,
Al momento, _senza ottimizzazione alcuna_,
Da 5 a 7, io ottengo questo:
1: 5 2 1 4 3 2 6 4 1 2 3 4 7
2: 5 2 1 4 3 2 6 4 1 8 3 4 7
3: 5 2 1 4 3 2 6 4 7
4: 5 2 1 4 3 8 1 2 3 4 1 8 3 2 6 4 7
5: 5 2 1 4 3 8 1 2 3 4 7
6: 5 2 1 4 3 8 1 2 6 4 1 8 3 4 7
7: 5 2 1 4 3 8 1 2 6 4 7
8: 5 2 1 4 6 2 3 4 1 2 6 4 7
9: 5 2 1 4 6 2 3 4 1 8 3 2 6 4 7
10: 5 2 1 4 6 2 3 4 7
11: 5 2 1 4 6 2 3 8 1 2 6 4 1 8 3 4 7
12: 5 2 1 4 6 2 3 8 1 2 6 4 7
13: 5 2 1 4 7
14: 5 2 1 8 3 2 6 4 1 2 3 4 7
15: 5 2 1 8 3 2 6 4 1 2 3 8 1 4 7
16: 5 2 1 8 3 2 6 4 3 8 1 2 3 4 7
17: 5 2 1 8 3 2 6 4 3 8 1 4 6 2 3 4 7
18: 5 2 1 8 3 2 6 4 3 8 1 4 7
19: 5 2 1 8 3 2 6 4 7
20: 5 2 1 8 3 4 1 2 3 8 1 4 3 2 6 4 7
21: 5 2 1 8 3 4 1 2 3 8 1 4 7
22: 5 2 1 8 3 4 1 2 6 4 3 8 1 4 7
23: 5 2 1 8 3 4 1 2 6 4 7
24: 5 2 1 8 3 4 6 2 3 8 1 2 6 4 7
25: 5 2 1 8 3 4 6 2 3 8 1 4 3 2 6 4 7
26: 5 2 1 8 3 4 6 2 3 8 1 4 7
27: 5 2 1 8 3 4 7
28: 5 2 3 4 1 2 6 4 3 2 1 4 7
29: 5 2 3 4 1 2 6 4 3 8 1 4 7
30: 5 2 3 4 1 2 6 4 7
31: 5 2 3 4 1 8 3 2 1 4 3 8 1 2 6 4 7
32: 5 2 3 4 1 8 3 2 1 4 7
33: 5 2 3 4 1 8 3 2 6 4 3 8 1 4 7
34: 5 2 3 4 1 8 3 2 6 4 7
35: 5 2 3 4 6 2 1 4 3 2 6 4 7
36: 5 2 3 4 6 2 1 4 3 8 1 2 6 4 7
37: 5 2 3 4 6 2 1 4 7
38: 5 2 3 4 6 2 1 8 3 2 6 4 3 8 1 4 7
39: 5 2 3 4 6 2 1 8 3 2 6 4 7
40: 5 2 3 4 7
41: 5 2 3 8 1 2 6 4 1 8 3 2 1 4 7
42: 5 2 3 8 1 2 6 4 1 8 3 4 6 2 1 4 7
43: 5 2 3 8 1 2 6 4 1 8 3 4 7
44: 5 2 3 8 1 2 6 4 3 2 1 4 7
45: 5 2 3 8 1 2 6 4 3 2 1 8 3 4 7
46: 5 2 3 8 1 2 6 4 7
47: 5 2 3 8 1 4 3 2 1 8 3 4 1 2 6 4 7
48: 5 2 3 8 1 4 3 2 1 8 3 4 7
49: 5 2 3 8 1 4 3 2 6 4 1 8 3 4 7
50: 5 2 3 8 1 4 3 2 6 4 7
51: 5 2 3 8 1 4 6 2 1 8 3 2 6 4 7
52: 5 2 3 8 1 4 6 2 1 8 3 4 1 2 6 4 7
53: 5 2 3 8 1 4 6 2 1 8 3 4 7
54: 5 2 3 8 1 4 7
55: 5 2 6 4 1 2 3 4 6 2 1 4 7
56: 5 2 6 4 1 2 3 4 7
57: 5 2 6 4 1 2 3 8 1 4 3 2 1 8 3 4 7
58: 5 2 6 4 1 2 3 8 1 4 6 2 1 8 3 4 7
59: 5 2 6 4 1 2 3 8 1 4 7
60: 5 2 6 4 1 8 3 2 1 4 3 8 1 2 3 4 7
61: 5 2 6 4 1 8 3 2 1 4 6 2 3 4 7
62: 5 2 6 4 1 8 3 2 1 4 7
63: 5 2 6 4 1 8 3 4 6 2 1 4 7
64: 5 2 6 4 1 8 3 4 6 2 3 8 1 4 7
65: 5 2 6 4 1 8 3 4 7
66: 5 2 6 4 3 2 1 4 6 2 3 4 7
67: 5 2 6 4 3 2 1 4 7
68: 5 2 6 4 3 2 1 8 3 4 1 2 3 8 1 4 7
69: 5 2 6 4 3 2 1 8 3 4 6 2 3 8 1 4 7
70: 5 2 6 4 3 2 1 8 3 4 7
71: 5 2 6 4 3 8 1 2 3 4 1 8 3 2 1 4 7
72: 5 2 6 4 3 8 1 2 3 4 6 2 1 4 7
73: 5 2 6 4 3 8 1 2 3 4 7
74: 5 2 6 4 3 8 1 4 6 2 1 8 3 4 7
75: 5 2 6 4 3 8 1 4 6 2 3 4 7
76: 5 2 6 4 3 8 1 4 7
77: 5 2 6 4 7
78: 5 4 1 2 3 4 6 2 1 4 3 2 6 4 7
79: 5 4 1 2 3 4 6 2 1 4 7
80: 5 4 1 2 3 4 6 2 1 8 3 2 6 4 3 8 1 4 7
81: 5 4 1 2 3 4 6 2 1 8 3 2 6 4 7
82: 5 4 1 2 3 4 7
83: 5 4 1 2 3 8 1 4 3 2 1 8 3 4 7
84: 5 4 1 2 3 8 1 4 3 2 6 4 7
85: 5 4 1 2 3 8 1 4 6 2 1 8 3 2 6 4 7
86: 5 4 1 2 3 8 1 4 6 2 1 8 3 4 7
87: 5 4 1 2 3 8 1 4 7
88: 5 4 1 2 6 4 3 2 1 4 6 2 3 4 7
89: 5 4 1 2 6 4 3 2 1 4 7
90: 5 4 1 2 6 4 3 2 1 8 3 4 6 2 3 8 1 4 7
91: 5 4 1 2 6 4 3 2 1 8 3 4 7
92: 5 4 1 2 6 4 3 8 1 4 6 2 1 8 3 4 7
93: 5 4 1 2 6 4 3 8 1 4 6 2 3 4 7
94: 5 4 1 2 6 4 3 8 1 4 7
95: 5 4 1 2 6 4 7
96: 5 4 1 8 3 2 1 4 3 8 1 2 3 4 7
97: 5 4 1 8 3 2 1 4 3 8 1 2 6 4 7
98: 5 4 1 8 3 2 1 4 6 2 3 4 7
99: 5 4 1 8 3 2 1 4 6 2 3 8 1 2 6 4 7
100: 5 4 1 8 3 2 1 4 7
101: 5 4 1 8 3 2 6 4 3 8 1 2 3 4 6 2 1 4 7
102: 5 4 1 8 3 2 6 4 3 8 1 2 3 4 7
103: 5 4 1 8 3 2 6 4 3 8 1 4 6 2 3 4 7
104: 5 4 1 8 3 2 6 4 3 8 1 4 7
105: 5 4 1 8 3 2 6 4 7
106: 5 4 1 8 3 4 6 2 1 4 3 2 6 4 7
107: 5 4 1 8 3 4 6 2 1 4 3 8 1 2 6 4 7
108: 5 4 1 8 3 4 6 2 1 4 7
109: 5 4 1 8 3 4 6 2 3 8 1 2 6 4 3 2 1 4 7
110: 5 4 1 8 3 4 6 2 3 8 1 2 6 4 7
111: 5 4 1 8 3 4 6 2 3 8 1 4 3 2 6 4 7
112: 5 4 1 8 3 4 6 2 3 8 1 4 7
113: 5 4 1 8 3 4 7
114: 5 4 3 2 1 4 6 2 3 4 1 2 6 4 7
115: 5 4 3 2 1 4 6 2 3 4 7
116: 5 4 3 2 1 4 6 2 3 8 1 2 6 4 1 8 3 4 7
117: 5 4 3 2 1 4 6 2 3 8 1 2 6 4 7
118: 5 4 3 2 1 4 7
119: 5 4 3 2 1 8 3 4 1 2 3 8 1 4 7
120: 5 4 3 2 1 8 3 4 1 2 6 4 7
121: 5 4 3 2 1 8 3 4 6 2 3 8 1 2 6 4 7
122: 5 4 3 2 1 8 3 4 6 2 3 8 1 4 7
123: 5 4 3 2 1 8 3 4 7
124: 5 4 3 2 6 4 1 2 3 4 6 2 1 4 7
125: 5 4 3 2 6 4 1 2 3 4 7
126: 5 4 3 2 6 4 1 2 3 8 1 4 6 2 1 8 3 4 7
127: 5 4 3 2 6 4 1 2 3 8 1 4 7
128: 5 4 3 2 6 4 1 8 3 4 6 2 1 4 7
129: 5 4 3 2 6 4 1 8 3 4 6 2 3 8 1 4 7
130: 5 4 3 2 6 4 1 8 3 4 7
131: 5 4 3 2 6 4 7
132: 5 4 3 8 1 2 3 4 1 8 3 2 1 4 7
133: 5 4 3 8 1 2 3 4 1 8 3 2 6 4 7
134: 5 4 3 8 1 2 3 4 6 2 1 4 7
135: 5 4 3 8 1 2 3 4 6 2 1 8 3 2 6 4 7
136: 5 4 3 8 1 2 3 4 7
137: 5 4 3 8 1 2 6 4 1 8 3 2 1 4 6 2 3 4 7
138: 5 4 3 8 1 2 6 4 1 8 3 2 1 4 7
139: 5 4 3 8 1 2 6 4 1 8 3 4 6 2 1 4 7
140: 5 4 3 8 1 2 6 4 1 8 3 4 7
141: 5 4 3 8 1 2 6 4 7
142: 5 4 3 8 1 4 6 2 1 8 3 2 6 4 1 2 3 4 7
143: 5 4 3 8 1 4 6 2 1 8 3 2 6 4 7
144: 5 4 3 8 1 4 6 2 1 8 3 4 1 2 6 4 7
145: 5 4 3 8 1 4 6 2 1 8 3 4 7
146: 5 4 3 8 1 4 6 2 3 4 1 2 6 4 7
147: 5 4 3 8 1 4 6 2 3 4 1 8 3 2 6 4 7
148: 5 4 3 8 1 4 6 2 3 4 7
149: 5 4 3 8 1 4 7
150: 5 4 6 2 1 4 3 2 6 4 1 2 3 4 7
151: 5 4 6 2 1 4 3 2 6 4 1 8 3 4 7
152: 5 4 6 2 1 4 3 2 6 4 7
153: 5 4 6 2 1 4 3 8 1 2 3 4 1 8 3 2 6 4 7
154: 5 4 6 2 1 4 3 8 1 2 3 4 7
155: 5 4 6 2 1 4 3 8 1 2 6 4 1 8 3 4 7
156: 5 4 6 2 1 4 3 8 1 2 6 4 7
157: 5 4 6 2 1 4 7
158: 5 4 6 2 1 8 3 2 6 4 1 2 3 4 7
159: 5 4 6 2 1 8 3 2 6 4 1 2 3 8 1 4 7
160: 5 4 6 2 1 8 3 2 6 4 3 8 1 2 3 4 7
161: 5 4 6 2 1 8 3 2 6 4 3 8 1 4 7
162: 5 4 6 2 1 8 3 2 6 4 7
163: 5 4 6 2 1 8 3 4 1 2 3 8 1 4 3 2 6 4 7
164: 5 4 6 2 1 8 3 4 1 2 3 8 1 4 7
165: 5 4 6 2 1 8 3 4 1 2 6 4 3 8 1 4 7
166: 5 4 6 2 1 8 3 4 1 2 6 4 7
167: 5 4 6 2 1 8 3 4 7
168: 5 4 6 2 3 4 1 2 6 4 3 2 1 4 7
169: 5 4 6 2 3 4 1 2 6 4 3 8 1 4 7
170: 5 4 6 2 3 4 1 2 6 4 7
171: 5 4 6 2 3 4 1 8 3 2 1 4 3 8 1 2 6 4 7
172: 5 4 6 2 3 4 1 8 3 2 1 4 7
173: 5 4 6 2 3 4 1 8 3 2 6 4 3 8 1 4 7
174: 5 4 6 2 3 4 1 8 3 2 6 4 7
175: 5 4 6 2 3 4 7
176: 5 4 6 2 3 8 1 2 6 4 1 8 3 2 1 4 7
177: 5 4 6 2 3 8 1 2 6 4 1 8 3 4 7
178: 5 4 6 2 3 8 1 2 6 4 3 2 1 4 7
179: 5 4 6 2 3 8 1 2 6 4 3 2 1 8 3 4 7
180: 5 4 6 2 3 8 1 2 6 4 7
181: 5 4 6 2 3 8 1 4 3 2 1 8 3 4 1 2 6 4 7
182: 5 4 6 2 3 8 1 4 3 2 1 8 3 4 7
183: 5 4 6 2 3 8 1 4 3 2 6 4 1 8 3 4 7
184: 5 4 6 2 3 8 1 4 3 2 6 4 7
185: 5 4 6 2 3 8 1 4 7
186: 5 4 7
Da 3 a 7 questo:
1: 3 2 1 4 5 2 6 4 1 2 5 4 7
2: 3 2 1 4 5 2 6 4 7
3: 3 2 1 4 6 2 5 4 1 2 6 4 7
4: 3 2 1 4 6 2 5 4 7
5: 3 2 1 4 7
6: 3 2 5 4 1 2 6 4 5 2 1 4 7
7: 3 2 5 4 1 2 6 4 7
8: 3 2 5 4 6 2 1 4 5 2 6 4 7
9: 3 2 5 4 6 2 1 4 7
10: 3 2 5 4 7
11: 3 2 6 4 1 2 5 4 6 2 1 4 7
12: 3 2 6 4 1 2 5 4 7
13: 3 2 6 4 5 2 1 4 6 2 5 4 7
14: 3 2 6 4 5 2 1 4 7
15: 3 2 6 4 7
16: 3 4 1 2 5 4 6 2 1 4 5 2 6 4 7
17: 3 4 1 2 5 4 6 2 1 4 7
18: 3 4 1 2 5 4 7
19: 3 4 1 2 6 4 5 2 1 4 6 2 5 4 7
20: 3 4 1 2 6 4 5 2 1 4 7
21: 3 4 1 2 6 4 7
22: 3 4 5 2 1 4 6 2 5 4 1 2 6 4 7
23: 3 4 5 2 1 4 6 2 5 4 7
24: 3 4 5 2 1 4 7
25: 3 4 5 2 6 4 1 2 5 4 6 2 1 4 7
26: 3 4 5 2 6 4 1 2 5 4 7
27: 3 4 5 2 6 4 7
28: 3 4 6 2 1 4 5 2 6 4 1 2 5 4 7
29: 3 4 6 2 1 4 5 2 6 4 7
30: 3 4 6 2 1 4 7
31: 3 4 6 2 5 4 1 2 6 4 5 2 1 4 7
32: 3 4 6 2 5 4 1 2 6 4 7
33: 3 4 6 2 5 4 7
34: 3 4 7
35: 3 8 1 2 5 4 6 2 1 4 5 2 6 4 7
36: 3 8 1 2 5 4 6 2 1 4 7
37: 3 8 1 2 5 4 7
38: 3 8 1 2 6 4 5 2 1 4 6 2 5 4 7
39: 3 8 1 2 6 4 5 2 1 4 7
40: 3 8 1 2 6 4 7
41: 3 8 1 4 5 2 6 4 1 2 5 4 7
42: 3 8 1 4 5 2 6 4 7
43: 3 8 1 4 6 2 5 4 1 2 6 4 7
44: 3 8 1 4 6 2 5 4 7
45: 3 8 1 4 7

 presi in considerazione) 5-4-3-2-6-4-7 o nel 5-2-6-4-1-2-3-4-7.
Ecco, (sto guardando il primo percorso che hai indicato, in particolare nei
tratti 4-3 e nel finale 4-7) questo rappresenta un perfetto caso da ...
discutere (uso ! per indicare il punto di destinazione):
Il 4 porta direttamente al 7! e quindi non avrebbe senso dal 4 andare sul 3
(o 5 o 6) per poi (molto dopo) tornare sul 4 e finalmente arrivare al 7!.
C'ero già. ;-)
Vero e lo terrò sicuramente in considerazione in fase di ottimizzazione, ma
_ipotizziamo_ che il 7! sia raggiungibile anche direttamente dal 3 (nella
mappa così non è, ma proverò a modificarla).
Se scartassi la deviazione 4-3-7! (solo per il fatto che, trovandomi sul 4,
mi butterei subito sul 7! di destinazione) e il tratto 4-7! avesse dei
lavori in corso, non riuscirei mai a "criticare" i due percorsi e
consigliare il, pur più lungo, 4-3-7!

 risalgono agli anni 50.
:) Mi accorgo adesso di avere un libro con un capitolo dedicato a questo
problema :P
E' un libro che quando la commessa del negozio ha visto che lo compravo ha
fatto un sorrisone con sconto annesso :PPP


 sono d'accordo, ma andiamo avanti.
Il Cristoforo Colombo del 2000 sa che sta andando a spanne e, per non
sbagliare, va da tutte le parti pur di essere certo di riscoprire l'America
(e magari pure le Indie, come avrebbe voluto) ;-)
Seriamente, Silvio (o Sergio?), io _non so_ come fare a potare qualcosa che
non ho. Ti chiederei ancora un minuto, quando e se vuoi, per farmi un
esempio. Grazie.
PS: Proverň sicuramente il tuo codice... che parrebbe, per restare in tema,
l'uovo di Colombo... (o di colombo?, mah, ho dormito poco)

 , Tu sei in X e la caserma e' A ,
<inciso>
Visto cosa succede a mettere uno spazio prima dei segni di punteggiatura? :)
</inciso>
Piccola ottimizzazione spicciola: anzichč scegliere il prossimo nodo in
senso orario prova scegliendo il piů veloce da raggiungere.
In questo modo in molti casi potrebbe bastarti la prima strada trovata.
Ciao


 Da 3 a 7 questo:
[cut]
Gli unici percorsi validi da 3 a 7 sono:
1: 3 4 7
2: 3 2 5 4 7
3: 3 2 1 4 7
4: 3 2 6 4 7
5: 3 8 1 4 7
6: 3 8 1 2 5 7
7: 3 8 1 2 6 4 7
Tutti gli altri *non* potranno *MAI* essere migliori di questi.
Ciao.


 consigliare il, pur più lungo, 4-3-7!
Per prima cosa considera che le strade sono quelle che sono, non basta
"inventare" strade sulla mappa per rendere raggiungibile un postoi che
in realtà non lo è.
Poi, nessuno vuole escludere il 4-3-7 (ipotizzando un collegamento 3-4),
però tu passi per un punto comunque una sola volta. 
Ed in ogni caso, ti ripeto ancora, conoscere tutti i percorsi possibil
(pur tralasciando quelli non validi con punti ripetuti) *non* ti serve a
nulla.
Ciao.


 esempio. Grazie.
Speravo di essere stato chiaro. Consideriamo semplicemente la lunghezza
delle strade per rendere più semplice l'esempio, ma il peso di un tratto
di strada verrà poi valutato in base a molti fattori, per esempio il
tratto 1-2 potrebbe essere molto veloce ma con un sottopasso con altezza
massima 2,50 m, per cui alcuni automezzi potrebbero passarci ed altri
no. L'algoritmo di calcolo del peso terrebbe conto di questo in base
all'automezzo che deve giungere a destinazione, ecc...
Consideriamo nuovamente il tratto 5-7 e queste lunghezze:
5-4 = 10 Km
5-2 = 30 KM
4-7 = 20 Km
2-3 = 5 Km
3-4 = 20 Km
4-1 = 50 Km
4-6 = 30 Km
... 
Iniziamo a valutare un percorso iniziando dagli archi di peso minore
(lunghezza minore)
5-4 = 10 Km 
4-7 = 20 Km
5-4-7 = 30 Km
Secondo percorso:
5-2 = 30 Km
A questo punto senza dover finire di valutare questo percorso e senza
valutare tutti gli altri sai già che nessuno potrà essere più breve di
5-4-7
Quindi *non* ti serve conoscere tutti i percorsi.


 Hai mai letto Numerical Recipes in c?
 No, mai letto!


 ha diverse diramazioni.
Premetto una cosa.
Io normalmente posto su it.hobby.enigmi, e lì questi problemi ce li
beviamo a colazione (molte faccine). Per cui sono interessato
all'aspetto *combinatorio* del problema. Su quello informatico, altri
interlocutori stanno sostendo le stesse mie tesi, quindi mi sento ben
rappresentato.
E mi pare di capire che almeno su un punto, *non ha senso passare due
volte per lo stesso punto* ti stiano (stiamo?) convingendo.
Comunque, se anche permettessi il passaggio multiplo, ancora non mi
trovo con i tuoi calcoli.
Prima ho provato a sostituire il controllo dell'unicità del nodo
all'interno del percorso con un controllo sull'unicità della tratta,
cambiando
If InStr(visitati, prossimo) = 0 Then
in
If InStr(visitati, CStr(ultimo) & prossimo) = 0
ovvero in linguaggio naturale "se il prossimo passo non è un nodo già
visitato allora" in "se la tratta ultimo-prossimo non è presente nel
percorso già fatto allora"
Risultato per la tratta 3-7: 77132 percorsi.
Il problema è che ci sono percorsi del tipo 32123... che comportano
anche inversioni di marcia come la sequenza 212. Anche aggiungendo
all'If un controllo che il penultimo passo sia diverso dal prossimo,
.. And (Right$(visitati, 1)<> prossimo)
restano pur sempre 923 percorsi.
Ad esempio, il percorso 321438123452647 tu non ce l'hai. Perché?
Un momento, mentre scrivo ho qui sotto le tue soluzioni, ed il 3 non è
mai ripetuto.
Infatti, se metto un ulteriore vincolo (.. And prossimo <>"3") ecco il
45.
Tutto a posto. Però mica è logico: per il nodo iniziale non ci si
ripassa, per gli altri sì *ma non subito*.
--
Ciao, Silv:o) <---NOME

 Come ho scritto un attimo fa, credo d'aver trovato l'artificio...
OK, sto leggendo il resto del 3ad. Felice per te
e il tuo giocattolo nuovo :-)
Bye, G.

 Tutti gli altri *non* potranno *MAI* essere migliori di questi.
Vero e (solo ora, per me) lapalissiano: Se, nello stesso percorso, ripasso
da un punto, ho solo fatto della strada in più. Anche se fosse un autodromo
tutto per me, sarebbe comunque strada in più.
Grazie dell'illuminazione e scusa la testardaggine.

 ripassa, per gli altri sì *ma non subito*.
Hai ragione, infatti ora ho capito quel che prima non mi era evidente,
ovvero che un nodo qualsiasi già passato (parliamo sempre del singolo
percorso in fase di costruzione) è del tutto analogo al punto di partenza,
quindi se torno dove già ero, punto di partenza o interno che sia, ho
comunque fatto della strada per niente. Se è per bighellonare può andar
bene, ma vedere un mezzo dei VVFF che continua a girare in tondo, non è il
massimo. ;-)
Nel frattempo ho trovato (sulla carta che ormai mi ha coperto) un altro
metodo per stabilire i tratti privilegiati, partendo dal punto di
destinazione sino a quello di partenza, secondo livelli a scalare. Devo
programmarlo, ma ho la sensazione che possa essere molto più veloce e con
zero scarti perchè il lavoro di preparazione elencherà, in ordine, solo i
tratti possibili...

  No, mai letto!
Se c'è un libro che prima o poi mi regalerò è proprio quello, è uno scrigno
pieno di tesori algoritmici ;-)
Tornando al problema dei cammini ottimi minimi, mi sono andato a rivedere
l'algoritmo di Dijkstra, e su un testo (Introduction to Algorithms di
Cormen, Leiserson e Rivest), in una piccola nota, ho letto che alcuni
ricercatori (Ahuja, Mehlhorn, Orlin e Tarjan) ne hanno pubblicato
recentemente (1988) una versione molto ottimizzata. Ho trovato l'articolo
(intitolato "Faster algorithms for the shortest path problem") su una banca
dati di articoli scientifici (questo è l'URI:
http://doi.acm.org/10.1145/77600.77615
), ma purtroppo si può leggere
soltanto l'abstract, il testo completo è a pagamento :-(
Nell'abstract gli autori comunque *dichiarano* che al momento della
pubblicazione il loro algoritmo era il meglio fico del bigoncio ;-)


 Grazie dell'illuminazione e scusa la testardaggine.
Ora che hai capito questo ti riconfondo un po' le idee. In realtà è
possibile che il mezzo possa essere costretto a passare più di una 
volta in qualche punto.
Mettiamo per esempio di voler andare da 1 a 7 ed aver stabilito che il
percorso migliore sia la tratta 1-2-3-4-7
L'automezzo sta percorrendo il tratto 1-2 quando si presenta un ostacolo
improvviso e non segnalato in centrale che blocca totalmente la strada.
A questo punto il mezzo non può fare altro che ripassare per punti già
visitati. 
Però, analizzando il problema, la soluzione è semplice, ed è quella di
calcolare il percorso più veloce tra il punto 2 ed il punto 7 avendo
l'accortezza di marcare come impraticabile il tratto 2-3.
Sperando di essere stato chiaro...


 Sperando di essere stato chiaro...
Chiarissimo, grazie.

 prima della partenza.
Esatto, la soluzione sarebbe proprio quella di contattare la caserma e
chiedere un ricalcolo del percorso (partendo non più dalla caserma ma
dal punto in cui si è giunti) escludendo il tratto interrotto.


 prima della partenza.
Un portatile a bordo ? ;-))
Bye, G.

*Paperino* ha scritto:

Perchè non, allora, un navigatore satellitare? :-P

 in ordine, solo i tratti possibili...
Ecco , come faceva quel cartone animato "Cicabum e le motorette" ?
"Te l'avevo detto io Te l'avevo detto io Cicabum brum ..."  ^_^
Un altro aiuto , non tenere conto degli imprevisti in quanto, Appunto,
imprevisti ! Se trovi un incidente su un tratto quello + logico e istintivo
da fare e' aggirarlo perche' col mio metodo (lo stesso che stai preparando
tu) e' molto + lento ricalcolare un persorso dal nodo in cui sei arrivato al
nodo di arrivo , sarebbe + semplice tornare in dietro fino ad un nodo
coincidente su un altro percorso alternativo calcolato sempre dall'arrivo
verso la stazione , esempio :
Percorso A
1-3-4-6-9
4 e' bloccato , chiami la centrale e ti dicono il percorso alternativo
1-3-7-8-10-9
devi tornare in dietro fino al nodo comune ( quindi 3 ) e proseguire sul
nuovo , PROBLEMA : Come je' passi ste informaziuoni per radio ? Secondo me i
film americani ci insegnano sempre, paghiamogli i navigatori satellitari
perche' cosi la centrale e l'automezzo possono sapere in tempo quasi reale
se sta andando verso un incidente che si e' creato mentre l'automezzo era in
viaggio ! E' il futuro , quindi non farebbero altro che anticiparsi sul
futuro anche se ora le tecnologie sat-alarm e GPS on road sono poco usate o
usate male ! :-/
Con questo cosa voglio dire ? non lo so pero' i fatti mi cosano ! ^____^


 serve a nulla.
e se il tratto 4-7 e' chiuso per lavori in corso di fatto e' INESISTENTE
quando calcoli la mappa ! quindi escludi il TRATTO ma non il nodo e per
magia hai la combinazione 4-3-7 che e' l'unica vera e praticabile !!!


 trovata.
gia' infatti alla fine bisognerebbe ordinare l'array di ogni singolo nodo in
modo che il primo da testare sia sempre quello con coficente + basso
E non dobbiamo dimenticarci che se inseriamo un "lavori in corso" i valori
dovranno essere ricalcolati per titti i tratti e nodi annessi !
Come ad esempio le strade trafficate solo in certi orari nelle quali magari:
la mattina alle 6 hanno valori bassi e quindi analizzabili per prima , alle
13 invece escono le scuole e i lavoratori e quindi si satura ed e' giusto
che venga analizzata in coda alla lista !


sia bruciato tutto?
ecco, allora e' ancora piu' facile di quello che avevo ipotizzato
nell'altro post: devi fare solo l'algoritmo del simplesso tra il
nodo-caserma ed il nodo-incendio.
a risolvere la rete comunale di bologna, considerando ovviamente anche
i sensi unici, impiego meno di 3 decimi di secondo. nella peggiore
delle possibilita' trovate.
saluti.
-- 
Gianni Rondinini
Icem s.r.l.
Tel: 
+39 0545 78036
Fax: 
+39 0545 78727

Ho la necessità di calcolare tutti i possibili percorsi (anche quelli
e' un lavoro inutile. la cosa utile e', invece, calcolare il percorso
ottimo che ti porta dal punto che tu sai gia' che sara' quello di
partenza a tutti gli altri punti.
se devi andare in piu' punti e vuoi trovare la sequenza ottima,
invece, la cosa ottima da fare e' trovare il percorso ottimo tra ogni
coppia di nodi e poi fare lo spanning tree della matrice
bidimensionale che hai trovato.
cerca in rete qualcosa su:
- algoritmo del simplesso --e' il piu' facile da implementare, per il
primo punto--
- algoritmo di generazione di spanning tree
considera che con l'algoritmo del simplesso --esistono algoritmi quasi
3 ordini di grandezza piu' veloci-- con una rete di 10.500 nodi e
35.000 archi risolveva il percorso ottimo tra 2 punti presi a caso in
circa 25 centesimi di secondo su un p3-600mhz.
e' stata la mia tesi, ma non posso rilasciare il codice.


La matrice è simmetrica, per cui potrebbe essere conveniente (ma non è
non lo e'. tu stai ipotizzando tutti doppi sensi di circolazione.
devi considerare, nel caso generale, i sensi unici.
il che complica un po' le cose, anche se solo marginalmente.
per il resto, tutto ok.


 - algoritmo di generazione di spanning tree
Sě, grazie Gianni. Se hai letto un po' il tutto, la soluzione (a dir il vero
piů d'una) l'ho giŕ trovata e applicata.
In futuro, se il caso, approfondirň per meglio ottimizzare tempi e modi.


mi sono un pň perso nel 3D, quale soluzione hai adottato?
--
bye BlackMagic
ICQ# 85485468

In futuro, se il caso, approfondirň per meglio ottimizzare tempi e modi.
onestamente, non ho capito che soluzione hai adottato :)
comunque, tanto che sia buona, sara' come quella che ti ho proposto,
che e' quella ottima :)
naturalmente mica mi vanto di quel che ho fatto come tesi: ho "solo"
scritto il codice per implementare un algoritmo di qualcun altro,
ahime' morto 10gg dopo aver discusso la tesi --gli anni passano per
tutti :|--.
il discorso e' che il problema ha complessita' esponenziale e quindi
qualsiasi soluzione che non sia quella ottima che ti ho proposto ti
portera' ad avere tempi di calcolo preoccupanti se hai una rete grande
almeno come quella urbana di un capoluogo di provincia --io ho usato
la rete del comune di bologna--. ad avere 12/15k nodi e 40/50k archi
fai presto --pensa che ogni incrocio-incrocio a doppio senso di
circolazione vale 2 archi-- e quindi posso consigliarti caldamente di
utilizzare un algoritmo *veloce* come il simplesso o, ancora meglio
--ma piu' ghignoso come strutture dati--, l's-dial.
il problema e' che nella tua rete di 8 nodi e 15 archi puoi anche
guardare tutti i percorsi possibili tra 2 punti, calcolarne la
lunghezza --che, poi, il parametro dovrebbe essere una combinazione
lineare tra lunghezza in metri e tempo previsto in secondi-- e
guardare quello piu' conveniente, ma hai visto anche tu che con una
rete cosi' piccola trovi 45 percorsi: immagina con 12.000 nodi e
40.000 archi quanti ne trovi ed il tempo che ci vuole a fare i conti
per tutti quanti...
con reti "reali" e' necessario andare su algoritmi che ad ogni passo
considerino soltanto i percorsi potenzialmente ottimi e scartino
quelli che sicuramente non lo sono. che, tipicamente, sono quasi tutti
quelli breadth-first e qualcuno best-first.
per farla breve, di implementazioni dell'algoritmo del simplesso
--symplex algorhytm-- ne trovi di open source e gia' pronte anche in
rete: basta che ti procui un compilatore c per win --tipo visual
c++--, butti tutto in una dll e chiami le funzioni da vb, come ho
fatto io.
saluti che non voglio farla cadere dall'alto ma cosi' eviti gli errori
che ho gia' fatto io :)


 mi sono un pň perso nel 3D, quale soluzione hai adottato?
Devo fare delle prove (con qualche centinaio di nodi) per scegliere la
migliore, poi pubblicherň.


  Be bisogna vedere poi se è applicabile ad un caso reale, a volte i super
algoritmi sono fini a se stessi ed applicarli "cosi come sono" ad un caso
reale comporta delle modifiche che rendono vane tutte le ottimizzazioni,
cmq...io me lo ottimizzo da solo cosi mi diverto di più :D
Ciaooo


 Sperando di essere stato chiaro...
Ecco, non avevo finito di leggere :)
Ciao
--
Math Parser : 
http://www.neodatatype.net
Sito Comune : 
http://www.it-lang-vb.net

 magia hai la combinazione 4-3-7 che e' l'unica vera e praticabile !!!
Ehm... però nella mappa il punto 7 è collegato solo con il punto 4, per
cui se il tratti 4-7 è chiuso il punto 7 diventa irraggiungibile... Od
ho sbagliato io a disegnare la mappa?


 il che complica un po' le cose, anche se solo marginalmente.
Oltre tutto direi che la rappresentazione attraverso la matrice non è
quella ottimale, perché si tratta di un grafo sparso e non denso...


 tratto sarebbe stato scartato a priori !
Fondamentalmente in questo caso non interessa sapere né la lunghezza
della strada, né il tipo di strada (statale, autostrada, ecc...), né le sue 
varie caratteristiche (larga, stretta, rettilinea, tutta curve, ecc...).
Quello che interessa è una cosa sola: il tempo di percorrenza. Ed è solo
questo che fornirà il peso dei vari archi. Tempo di percorrenza che
andrà calcolato (e memorizzato) in base al tipo di automezzo, perché
un'autovettura potrebbe impiegare meno tempo a percorrere una strada di
10 Km in salita e piena di curve che una strada di 70 Km, ma per
un'autobotte potrebbe non essere così.


 quella ottimale, perché si tratta di un grafo sparso e non denso...
Verissimo. Infatti, pur essendo in tal caso il codice per rilevare i
percorsi più conciso, sono orientato a non adottarlo perchè, in previsione
di molti nodi/tratti con molte informazioni descrittive e inerenti il
calcolo, questi staranno su database e non mi pare il caso di lavorare su
una matrice tutta in memoria (dove, oltretutto, i punti/tratti sono
codificati con codici alfanumerici, non numerici), ma (pur a costo di tempi
maggiori) carico un solo tratto alla volta. Ho già risolto anche il problema
dei sensi unici, oltre che della "sospensione" di nodi e/o tratti.

 ho sbagliato io a disegnare la mappa?
No, non hai sbagliato ed hai ragione. Gigio, immagino, partiva da
quell'ipotesi che io avevo fatto (non corrispondente alla mappa) che il
punto 3 avesse un collegamento anche al punto 4, proprio per evidenziare che
la tratta 4-3-7 avrebbe potuto essere più conveniente (complessivamente)
della 4-7 se questa aveva un "lavori in corso" tale da rallentane la
percorrenza pur più breve in termini di distanza assoluta.

 percorrenza pur più breve in termini di distanza assoluta.
Questo è uno dei motivi per cui ritengo la cosa giusta sia memorizzare 
come informazione relativa ad i vari tratti solo i tempi di percorrenza
(relativi ai vari automezzi). In questo modo anche gestire il caso di
lavori in corso diventa semplicissimo...
Ciao.
-- 
BSD is for UNIX lovers -- linux is for Windows haters.

 lavori in corso diventa semplicissimo...
Ancora più "generalizzabile": Il tratto archivia solo i dati certi e
assoluti, ovvero i due punti e la distanza assoluta. Di fatto, niente altro.
Tramite una tabella ulteriore e separata posso poi aggiungere (a oltranza)
informazioni tali da "valutare" (in + o in - con dei coefficienti) e/o
descrivere il tratto stesso, anche in relazione al mezzo specifico (con
tutte le sue caratteristiche) per il quale sto calcolando il percorso

 tutte le sue caratteristiche) per il quale sto calcolando il percorso
Secondo me basta solo il tempo di percorrenza, comunque potresti utilizzare
benissimo solo la tabella senza memorizzare la distanza assoluta del
tratto, che in definitiva non è di alcuna utilità almeno che tu non
volglia poter utilizzare lo stesso programma anche per altri scopi.
