Newsgroup: it.comp.appl.access
Titolo: Tutte le strade portano ad ACCESS... aiuto!!

Salve a tutti,
vi sottopongo il mio novo rebus: dovrei realizzare un database con le
strade di una regione (autostrade, strade stattali etc...) per trovare
il percorso più comnveniente fra due città. Sembererebbe un tipico
problema di grafi pesati...
Vi dico cosa ho pensato fino ad ora:
- una tabella con tutti le città presenti nella regione
- una tabella che per ogni pezzo di strada con (almeno) tre campi:
città_di_partenza, ciità_di_arrivo, codice_strada.
Con il codice strada, potrei individuare i tratti che fanno parte
della stessa strada (A1, SS23, etc...)
e qui mi sono fermato...
Chi mi vuol dare una mano?? Avrei bisogno anche di qualche riferimenti
che tratti la risoluzione di problemi relativi ai grafo in SQL...
Qualsiasi consiglio/aiuto/rimprovero è bene accetto...
PLEASE!!!
salute

 che tratti la risoluzione di problemi relativi ai grafo in SQL...
Non saprei che dirti... sono problemi di ottimizzazione, ed esistono delle
tecniche per trovare percorsi ragionevolmente ottimali. A quanto ne so non
hai speranze di ottenere il percorso migliore in assoluto se non provando
tutte le combinazioni possibili... ma questo spesso è impossibile in termini
di calcolo (ci metti i secoli se giri molte città).
Fai delle ricerche in rete su "problema del commesso viaggiatore" in genere
lo chiamano così,
troverai vari algoritmi che ti permettono di trovare delle soluzioni
ragionevolmente ottimizate in tempi ragionevolmente brevi.
Tuttavia non ho idea di se possano essere aplicate ai DB, sono problemi di
intelligenza artificiale fondamentalmente...
Tuttavia nessuno ti vieta di usare il DB per avere i dati e di darli in
pasto ad un algoritmo scritto in VBA.
Prova a chiedere anche su    it.comp.ia   (NG di intelligenza artificiale)
Ciao, Max


Grazie per la celerità e per la completezza... accidenti non pensavo
fosse così complicato!
Servo Vostro!

Ciao,
forse posso esserti di aiuto.
Per quanto riguarda il problema in se secondo me la fai un pò semplice. Per
essere più precisi dipende da quello che devi ottenere comunque a grandi
linee penso che dovresti considerare, oltre la lunghezza come ti è già stato
suggerito, anche altri dati tipo i vari tratti (una via ad esempio è
composta da molti tratti), i sensi di marcia (non puoi consigliare di
prendere una strada con senso vietato), e via dicendo.
Non ho una grande esperienza di Access ma essendo una analista che sviluppa
in altri linguaggi ti consiglio di fare un'analisi approfondita della
problematica.
Per quanto riguarda la soluzione del problema ti consiglio un libro (che
puoi trovare in qualche biblioteca):
Turbo C
Guida Completa
H. Schildt
Mc Graw Hill (ed. maggio 1989)
ISBN 88-386-0124-0
Il capitolo 26 spiega come risolvere problemi di questo tipo.
Chiaramente lo spiega in C ma penso che in concetti siano validi.
Cmq per affrontare il problema devi utilizzare un Grafo.
Il Grafo lo puoi implementare tramite liste e quindi tramite tabella con
particolari campi di collegamento tra loro.
Accedendo ai vari campi in maniera non sequenziale potrai usare
tranquillamente la tabella come una lista dinamica bidirezionale e quindi
come grafo.
Spero di non essere stato tropo prolisso
Ciao
FACE ONE

 prendere una strada con senso vietato), e via dicendo.
Ora che mi ci fai pensare a livello di ottimizzazione sarebbe fondamentale
avere a disposizione la velocità media di percorrenza di ogni tratto di
strada.... Il percorso più breve è inutile se lo percorri a 20Km/h :-)
Max

