.dsy:it. - [Algoritmi] Progetto "RICHIAMI"

Pages (33): « First ... « 7 8 9 10 [11] 12 13 14 15 » ... Last »
Show 150 posts per page

.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)

Posted by elpampero on 13-02-2005 14:22:

Ok p2p! Cosa intendi però per punti doppi? Come lo costruiamo un grafo?

Posted by wingzero on 13-02-2005 14:31:

Originally posted by elpampero
Forse mi sono espresso male. Noi non dobbiamo trovare il cammino minimo tra i due punti in quanto tale cammino è banalmente data da |x0-x1|+|y0-y1|. Quindi lo visita del nostro grafo non serve per trovare questa distanza rispetto ad altre (in quanto sappiamo già quanto debba essere) ma serve per capire se esite un percorso

La distanza minima che dice il professore sul testo serve per stabilire poi se e come deve muoversi l'automa. Ma certo che devi trovare il percorso minimo. I casi degli automi 101 e 110 nella mappa di esempio fanno vedere chiaramente il problema come ho detto nei post precedenti.

Posted by elpampero on 13-02-2005 14:38:

Sì, wingzero. Ma la distanza minima si trova con un semplice calcolo! Il problema è stabilire se tra i vari percorsi minimi (tutti con tortuosità diversa) ne esiste almeno uno che arriva a destinazione!

Posted by wingzero on 13-02-2005 14:49:

Originally posted by elpampero
Sì, wingzero. Ma la distanza minima si trova con un semplice calcolo! Il problema è stabilire se tra i vari percorsi minimi (tutti con tortuosità diversa) ne esiste almeno uno che arriva a destinazione!

Appunto. Quindi dal punto alla sorgente dobbiamo trovare il cammino minimo che si attenga ad essere equivalente alla distanza minima e che abbia il minor numero di cambi di direzione, e che ovviamente sia libero e percorribile.

Posted by elpampero on 13-02-2005 15:02:

Questo non lo so in quanto non so bene come implementare un grafo orientato.
Se lo implementassimo con una lista di adiacenza saremmo noi a decidere i vertici collegati da archi e il percorso minimo è implicito

Posted by wingzero on 13-02-2005 15:39:

Ho pensato a questo piccolo esempio per dimostrare come possa esistere, in presenza di ostacoli, un percorso libero che possa consentire ad un automa a tot coordinate di raggiungere una sorgente in determinate coordinate, ma che essendo un percorso superiore alla distanza minima non debba essere seguito. Tuttavia per saperlo uno deve per forza verificare le combinazioni disponibili dei percorsi liberi.

Intendo questo.

Mappa:

Automa a coordinate iniziali (0,0)
Sorgente a coordinate (6,-7)
[quindi rettangolo 6x7 fra i due punti]

Ostacolo #1, rettangolo da (5,2) a (9,-3)
Ostacolo #2, rettangolo da (-4,-2) a (3,-3)
Ostacolo #3, rettangolo da (4,-5) a (11,-6)

Un percorso libero per automa per raggiungere la sorgente, spostandosi il più possibile verso di essa potrebbe essere:

(0,0) -> destra di 4
(4,0) -> basso di 4
(4,-4) -> sinistra di 1
(3,-4) -> basso di 3
(3,-7) -> destra di 3
(6,-7) RAGGIUNTA LA SORGENTE

Totale distanza : 4+4+1+3+3 = 15

Se l'ostacolo/rettangolo #3 fosse partito da (5,-5) a (11,-6) , allora l'automa avrebbe avuto un percorso di lunghezza equivalente alla distanza minima che è |6-0|+|-7+0|=13. Questo:

(0,0) -> destra di 4
(4,0) -> basso di 7
(4,-7) -> destra di 2
(6,-7) RAGGIUNTA LA SORGENTE

Totale distanza : 4+7+2 = 13

Spero di non aver sbagliato qualche coordinata nell'esempio, altrimenti diventa difficile da riprodurre.

La presenza degli ostacoli cambia necessariamente le combinazioni esistenti ed in più bisogna calcolarsi il numero di cambi direzione. Il che non rende la distanza minima tanto banale come può sembrare.

Posted by Polsy on 13-02-2005 16:10:

Originally posted by wingzero
Mappa:

Automa a coordinate iniziali (0,0)
Sorgente a coordinate (6,-7)
[quindi rettangolo 6x7 fra i due punti]

ok, quindi per la condizione ke intendevo implicita all'inizio l'automa si può muovere solo a destra e in basso (=verso la sorgente)

Ostacolo #1, rettangolo da (5,2) a (9,-3)
Ostacolo #2, rettangolo da (-4,-2) a (3,-3)
Ostacolo #3, rettangolo da (4,-5) a (11,-6)

