.dsy:it. (http://www.dsy.it/forum/)
- Algoritmi e strutture dati (http://www.dsy.it/forum/forumdisplay.php?forumid=207)
-- [Algoritmi] Progetto "RICHIAMI" (http://www.dsy.it/forum/showthread.php?threadid=17192)

Originally posted by mattcobain
110 e 111 e 1 non possono perché facendo i percorsi alternativi detti da te (salire di un tot, andare a sx e riscendere, oppure aggirare tutto l'ostacolo) raggiungerebbero la sorgente del segnale facendo un percorso più lungo di D (che è la distanza minima, sgombra da ostacoli)
possono raggiungere il segnale solo quegli automi che lo raggiungono con un percorso libero (cioè senza passare sopra gli ostacoli) della stessa lunghezza di D (cioè la distanza sgombra da ostacoli)...e fra questi solo quelli che hanno D più piccola....
infatti, sempre dall'esempio, possono raggiungere il segnale 10 con D=8, 11 con D=8, 100 con D=9 e 101 con D=8....fra questi, quelli con D piu piccola sono 10, 11, 101 (la loro D=8, nessun'altro automa ha una D piu bassa) e quindi ecco spiegato il tuo dubbio....spero di essere stato chiaro

__________________
"Why, Sir, you find no man at all intellectual who is willing to leave London.
No, Sir, when a man is tired of London, he is tired of life; for there is in London all that life can afford."
(DR SAMUEL JOHNSON 1777)

MSN andrea.poretti(at)hotmail.it

si, ma x il fatto che ho postato prima che mi dite??
com è possibile che ad esempio l automa 11 arrivi alla sorgente se un passo unitario fa incrementare la y???l 11 la raggiinge decrementandolo e non viceversa!

Originally posted by p2p
si, ma x il fatto che ho postato prima che mi dite??
com è possibile che ad esempio l automa 11 arrivi alla sorgente se un passo unitario fa incrementare la y???l 11 la raggiinge decrementandolo e non viceversa!

a questo punto credo che la regola che da lui sia generale..avrebbe potuto mettere X0<X<X0 +/- 1....
puo' essere no??

__________________
"Why, Sir, you find no man at all intellectual who is willing to leave London.
No, Sir, when a man is tired of London, he is tired of life; for there is in London all that life can afford."
(DR SAMUEL JOHNSON 1777)

MSN andrea.poretti(at)hotmail.it

Originally posted by mattcobain
il fatto che il passo unitaio faccia incrementare la y non significa che la y si incrementa è se ne va oltre l'automa 11....puoi vedere il percorso come se parte dalla sorgente, vedi che cmq il percorso alla fine unisce in ogni caso automa e sorgente, considerando solo passi che vanno verso l'alto
cmq, in definitiva, per come il prof ha descritto i passi unitari, non vedo la limitazione che ogni passo deve seguire l'altro in senso incrementale....puoi anche tornare indietro facendo passi di uno e inserendo un altro passo 2 posizioni in negativo piu in la...insomma ,non riesco a spiegartelo però il fatto che x0 e y0 siano interi a scelta non ti limita a fare solo passi o verso l'alto o verso destra....puoi benissimo vederli anche verso il basso e verso sinistra, affiancando i singoli passi nel modo giusto....
che casino ho scritto!!!

vediamo, magari mi spiego meglio
se da un automa non puoi raggiungere la sorgente perché si trova al di sotto o alla sinistra dell'automa stesso (e quindi dovresti muoverti per decrementi secondo il tuo ragionamento) allora in questo caso vedi il percorso come se parta dalla sorgente....
cmq ripeto, non è scritto da nessuna parte che l'automa si muove solo in positivo verso l'alto e verso destra....
se devi scendere vedila come una sequenza di passi, si incrementali per definizione, ma uno successivo all'altro partendo di volta in volta da una x0 (o y0 a seconda del caso) negativa di 2 volte rispetto la precedente....ok, ho fatto ancora casino, non riesco a spiegartelo!!!!

Originally posted by mattcobain
vediamo, magari mi spiego meglio
se da un automa non puoi raggiungere la sorgente perché si trova al di sotto o alla sinistra dell'automa stesso (e quindi dovresti muoverti per decrementi secondo il tuo ragionamento) allora in questo caso vedi il percorso come se parta dalla sorgente....
cmq ripeto, non è scritto da nessuna parte che l'automa si muove solo in positivo verso l'alto e verso destra....
se devi scendere vedila come una sequenza di passi, si incrementali per definizione, ma uno successivo all'altro partendo di volta in volta da una x0 (o y0 a seconda del caso) negativa di 2 volte rispetto la precedente....ok, ho fatto ancora casino, non riesco a spiegartelo!!!!

__________________
"Why, Sir, you find no man at all intellectual who is willing to leave London.
No, Sir, when a man is tired of London, he is tired of life; for there is in London all that life can afford."
(DR SAMUEL JOHNSON 1777)

MSN andrea.poretti(at)hotmail.it

Originally posted by Skilotto83
esatto..incrementare una posizione nn è per forza in positivo...
anche da -2 a -3 incrementi di uno..ma in negativo..
kapito??

forse ora ce la faccio....
consideriamo il percorso che collega "11" alla sorgente
il percorso è formato solo da passi unitari verticali...la sequenza potrebbe essere questa:
ricordando che un P.U.V è della forma y0 <= Y <= y0 + 1 con y0 scelto fra i numeri interi...la sequenza di passi che da "11" da arrivare alla sorgente è:
P1 : 10 <= Y <= 11 (quindi y0=10)
P2 : 9 <= Y <= 10 (quindi y0=9)
P3 : 8 <= Y <= 9 (quindi y0=8)
P4 : 7 <= Y <= 8 (quindi y0=7)
...
...
...
P8 : 3 <= Y <= 4 (quindi y0=3)

i passi infatti sono 8 in tutto...e ogni passo ha solo un punto in comune con il successivo (come richiesto da progetto)....
ora spero di essermi spiegato....vedi che il percorso si forma alla fine!!!
il prof ha dato quella definizione "matematica" solo per rappresentare un passo, ma non ha detto che l'automa si muove in quel modo!!! l'automa si muove poi seguendo il percorso finale.....

Originally posted by mattcobain
forse ora ce la faccio....
consideriamo il percorso che collega "11" alla sorgente
il percorso è formato solo da passi unitari verticali...la sequenza potrebbe essere questa:
ricordando che un P.U.V è della forma y0 <= Y <= y0 + 1 con y0 scelto fra i numeri interi...la sequenza di passi che da "11" da arrivare alla sorgente è:
P1 : 10 <= Y <= 11 (quindi y0=10)
P2 : 9 <= Y <= 10 (quindi y0=9)
P3 : 8 <= Y <= 9 (quindi y0=8)
P4 : 7 <= Y <= 8 (quindi y0=7)
...
...
...
P8 : 3 <= Y <= 4 (quindi y0=3)

i passi infatti sono 8 in tutto...e ogni passo ha solo un punto in comune con il successivo (come richiesto da progetto)....
ora spero di essermi spiegato....vedi che il percorso si forma alla fine!!!
il prof ha dato quella definizione "matematica" solo per rappresentare un passo, ma non ha detto che l'automa si muove in quel modo!!! l'automa si muove poi seguendo il percorso finale.....

woooh, ce l'abbiamo fatta!
bella, ora però stacco, simpson e poi dinuovo al lavoro!!!

Dall'esempio del prof. si deduce che sono ammissibili anche i movimenti nel senso negativo delle ascisse e delle ordinate, anche se secondo me al riguardo la spiegazione del prof. lascia molto discutere.

Forse avete già risolto il problema del cammino minimo tra sorgente ed automa, ma volevo comunque sottoporvi la mia idea:
1. si costruisce un grafo fatto da tutti e soli gli spostamenti ammissibili tra sorgente e automa, in pratica, solo quelli inscritti nel rettangolo che ha per vertici la Sorg. e l'Aut. e senza i punti occupati da eventuali ostacoli.
2. si visita ricorsivamente il grafo alla ricerca di un cammino libero.
3. la condizione d'uscita è: puntatore figlio SX e DX = Null e distanza = Distanza minima.
4. Per la tortuosità si potrebbe pensare ad un ipotesi greedy per la quale, se si arriva ad un nodo come figlio SX, prima si tenta di proseguire verso il suo Filgio SX verso la sorgente, altrimenti, si tenta un'altra strada. Questo dovrebbe contenere la tortuosità...

Cosa ne pensate???

Io mi sono comunque già arenata nella scrittura della ricorsione... se qulcuno ritiene l'idea buona ed ha suggerimenti... grazie.

Se pensate sia sbagliato... grazie per il tempo che mi farete risparmiare!!!

- ostacolo (x0; y0; x1; y1)
Se i punti nel rettangolo R(x0; y0; x1; y1) non contengono alcun automa, inserisce l’ostacolo rappresentato
da R(x0; y0; x1; y1), altrimenti non compie alcuna operazione.

qualke dubbio:
quando creo l'ostacolo devo assicurarmi ke in quell'area non ci siano automi, dato ke memorizzo gli automi ordinandoli per nome, per vedere se un automa è presente in quell'area come faccio? qualcuno ha un'idea migliore di una ricerca esaustiva? dovrei crearmi un'altra struttura che ordina gli automi per posizione?
e se in quell'area è presente un altro ostacolo? possono sovrapporsi?

Originally posted by Polsy
- ostacolo (x0; y0; x1; y1)
Se i punti nel rettangolo R(x0; y0; x1; y1) non contengono alcun automa, inserisce l’ostacolo rappresentato
da R(x0; y0; x1; y1), altrimenti non compie alcuna operazione.

qualke dubbio:
quando creo l'ostacolo devo assicurarmi ke in quell'area non ci siano automi, dato ke memorizzo gli automi ordinandoli per nome, per vedere se un automa è presente in quell'area come faccio? qualcuno ha un'idea migliore di una ricerca esaustiva? dovrei crearmi un'altra struttura che ordina gli automi per posizione?
e se in quell'area è presente un altro ostacolo? possono sovrapporsi?