Newsgroup: it.comp.www.php
Titolo: Motore di ricerca

Mi piacerebbe realizzare un motore di ricerca per il trasporto pubblico 
della mia città inserendo le varie compagnie di trasporto.
Da dove posso iniziare? Per quanto riguarda i dati delle linee, orari e 
fermate son a buon punto ma ora devo realizzare gli script di ricerca.
Avevo pensato di "ispirarmi" al servizio di ATM di Milano o ATAC di Roma.
Qualcuno può aiutarmi?
Grazie. 

Da dove posso iniziare?
Comincerei dal definire cos'e' che farebbe questo "motore di ricerca".
Leonardo
-- 
While ordinarily valid that being widespread does not make a statement
true, I feel that the diffusion of anti-evolutionary beliefs does pose
a strong argument for Darwin having been, indeed, sorely mistaken.

>della mia cittą inserendo le varie compagnie di trasporto.


funzionamento.
Si' e no...
Per esempio, nel caso che tu volessi implementare qualcosa del genere
"Voglio andare da qui a qui", dovresti creare qualcosa di simile all'
algoritmo di Dijkstra (modificato per tener conto delle coincidenze -
questo se vuoi prevedere di cambiare mezzo in corsa).


>Pensavo indicando dei sistemi già esistenti si potesse ipotizzare il suo


 riscriverlo per il funzionamento in php.
http://en.giswiki.net/wiki/Dijkstra's_algorithm#PHP
http://www.cs.sunysb.edu/~skiena/combinatorica/animations/dijkstra.html
Ciao, Maverick
-- 
ĢChe non siete pių liberi di non avere una casa con letto per dormire.
 Lavorate voi - schiavi dei soldi - che non sentite la puzza della
 schiavitų!ģ (a Mario di Monte Mario, Roma) # 
http://libre.netsons.org/

calcolare i percorsi con eventuali cambi.
Eh. L'algoritmo di base e' molto semplice.
Innanzitutto identifichi tutti i tuoi punti nello spazio-tempo, ovvero
per esempio:
AUTOBUS 15
	Via di Scantignano	08:00
	Piazza Rontivalli	08:15
	Viale Cioppa		08:19
	Via Riparella		08:22
	Viale Cioppa		08:29 (fa un percorso a quadrifoglio)
	Via Pargonza		08:34
 
AUTOBUS 39
	Largo Armida		08:16
	Piazza Rontivalli	08:21
	...
	Via Poncassi		08:38