Grazie a tutti, se vi interessa vi dico come sto pensando di
risolverlo:
Faccio una tabella i cui record rappresentano dei TRATTI stradali e i
cui campi sono
- Codice della strada, tipo E45S (corsia sud) e E45S (stessa strada
corsia nord)
- Un ordinale, che rappresenta la posizione del tratto all'interno
della strada (per esempio il tratto Caianello-Capua potrebbe essere il
numero 17 della A1)
- Località di partenza, la città da cui parte l'arco
- Località d'arrivo, la città dove termina il tratto
- Lunghezza in Km del tratto
- Tempo tipico di percorrenza
...
per il momento mi fermo qui, perchè le altre informazioni esulano
dalla problematica che sto trattando...
Ora, per trovare una strada che colleghi DIRETTAMENTE due località
(loc_partnza e loc_arrivo), è sufficiente trovare due record che
abbiano lo stesso CODICE DELLA STRADA, e uno abbia Localirà di
partenza = loc_partnza e l'altro abbia Località di arrivo =
loc_arrivo...
non so se mi sono spiegato...
ora sto cercando di implementare questa cosa con Access (e se qualcuno
è così paziente)...
e sto cercando un metodo per cercare collegamenti con uno, due, enne
cambi di strada....
Ancora un grande ed ammirato grazie a chi mi ha dato una mano

 cambi di strada....
appunto... devi prevedere nelle tue tabelle qualcosa che indichi quali sono
i tratti di strada che ti permettono di cambiare "Codice strada"
Per esempio se da Bologna devi andare a Tabiano (paesino termale vicino a
Fidenza in provincia di Parma) devi uscire dalla A1 a Fidenza, e poi
prendere svariate statali per arrivarci.
Max


Innanzitutto ti ringrazio per l'attenzione... mi sentivo così solo
davanti a 'sto problema!!!
Per trovare un percorso che colleghi due località che non sono servite
dalla stessa strada: ne caso più semplice, un solo cambio di strada,
sarebbe sufficiente trovare una località di svincolo. Una località
cioè cui afferiscano le due strade che collegano le due località che
non sono collegate con una strada comune... ci sto lavorando... spero
di riuscire a postare un po' di sql per spiegarmi meglio.

problema di grafi pesati...
Un consiglio spassionato: a meno che tu non abbia mooooolto
tempo e non ti diano mooooolti soldi, lascia perdere access
e prova un software gis (tipo arcview, mappoint...)
--
Lorenzo Coronati
--
<<Ragazzi, sapete indicarmi una utility in 
internet che sia in grado di recuperare le 
password da un database access e da un system mdw?
intendevo, gratuita...>>
(Marco Tullio Bisoli, 27/04/2001)
--

 e qui mi sono fermato...
Come inizio mi sembra corretto.
Si tratta sostanzialmente di minimizzare la funzione di costo: se il costo è
il tempo, trovi il percorso più veloce, se è la distanza, quello più breve,
ecc.
Algoritmi classici in letteratura se ne trovano diversi, ad esempio Dijkstra
Shortest Path.
Lascia perdere il problema del commesso viaggiatore, o TSP, che è un'altra
cosa e non ti serve.
Ti dò solo qualche spunto, poi se vuoi approfondire qualche punto scrivi
pure.
Rappresentando il problema secondo lo schema "Stati e Operatori", da ogni
città (nodo) escono x strade (archi) che portano ad altre x città. Una
ricerca esaustiva (brute force) è impensabile oltre una certa dimensione del
grafo, a causa della complessità temporale esponenziale.
Potresti partire con una ricerca DFS (Depth First Search) su cui applichi il
Branch & Bound (taglia sottoalberi che sicuramente non contengono la
soluzione ottima). I pesi degli archi si sottintendono positivi.
Per migliorare le prestazioni aggiungi una tecnica euristica (ad esempio dai
un'occhiata all'algoritmo A*). Come euristica ammissibile h'(n) (vedrai che
ti serve nella funzione f(n) = g(n)+h'(n)) puoi usare la distanza in linea
d'aria (la normale distanza euclidea tra due punti di cui conosci le
coordinate, che memorizzerai nella tabella dei nodi).
Insomma... se la cosa ti interessa, scrivi che possiamo affrontare il
problema a poco alla volta...
--
Ciao, AntoGal
*************************************************
Gestione punti vendita (casse e pos NCR)
 
www.powerretail.it
-------------------------------------------------------------
per scaricare un gioco di DAMA ITALIANA
http://volftp.mondadori.com/italiani/galletta/
*************************************************