Newsgroup: it.comp.ia
Titolo: Progetto Topo: Proposta di Algoritmo

Provo a proporre un algoritmo (scusatemi per il linguaggio e il metodo
"rozzo" ma sono a digiuno di IA):
- Il labirinto si considera come una scacchiera (perché complicarsi la
vita?), il movimento minimo del topo è di una casella, alcune caselle
saranno "bloccate", e saranno gli ostacoli o le pareti del labirinto.
- Il topo si muove in una direzione a caso, e prosegue nella direzione
scelta finché non incontra un'ostacolo, ma non ritorna MAI nella direzione
opposta.
- In caso debba tornare nella direzione opposta, considera la casella su cui
si trova bloccata", e non ci tornerà piu; in questo modo il topo eviterà di
tornare in un vicolo cieco più di una volta.
- Quando il topo ricomincia daccapo, difficilmente seguirà lo stesso
percorso, ma ricorderà le caselle che aveva bloccato (magari non tutte..)
PROBLEMI:
Se il topo si muove nella stessa direzione finchè non trova un ostacolo, può
darsi che in alcuni casi cominci a girare in tondo. Forse dovrebbe scegliere
la direzione ad ogni passo, ma anche cosi, se il topo si trova in una stanza
"larga" ci metterà una vita a uscire..
PROSPETTIVE:
E se ci mettessi anche un gatto? O dessi al topo l'olfatto? O mi ricoverassi
in un manicomio?
Se qualcuno vuol darmi qualche consiglio per affinare l'algoritmo, o
tradurlo in un linguaggio più consono al NG... (es. La simulazione biologica
memorizza il cambio di direzione a ogni nodo non pari ed esegue il
backtracking vettoriale ogni volta che deve fare la pipì ;-) ...comincio a
lavorare. Chi volesse il codice della classe Topo non deve fare altro che
chiedermelo, una volta che l'avro finito.
Curiosità: ho trovato un collegamento morto a un certo programma Mice (...)
qualcuno ne sa qualcosa?

Ciao
Immagino tu sappia che per uscire da un labirinto basta seguire una parete
fino all'uscita... senza memoria e senza tanta intelligenza :-)
Comunque è un buon esercizio di IA
Ciao


Non ho parole. Mi hai distrutto. Sei sicuro?

]

> fino all'uscita... senza memoria e senza tanta intelligenza :-)
Non è proprio esatto, perché potresti trovarti a seguire le pareti di
un muro isolato all'interno del labirinto e girare all'infinito se il
muro è abbastanza grande e non ti accorgi di ripassarlo più volte.
Es.:
------------
|          |
| | -----  |
|-- |   |   =>  USCITA
|   | | |  |
|     |    |
------------
prova a seguire il muro interno di questo labirinto (un labirinto
potrebbe essere molto grande e averne a decine di muri isolati dalle
pareti esterne)
Servono algoritmi un po' piu' complessi (visita in profondità con
memoria delle zone già visitate); insomma, funziona bene il sistema
delle briciole di pane.
Ciao, Max.

muro č abbastanza grande e non ti accorgi di ripassarlo piů volte.
Se nel labirinto ci _entri_ ci esci di sicuro, se invece parti da una
qualsiasi parte interne effettivamente c'e' questo problema.


qualsiasi parte interne effettivamente c'e' questo problema.
Se non ricordo male, la tecnica che proponete funziona per un labirinto
connesso; se il labirinto non e' connesso, c'e' una variante un po' piu'
complessa, che ora non ricordo perfettamente, ma recita piu' o meno cosi':
durante il cammino, si segna una parete del corridoio (sempre la stessa:
destra o sinistra!); quando si giunge ad un incrocio, si prende sempre la
direzione piu' a destra, a meno che la parete non sia gia' stata segnata due
volte. Questa regoletta (ammesso che l'abbia citata correttamente)
*garantisce* l'uscita; ovviamente non garantisce il percorso piu' breve.
Ciao,
Gianfranco

*garantisce* l'uscita; ovviamente non garantisce il percorso piu' breve.
Questo algoritmo che tu dici è una caso particolare dell'algoritmo con
visita di profondità a memoria di stati cui prima facevo riferimento:
in questo caso la visita in profondità parte ad analizzare la via più
a destra tra le possibili.
Ciao, Max.