Home  Rudi algoritmi per RUDI  Home

(Problema di Ottobre 2010)

Bisogna determinare quanta strada farà il robottino RUDI per raggiungere un obiettivo a 100 metri in un numero N di segmenti utilizzando un algoritmo efficiente (nel senso che la distanza in linea d'aria di RUDI dall'obiettivo diminiusca continuamente) ma scelto in modo tale da massimizzare il percorso.
Detta L(N) la lunghezza di tale percorso in metri, sarà L(N)=sqrt(N)*100

Più in generale, detta l la distanza di RUDI dall'obiettivo, sarà L(N)=sqrt(N)*l

triangolo percorso
Per la dimostrazione si faccia riferimento alla figura a fianco dove è indicato con A l'obiettivo e con BC il primo segmento del percorso.
Si può notare innanzitutto che deve essere 0<=beta<=pigreco/2 e pigreco/2<=gamma<pigreco altrimenti lungo il segmento BC il robottino si allontanerebbe dall'obiettivo. Si può anche vedere che il percorso è massimo quando gamma=pigreco/2 .

Dimostrerò la validità della risoluzione per induziione su N.
La relazione è banalmente valida per N=1 infatti L(1)=l.
Bisogna dimostrare che 0<=beta<=pigreco/2
In base alla figura abbiamo
equazioni
Cerchiamo il massimo della funzione al variare di α.
equazioni
Dalla dimostrazione si ricava anche il valore dell’angolo alfa(N)=sqrt(1/N)che permette di costruire l’effettivo percorso fatto da RUDI.
A questo proposito si può osservare che ogni segmento, tranne l’ultimo, può essere scelto con un angolo preso in senso orario o antiorario per cui in realtà saranno possibili 2N-1 diversi percorsi tra i quali la spirale destrorsa e sinistrorsa e l’avvicinamento a zig-zag.
Se si considera un sistema di assi coordinati con l'obiettivo sull’origine, dette (x1,y1) le coordinate della posizione del robottino, e (x2,y2) le nuove coordinate (quando si devono effettuare N passi) sarà
equazioni oppure equazioni
Qui sotto è possibile visualizzare diversi percorsi.
Numero di segmenti
Distanza dall'obiettivo px
Modalità di avvicinamento