Newsgroup: it.scienza.informatica
Titolo: Alagoritmo (A*)

Sto finendo il lavoro di approfondimento da presentare al nuovo esame di
maturita' e ho preso in esame un algoritmo che ottimizzi il percorso di
ricerca ottimale di un labirinto. Cerco quindo qualche notizia
sull'algoritmo (A*), i vari motori di ricerca da google ad altavista non mi
hanno dato alcuna indicazione utile, lancio allora questo "help".
Grazie in anticipo per ogni suggerimento.
Alef
------------
replay to 
nt...@tin.it

...

che roba è 'sto algoritmo A* ????????
ti dico solo che mi sto laureando in informatica e non ne ho mai sentito
parlare.
Invece ti propongo un'altra soluzione:
Un labirinto può essere rappresentato mediante un grafo non direzionato, con
un vertice in ogni incrocio, e penso che il buon vecchio algoritmo di
Dijkstra (percoso minimo da un nodo sorgente a tutti gli altri) potrebbe
aiutarti molto in questo, che so, assegnando peso unitario ad ogni arco
magari, e fissando due vertici che costituiranno l'ingresso e l'uscita dal
labirinto.
Un mio collega in passato ha tentato qualcosa del genere e gli funzionava
benissimo.
In bocca al lupo per gli esami.
The young bad Werther
f...@ctonline.it
fabi...@geocities.com
http://www.geocities.com/Paris/Jardin/6726/
Un mio collega ha fatto qualcosa del genere in passato e gli funzionava
benissimo

>PGP public key avaiable<<
fingerprint: 14AA 1D7A 1653 E132 47CE  334C C9D3 6A97 208B A915

 
Dico la mia, da totale inesperto. :)
Secondo me, se tratti labirinti generici, c'e' poco da fare: forza bruta,
si provano tutte le strade, e si sceglie poi la piu' breve.
Questo perche' si capisce bene che potrebbe avere 1 sola soluzione, o tante...
Se una potrebbe essere la piu' lunga... se tante potrebbero essercene di pari,
insomma: troppi casi.
Piu' interessante potrebbe essere invece qualcosa sulla ricerca del
percorso migliore in qualche "ambiente" strano...
Ad esempio, ti rimando al thread che si e' sviluppato su
	it.comp.lang.c
Subject: Re: Problema degli esagoni
bye!
-- 
Emanuele Cesena                 
http://www.penguinpowered.com/~ecesena
ece...@penguinpowered.com
                 Attenti all'antispam NOSPAM
"In un qualsiasi insieme di dati, la cifra cosi' evidentemente corretta da
non richiedere un controllo e' l'errore", terza legge di Finagle

Nella terminologia informatica cosa significano i termini:
background
foreground
dead-lock
plug & play
Vi ringrazio anticipatamente del vostro aiuto.
Rocco

hanno dato alcuna indicazione utile, lancio allora questo "help".
Rispondo con ritardo, ma spero di essere ancora in tempo...
A* e` un algoritmo di ricerca euristica che sotto opportune condizioni
trova sempre la soluzione (se esiste) di costo minimo.
La caratteristica di tale algoritmo e` la suddivisione della funzione
di valutazione in due componenti:
F(x) = g(x) + h(x)
dove g(x) e` il costo necessario a raggiungere il nodo x a partire
da quello iniziale, mentre h(x) e` la stima del costo necessario a
raggiungere la soluzione a partire da x.
L'algoritmo procede cosi` (per semplicita` considero il caso della
visita di un albero)
Sia L una lista ordinata sulla base del valore di F(x), inizialmente
tale lista conterra` solo la radice (il nodo iniziale) dell'albero
di ricerca (per il quale g(x) = 0) cui si associano i valori di
g e h corrispondenti.
a) Si estrae il nodo (N) da L per il quale F(x) e` minima
b) per ogni successore Y di N
      b.0) Se Y e` una soluzione, si termina con successo altrimenti:
      b.1) si calcolano i valori g(y) e h(y)
      b.2) si memorizza Y in L assieme ai valori precedentemente calcolati
c) Se L non vuota ritorna al passo a)
d) termina con fallimento
Sia H(x) il costo reale per giungere alla soluzione
Sotto la condizione h(x) <= H(x), A* trova la soluzione di costo
minimo.
Nel caso di visita di un grafo (quale sembra essere il tuo), bisogna
considerare la possibilita` di raggiungere lo stesso nodo da cammini
diversi e con costi diversi e la faccenda si complica un poco ma non
eccessivamente.
Comunque per altre informazioni ti rimando a:
E. Rich, K. Knight
"Intelligenza artificiale", 2a edizione
McGraw-Hill
Paolo
-----------------------------------------------------------------
  Paolo Marotta
  Computer Science, University of Pisa
  home:   