Un percorso libero per automa per raggiungere la sorgente, spostandosi il più possibile verso di essa potrebbe essere:

(0,0) -> destra di 4
(4,0) -> basso di 4
(4,-4) -> sinistra di 1
(3,-4) -> basso di 3
(3,-7) -> destra di 3
(6,-7) RAGGIUNTA LA SORGENTE

Totale distanza : 4+4+1+3+3 = 15

non può andare a sinistra x le condizioni iniziali-->questo non è un cammino accettabile
in questo esempio infatti la funzione esiste cammino dà no come risposta

Se l'ostacolo/rettangolo #3 fosse partito da (5,-5) a (11,-6) , allora l'automa avrebbe avuto un percorso di lunghezza equivalente alla distanza minima che è |6-0|+|-7+0|=13. Questo:

(0,0) -> destra di 4
(4,0) -> basso di 7
(4,-7) -> destra di 2
(6,-7) RAGGIUNTA LA SORGENTE

Totale distanza : 4+7+2 = 13

e questo rispetta le condizioni iniziali (si muove solo in basso e a destra) x cui può considerarsi un cammino, e cvd ha lunghezza esattamente pari alla distanza tra l'automa e la sorgente

Posted by wingzero on 13-02-2005 16:40:

Metti che un segnale fosse a (10,0)
Spostamento diretto a destra sarebbe distanza 10.
Ma un percorso per raggiungerlo libero aggirando l'ostacolo, e sempre spostandosi verso il segnale: (4,0) -> (4,3) -> (10,3) -> (10,0) = 16

Metti che un segnale fosse a (0,-4)
Spostamento diretto in basso di 4 : impraticabile per ostacolo.
L'automa (0,0) potrebbe raggiungerlo da entrambe le direzioni aggirando l'ostacolo in quella mappa....
sia destra -> basso -> sinistra come movimento
che sinistra -> basso -> destra
Ed in tale caso specifico cosa consideri come congiunzione fra il punto del segnale e l'automa ? Il rettangolo degenerato di larghezza zero e lunghezza 4 o l'altro rettangolo poi ?
Ma soprattutto come fai ragionando così a tenere conto di tutti questi parametri per calcolarti il percorso libero minimo con tortuosità minore ?

Quindi non è detto che esista un solo modo per raggiungere un segnale per un automa, spostandosi sempre verso di esso. Dipende dalle configurazioni della mappa e degli ostacoli....

Posted by nothingman7 on 13-02-2005 17:48:

scusate ma voi non avete per caso trovato un errore nel output del testo..per quanto riguarda il segnale..secondo me sia l'automa 1 sia 0 raggiungono il segnale..ho disegnato su carta il piano con gli automi gli ostacoli..
l'output del prof dice che rimangono fermi, secondo me no..infatti esiste chiaramente il passaggio..bho..ho mandato un'email al prof ma non mi ha risposto..spero in un suo chiarimento

Posted by Polsy on 13-02-2005 18:00:

Originally posted by wingzero
Metti che un segnale fosse a (10,0)
Spostamento diretto a destra sarebbe distanza 10.
Ma un percorso per raggiungerlo libero aggirando l'ostacolo, e sempre spostandosi verso il segnale: (4,0) -> (4,3) -> (10,3) -> (10,0) = 16

Metti che un segnale fosse a (0,-4)
Spostamento diretto in basso di 4 : impraticabile per ostacolo.
L'automa (0,0) potrebbe raggiungerlo da entrambe le direzioni aggirando l'ostacolo in quella mappa....
sia destra -> basso -> sinistra come movimento
che sinistra -> basso -> destra
Ed in tale caso specifico cosa consideri come congiunzione fra il punto del segnale e l'automa ? Il rettangolo degenerato di larghezza zero e lunghezza 4 o l'altro rettangolo poi ?
Ma soprattutto come fai ragionando così a tenere conto di tutti questi parametri per calcolarti il percorso libero minimo con tortuosità minore ?

Quindi non è detto che esista un solo modo per raggiungere un segnale per un automa, spostandosi sempre verso di esso. Dipende dalle configurazioni della mappa e degli ostacoli....

ho l'impressione ke ti sfugga sempre una parte del mio discorso
con "l'automa deve dirigersi sempre verso la sorgente" intendo ke se la sorgente è a S-E l'automa non può MAI fare nemmeno un passo nè verso nord nè verso ovest, ora tu mi puoi citare 10000 esempi ke ignorano questa restrizione e ovviamente otterrai percorsi di lunghezza maggiore ma tanto li devi buttare via perkè non sono accettabili
il punto è: puoi usare questa restrizione e assumere che tutti i percorsi ke la rispettano hanno lunghezza uguale, oppure puoi ignorarla e calcolarti TUTTI i percorsi possibili e immaginabili del piano e tra questi scegliere quelli che hanno lunghezza pari alla distanza tra sorgente e automa, ma comunque otterrai lo stesso risultato, il tutto dipende da quanto vuoi complicarti la vita