In questo caso ogni coppia (Luogo, Tempo) costituisce un "nodo". Oltre
ai nodi, hai anche degli archi, cosi' concepiti:
- Per ogni "percorso" (es. Autobus 15), gli archi vanno da nodo a nodo
e hanno un costo pari alla differenza dei tempi.
- Dati due nodi con uguale Spazio (es. Piazza Rontivalli), se il tempo
e' negativo non c'e' proprio l'arco, e altrimenti il costo e' di nuovo
la differenza dei tempi.
Quindi li' sopra hai sei nodi, e nove archi: due archi del bus 39 piu'
cinque del bus 15; piu' un arco interno Cioppa-Cioppa del bus 15, piu'
uno che collega l'autobus 15 al 39 in piazza Rontivalli, ed e' lungo 6
minuti.
Quindi hai qualcosa come:
	$luoghi	= array(
		1	=> 'Via di Scantignano',
		2	=> 'Piazza Rontivalli',
		...
	);
	$mezzi	= array(
		0	=> 'Autobus 15',
		1	=> 'Autobus 39',
		...
	);
	$percorsi = array(
		0 => array(
			'1,08:00', '2,08:15', '3,08:19', ...
			),
		1 => ...
Questi sono i tuoi dati iniziali che gia' hai. Da questi devi popolare
gli array $nodi e $archi:
	$nodi = array(
		0 => '1,08:00',
		1 => '2,08:15',
		...
	);
	$archi	= array(
		0 => '0,1,15,0',/* Da nodo 0 a nodo 1, 15 minuti con il
mezzo 0*/
Da qui puoi proseguire pari pari con l'algoritmo di Wikipedia. Pero' va
fatta una osservazione: io ho utilizzato, in $archi, una quadrupla, con
nodo di partenza, di arrivo, costo e mezzo usato.
Avrei potuto anche scrivere:
		'0,1'	=> '15,0',
ossia: per andare dal nodo 0 al nodo 1, prendo il mezzo #0 - e mi costa
15 minuti. Messa cosi' la fase di ricerca successiva stile Wikipedia e'
molto piu' rapida. Pero' puo' succedere che due autobus seguano un solo
percorso, magari in tempi diversi, sicche' io ho:
		'0,1'	=> '15,0'
e anche
		'0,1'	=> '14,7' (uso un ipotetico autobus 93).
Nell'array $archi ci posso mettere un solo nodo '0,1' - e quindi, viene
spontaneo dire di metterci quello piu' breve. Con gli autobus non ti fa
cosi', pero', perche' non e' pensabile di scendere dal 15 in piazza per
salire sul 39, fare una fermata, riscendere e risalire sul 15.
Quindi una alternativa e' modificare l'algoritmo di Dijkstra per tenere
conto del "mezzo attuale", ed assegnare una "penalita'" ad ogni cambio.
Questo avviene nel passo "assegnazione etichetta provvisoria" del ciclo
di Wikipedia. Anziche' fare " f(i)=f(j)+p(j,i) ", devi imporre qualcosa
di questo tipo:
	$f[$i] = $f[$j] + Costo($j, $i);
dove "Costo" valutera' su quale mezzo ti trovi quando sei in j, e quale
mezzo puoi usare per quel particolare arco j-i: se e' diverso, oltre al
costo dell'arco ritorna anche la penalita'.
Va detto che occasionalmente in questi casi, in teoria, l'algoritmo non
converge. Ma con i pesi di un grafo di trasporti reale, in pratica cio'
non si verifica mai.
In alternativa (e' leggermente piu' stabile -- e lento) puoi provare ad
usare l'algoritmo di Bellman-Ford. Qui c'e' anche il codice in C, molto
simile al PHP:
http://en.wikipedia.org/wiki/Bellman-Ford_algorithm


 ha scritto nel messaggio 
news:mgksh31bvv4pve2cc...@4ax.com...


> '1,08:00', '2,08:15', '3,08:19', ...
Piu' di cosi' ti posso solo scrivere io il codice :-)
Incidentalmente: una volta che sai che l'algoritmo si chiama "Dijkstra" e
che lo vuoi fare in PHP... hai abbastanza dati per l'invocazione satanica
 
http://alnitak.ctt.it/lserni/vm18.avi
che ti porta ratto come il fulmine qui:
 
http://en.giswiki.net/wiki/Dijkstra's_algorithm#PHP



Magari tutto no ma una mano... :-P 





Scusa - non per tirarmela, farla cadere dall'alto o cose cosi': pero':
Qui c'e' il codice gia' implementato, con esempi.
 
http://en.giswiki.net/wiki/Dijkstra's_algorithm#PHP
Nel mio post ti ho detto come si possono archiviare dati del tipo che
dici tu.
...come minimo *PROVA* e poi poni delle domande precise (che so, "con
questo array in ingresso mi ritorna cosi' invece che cosa'"). E se no
in che modo di preciso, uno puo' "darti una mano"? Scrivendoti i nomi
delle funzioni? :-)
Copiati il codice di giswiki e fallo funzionare. Poi estendilo ad una
classe di oggetti piu' complessi, con i nodi al posto delle fermate e
l'intertempo fra le fermate come peso di ogni arco. Lo estendi ancora
usando dei pesi multipli (se puoi andare da A a B usando il bus 15 od
il bus 39, e l'arco AB ha un peso X per il bus 15 ed un peso Y per il
bus 39, scegli il peso minore). Poi pesi variabili (nell'esempio, hai
una variabile globale che dice su quale bus sei, e se e' il 15, oltre
a Y per il bus 39 calcoli Y+K con K = costo del cambio di autobus (ad
esempio meta' del tempo di interarrivo del nuovo autobus)).
E ripeto, domande precise: 
http://alnitak.ctt.it/lserni/smartq.php


 ha scritto nel messaggio 
news:n2k4i3h09f6o4qtdu...@4ax.com...


 Esiste qualcosa di già pronto da personalizzare?
Certo, ciò che ti ha indicato Leonardo.
Più di quel che ti ha detto, da questo ng sicuramente non otterrai, se
non mostri un minimo di collaborazione. Altrimenti chiedi su
it.comp.www.php.pappa.pronta, forse lì troverai il lavoro già fatto.
Ciao, Maverick
-- 
«Che non siete più liberi di non avere una casa con letto per dormire.
 Lavorate voi - schiavi dei soldi - che non sentite la puzza della
 schiavitù!» (a Mario di Monte Mario, Roma) # 
http://libre.netsons.org/