http://www.cli.di.unipi.it/~marotta
-----------------------------------------------------------------

Nella terminologia informatica cosa significano i termini:
background  (sfondo)
foreground  (primo piano)
plug & play (collega e vai, riferito al riconoscimento automatico da
parte del sistema di eventuali periferiche aggiunte alla macchina e di
utilizzo delle stesse in modo immediato) 

plug & play
ma volete imparare tutto insieme ?
DataBase, SQL, Pascal, terminologia.....e poi che altro ancora ? :-)))
Mi sbaglio o mi avete scritto anche in privato oltre ad una 10 di newsgroup
? (se non di più)
Ehi........non è un rimprovero però vi conviene trattare un argomento alla
volta, magari dopo averci lavorato un po' sopra, altrimenti da un orecchio
entra e dall' altro esce !!
Riguardo i termini, traducete dall' inglese all' italiano e capite cosa
vogliono dire.
Ad esempio "background"  può indicare il colore di sfondo in un' area di
lavoro
dell' applicazione, foreground il colore del testo sullo sfondo ecc.....
Per quanto riguarda Plug & Play, è un discorso un po' lungo !!
Riguarda le periferiche del PC, o per meglio dire la tecnologia di quest'
ultime.
Acquistate delle riviste d' informatica e troverete quello che vi interessa
!!
Saluti !!
Antonio Tarolla

benissimo.
Non credo sia praticabile, innanzi tutto perche` dovresti costruirti il grafo e
questo implica l'esplorazione del labirinto, ma esplorato il labirinto hai
gia` praticamente risolto il problema.
In generale poi l'esplorazione di un grafo se non erro mi pare sia O(nm),
e bisogna considerare che relativamente al problema, il numero
di nodi cresce esponenzialmente (anche se alcune strade riportano e
quindi la valutazione e` piu` difficile).


Rocco
ByezZz


 di una mano).
Ciao Paolo, sarei molto interessato a conoscere e ad approfondire
gli algoritmi di cui parli. Puoi darmi qualche riferimento?
Grazie in anticipo,
                       Antonio

-----------------------------------------------------------------
costruire il grafo ????
ma il labirinto E' il grafo!!!!!!! E' già bello e costruito!!!! poi, scusa
un attimo:
1) l'algoritmo di Dijkstra è logaritmico polinomiale
2) dubito che debba provare l'algoritmo con un numero di nodi
allucinante!!!! poi certo, se osserviamo la cosa in grande scala, allora
quasi tutto diventa di una certa complessità, chi meno (P) chi di più (NP).


gli algoritmi di cui parli. Puoi darmi qualche riferimento?
In rete non saprei, come testi i grandi classici sono:
Matt Ginsberg
"Essential of artificial intelligence"
Morgan Kaufmann Publishers
Nils J. Nilsson
"Principles of artificial intelligence"
Springer-Verlag
E. Rich, K. Knight
"Intelligenza artificiale" 2a edizione
McGraw Hill
In particolare ti consiglio il primo ed il terzo... il secondo e` orientato
principalmente ai sistemi basati su regole ("sistemi esperti"), cmq in tutti
e 3 la ricerca euristica e` solo una parte dell'argomento.
Paolo
P.s.
   Buona lettura!


 Rocco
--
--------------------------------------------------------------
Fabrizio Sebastiani, 
http://userspace.ats.it/free/fsebasti
--------------------------------------------------------------

quasi tutto diventa di una certa complessità, chi meno (P) chi di più (NP).
questa non l'ho capita, qualcosa mi dice che stiamo considerando il problema
da punti di vista molto diversi... Dal mio punto di vista il labirinto
non e` noto all'esploratore, e` come se tu fossi piazzato all'ingresso
e ti chiedessero di trovare l'uscita nel minor tempo possibile, magari
disponendo di qualche indizio da utilizzare nelle scelte.
A questo punto chiaramente ti troveresti a dover dominare il numero
complessivo di scelte che per un certo tempo cresce esponenzialmente
Avendo la mappa del labirinto ti troveresti effettivamente a dover
semplicemente visitare un grafo pesato e trovare l'uscita
sarebbe molto semplice!!!!
Non mi pare che il problema fosse questo.
Paolo


 McGraw Hill
Grazie infinite!
Ti faro' sapere com'e' andata la lettura...  ;)
Antonio