Posted by Polsy on 13-02-2005 20:10:

Originally posted by nothingman7
scusate ma voi non avete per caso trovato un errore nel output del testo..per quanto riguarda il segnale..secondo me sia l'automa 1 sia 0 raggiungono il segnale..ho disegnato su carta il piano con gli automi gli ostacoli..
l'output del prof dice che rimangono fermi, secondo me no..infatti esiste chiaramente il passaggio..bho..ho mandato un'email al prof ma non mi ha risposto..spero in un suo chiarimento

s 2 7 1
chiama 1, 10 e 11 nella posizione 2,7
1 è a distanza 18 ed esiste un cammino
10 è a distanza 6 ed esiste un cammino
11 è a distanza 6 ed esiste un cammino
dato ke si muovono solo gli automi + vicini, 10 e 11 raggiungono la sorgente, mentre 1 resta fermo, infatti le posizioni finali sono
(
1: -13, 4
10: 2, 7
11: 2, 7
)

s 2 7 0
chiama 0, 00 e 01 in 2,7
0 è a distanza 15, ma non esiste un cammino (ricorda ke i lati e i vertici di un ostacolo sono da considerare occupati, quindi l'automa non può passare tra l'ostacolo 7,11,8,13 e l'ostacolo 9,2,12,10)
00 è a distanza 22 ed esiste un cammino
01 è a distanza 17 ed esiste un cammino
l'automa + vicino alla sorgente x cui esiste un cammino è 01 x cui si muove solo lui
posizioni finali:
(
0: 13, 11
00: -10, -3
01: 2, 7
)

Posted by p2p on 13-02-2005 20:14:

Polsy, tu come stai implementando il tutto? con un grafo o altro?

Posted by virtual on 13-02-2005 20:14:

Originally posted by Polsy
ragazzi, qui il problema non è trovare il cammino minimo visto ke se poniamo come condizione ke l'automa si debba spostare sempre e solo verso la sorgente...[cut]

Secondo me Polsy ha azzeccato una delle strade possibili. Il ragionamento è giusto.
Basta regionare sulla tortuosità, ovvero.... QUANDO LA TORTUOSITA' AUMENTA?
Aumenta quando passo da un movimento VERTICALE ad un movimento ORIZZONTALE. Percio' dovro' portarmi dietro due variabili che mi indicano che movimento stavo facendo prima e quindi, in base al movimento che sto facendo ora aumento oppure no la tortuosità.
La soluzione con backtrack pero' non è il massimo della performance, le chiamate ricorsive sono fatte su una "matrice" nxm.
La costruzione del grafo secondo me è troppo uno sbattimento.
Qualsiasi sia la strada la lunghezza del cammino è sempre la stessa.
Quello che fa la differenza tra un cammino ed un altro è la tortuosità perchè è quella che determina se un automa si deve spostare o no a seguito del segnale.

Posted by Skilotto83 on 13-02-2005 20:27:

come gia' detto da polsy la distanza o lunghezza di ogni percorso è uguale!!!Non puo' essere altrimenti...
Il discorso è che se con il comando alfa=01 si possono muovere 10 automi con distanza 8 e 10 con distanza 9 si muovono solo quelli con distanza 8...
L'unika kosa che conta è la tortuosita'...
io sto facendo un algoritmo per quello...
Solo che il problema è che devo kmq sbattere la testa sull'ostacolo per capire che ho sbagliato...la cosa perfetta sarebbe di saperlo ancor prima di sbatterci...
Ci sto pensando..kazzo...

__________________
"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

Posted by Polsy on 13-02-2005 20:47:

Originally posted by p2p
Polsy, tu come stai implementando il tutto? con un grafo o altro?

come avevo scritto prima ho pensato a una matrice, ma poi il backtracking esaustivo è molto brutto come tempi...diciamo ke quella è proprio l'ultima spiaggia
ora stavo pensando a un grafo di intervalli, di modo da non avere tanti nodi quanti sono i punti, ma tanti nodi quante sono le "strade" (x intenderci, se posso arrivare da A a B in linea retta con n passi, non mi interessa avere n nodi, ma solo 1 nodo di intervallo <posizione di A> - <posizione di B> ) cmq questa idea è ancora in fase embrionale, se riesco a cavarci fuori qualcosa di buono magari lo posto

altre proposte?

All times are GMT. The time now is 20:31.

Pages (33): « First ... « 7 8 9 10 [11] 12 13 14 15 » ... Last »
Show all 482 posts from this thread on one page