Newsgroup: it.scienza.informatica
Titolo: problema algoritmo

Devo realizzare una cosa simile:
Ho n citta', ad ogni citta' e' associata la citta' piu' vicina. Partendo da
una citta' qualsiasi devo ottenere tutte le n citta' in ordine di vicinanza
con la citta' prescelta.
Es.
| Citta'        | Citta' piu' vicina |
| Roma       | Frosinone          |
| Frosinone | Cassino             |
| Cassino    | Caserta             |
| Caserta    | Cassino             |
Scelgo Frosinone, devo avere:
Cassino, Caserta, Roma
Scelgo Cassino, devo avere:
Caserta, Frosinone, Roma
Ovviamente nell'implementazione posso aggiungere parametri a mio piacimento
per facilitare le operazioni, quindi oltre a "citta' piu' vicina" ci posso
mettere anche altre cose.... Sto lavorando in PHP + MySQL.
Cosa mi suggerite?
Grazie

Grazie
La tua struttura dati produce una foresta di uno o piu' quasi-alberi.
Per quasi-albero intendo un albero con un arco aggiuntivo che, per
forza di cose, chiude un ciclo.
Quindi il tutto si riduce ad una visita dell'albero che contiene la
citta' di partenza, a partire dalla citta' stessa come radice. Un arco
puo' essere seguito in entrambi i versi.
Ciao. Federico.

~\/~ "Valerio" == Valerio  <k...@ko.ko> writes:
Valerio> Devo realizzare una cosa simile:
Valerio> Ho n citta',
x backtracking msg: "avere" non sembra un verbo appropriato
Valerio> ad ogni citta' e' associata la citta' piu' vicina.
Valerio> Partendo da una citta' qualsiasi
Valerio> devo ottenere tutte le
Valerio> n citta'
Valerio> in ordine di vicinanza
Valerio> con la citta' prescelta.
se le "hai" non le devi ottenere,
allora devi solo ordinarle.
Valerio> Es.
Valerio> | Citta' | Citta' piu' vicina |
Valerio> | Roma | Frosinone |
Valerio> | Frosinone | Cassino |
Valerio> | Cassino | Caserta |
Valerio> | Caserta | Cassino |
Valerio> Scelgo Frosinone, devo avere: Cassino, Caserta, Roma
Con il criterio che hai scelto non puoi sapere in che posizione ordinata
mettere Caserta e Roma.
Io non capisco come certa gente ragioni ortogonalmente alla logica,
come si fa a pensare di mettere in un database una
riduzione di informazioni  come il risultato della ricerca del minimo..,
cioe` perche` anziche` memorizzare il risultato della ricerca in
logica locale della piu` vicina, non si sono mantenute le misure
delle distanze...
Per erperienza so che molta gente, anche dopo aver studiato
(meccanicamente) la teoria (non penso sia il caso di Valerio),
sceglie le strutture dati secondo il principio "la prima che capita",
poi quando va bene presenta problemi irrisolti senza accorgersi
che sono irrisolvibili, o quando va male... sono risolvibili
in modo molto piu` complicato del necessario.
Partiamo dal fatto che intuitivamente la distanza e` una proprieta`
topologica applicata in questo caso a 2 (o 3) dimensioni.
L'ordinamento e` sempre appiattito su una dimensione, basarlo poi
su proprieta` estreme ("piu` vicino") dovrebbe insinuare il sospetto
che il problema degeneri.
chiamerei Roma R, Frosinone F, Cassino C, Caserta D (solitamente
gli esemi si cerca di farli con lettere iniziali distinte...,
abbrevio solo con ``d'' la funzione distanza)
* la prima proprieta` [la citta` piu` vicina a Roma(R) e` Frosinone(F)]
equivale (nell'insieme delle n-citta` = 4-citta` d'esempio) a queste
disequazioni:
	d(Roma,Frosinone) < d(Roma,Cassino)
	d(Roma,Frosinone) < d(Roma,Caserta)
* la seconda proprieta` [la citta` piu` vicina a Frosinone(F) e` Cassino(C)]
	d(Frosinone,Cassino) < d(Frosinone,Caserta)
	d(Frosinone,Cassino) < d(Frosinone,Roma)
* la terza [la citta` piu` vicina a Cassino(C) e` Caserta(D)]
	d(Caserta,Cassino) < d(Caserta,Frosinone)
	d(Caserta,Cassino) < d(Caserta,Roma)
* la quarta [la citta` piu` vicina a Caserta(D) e` Cassino(C)]
	d(Caserta,Cassino) < d(Cassino,Frosinone)
	d(Caserta,Cassino) < d(Cassino,Roma)
raccogliendo quelle che potrebbero interessare l'ordinamento con
prescelta Frosinone:
d(Cassino,Caserta) < d(Frosinone,Cassino) < d(Frosinone,Roma)
                     d(Frosinone,Cassino) < d(Frosinone,Caserta)
nulla si puo` dire sulla relazione ordinale tra le distanze
	d(Frosinone,Roma)  d(Frosinone,Caserta)
Qualcos'altro possiamo dire per le proprieta` della norma (distanza),
mi pare si chiami proprieta` triangolare, ma e` ovvia:
d(Frosinone,Caserta)+d(Caserta,Cassino) >= d(Frosinone,Cassino)
     d(Roma,Caserta)+d(Caserta,Cassino) >= d(Roma,Cassino)
PS: Anzi non serve neppure scomodare il fatto che la distanza e` su 2
    o tre dimensioni, questi esempi addirittura lineari in rispetto
    alla tabella proposta, "prescegliendo" F ha due soluzioni diverse:
topologia:      R          F        C      D
->  F,C,R,D
topologia:      R          F    C  D
->  F,C,D,R
Valerio> Scelgo Cassino, devo avere: Caserta, Frosinone, Roma
Valerio> Ovviamente nell'implementazione
Valerio> posso1 aggiungere parametri
Valerio> a mio piacimento
Valerio> per facilitare le operazioni,
Valerio> quindi oltre a "citta' piu' vicina"
Valerio> ci posso mettere anche altre cose....
Ecco un esempio di cosa intendevo per "la prima struttura dati che capita",
anche se le righe sopra sono anche peggio di quello che pensavo..., il
fatto poi che ne parli come se si trattasse di "implementazione",
e` molto significativo, ma lasciamo perdere.
Valerio> Sto lavorando in PHP + MySQL.
Se lavori in PHP e MySQL  annàmo bbéne...
Valerio> Cosa mi suggerite?
Non so poi cosa aveva in mente tal Federico/mfede quando ti ha scritto
"La tua struttura dati produce una foresta di uno o piu' quasi-alberi"
inheritance of orthogonal logic (e` un mio neologismo)
Valerio> Grazie
Saluti,
MARco
-- 
http://mar.i.am/~u16566.20072/it.scienza.informatica/ortogonallogic,it
x(t),y(t) = th(3t-34.5)*e^[-(3t-34.5)^2]/2-4.3+e^(-1.8/t^2)/(.8*atg(t-
3)+2)(t-1.8)-.3th(5t-42.5),(1.4e^[-(3t-34.5)^2]+1-sgn[|t-8.5|-.5]*1.5*
|sin(pi*t)|^[2e^(-(t-11.5)^2)+.5+e^(-(.6t-3.3)^2)])/(.5+t)+1  ; 0<t<14

MARco
Ciao. Federico.

 MARco
Saluti anche a te,
Valerio