 |
 elpampero |
| Ok p2p! Cosa intendi però per punti doppi? Come l ... |
13-02-2005 14:22 |
|
 |
elpampero |
Aniversario
Registered: Sep 2003
Posts: 911 (0.11 al dì)
Location: Milano
Corso: Informatica Magistrale
Anno: I
Time Online: 8 Days, 3:06:36 [...]
Status: Offline
Edit | Report | IP: Logged |
Ok p2p! Cosa intendi però per punti doppi? Come lo costruiamo un grafo?
|
|
13-02-2005 14:22 |
|
|
| |
|
| wingzero |
| [QUOTE][i]Originally posted by elpampero [/i]
... |
13-02-2005 14:31 |
|
|
wingzero |
.precettore.
Registered: Mar 2004
Posts: 96 (0.01 al dì)
Location:
Corso: Diploma Univ. Informatica
Anno: Laureato
Time Online: 1 Day, 11:14:09: [...]
Status: Offline
Edit | Report | IP: Logged |
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.
|
|
13-02-2005 14:31 |
|
|
| |
|
| elpampero |
| Sì, wingzero. Ma la distanza minima si trova con ... |
13-02-2005 14:38 |
|
|
elpampero |
Aniversario
Registered: Sep 2003
Posts: 911 (0.11 al dì)
Location: Milano
Corso: Informatica Magistrale
Anno: I
Time Online: 8 Days, 3:06:36 [...]
Status: Offline
Edit | Report | IP: Logged |
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!
|
|
13-02-2005 14:38 |
|
|
| |
|
| wingzero |
| [QUOTE][i]Originally posted by elpampero [/i]
... |
13-02-2005 14:49 |
|
|
wingzero |
.precettore.
Registered: Mar 2004
Posts: 96 (0.01 al dì)
Location:
Corso: Diploma Univ. Informatica
Anno: Laureato
Time Online: 1 Day, 11:14:09: [...]
Status: Offline
Edit | Report | IP: Logged |
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.
|
|
13-02-2005 14:49 |
|
|
| |
|
| elpampero |
| Questo non lo so in quanto non so bene come implem ... |
13-02-2005 15:02 |
|
|
elpampero |
Aniversario
Registered: Sep 2003
Posts: 911 (0.11 al dì)
Location: Milano
Corso: Informatica Magistrale
Anno: I
Time Online: 8 Days, 3:06:36 [...]
Status: Offline
Edit | Report | IP: Logged |
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
|
|
13-02-2005 15:02 |
|
|
| |
|
| wingzero |
| Ho pensato a questo piccolo esempio per dimostrare ... |
13-02-2005 15:39 |
|
|
wingzero |
.precettore.
Registered: Mar 2004
Posts: 96 (0.01 al dì)
Location:
Corso: Diploma Univ. Informatica
Anno: Laureato
Time Online: 1 Day, 11:14:09: [...]
Status: Offline
Edit | Report | IP: Logged |
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.
|
|
13-02-2005 15:39 |
|
|
| |
|
| Polsy |
| [QUOTE][i]Originally posted by wingzero [/i]
... |
13-02-2005 16:10 |
|
|
Polsy |
.arcimaestro.
Registered: Dec 2003
Posts: 477 (0.06 al dì)
Location:
Corso: Info phd
Anno:
Time Online: 17 Days, 17:11:50 [...]
Status: Offline
Edit | Report | IP: Logged |
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
|
|
13-02-2005 16:10 |
|
|
| |
|
| wingzero |
| Metti che un segnale fosse a (10,0)
... |
13-02-2005 16:40 |
|
|
wingzero |
.precettore.
Registered: Mar 2004
Posts: 96 (0.01 al dì)
Location:
Corso: Diploma Univ. Informatica
Anno: Laureato
Time Online: 1 Day, 11:14:09: [...]
Status: Offline
Edit | Report | IP: Logged |
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....
Last edited by wingzero on 13-02-2005 at 16:44
|
|
13-02-2005 16:40 |
|
|
| |
|
| nothingman7 |
| scusate ma voi non avete per caso trovato un error ... |
13-02-2005 17:48 |
|
|
nothingman7 |
.amico.
Registered: Nov 2003
Posts: 38 (0.00 al dì)
Location: Milano
Corso: informatica
Anno: 2
Time Online: 1 Day, 1:57:27 [...]
Status: Offline
Edit | Report | IP: Logged |
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
|
|
13-02-2005 17:48 |
|
|
| |
|
| Polsy |
| [QUOTE][i]Originally posted by wingzero [/i]
... |
13-02-2005 18:00 |
|
|
Polsy |
.arcimaestro.
Registered: Dec 2003
Posts: 477 (0.06 al dì)
Location:
Corso: Info phd
Anno:
Time Online: 17 Days, 17:11:50 [...]
Status: Offline
Edit | Report | IP: Logged |
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
|
|
13-02-2005 18:00 |
|
|
| |
|
| Polsy |
| [QUOTE][i]Originally posted by nothingman7 [/i]
... |
13-02-2005 20:10 |
|
|
Polsy |
.arcimaestro.
Registered: Dec 2003
Posts: 477 (0.06 al dì)
Location:
Corso: Info phd
Anno:
Time Online: 17 Days, 17:11:50 [...]
Status: Offline
Edit | Report | IP: Logged |
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
)
|
|
13-02-2005 20:10 |
|
|
| |
|
| p2p |
| Polsy, tu come stai implementando il tutto? con un ... |
13-02-2005 20:14 |
|
|
p2p |
.arcimaestro.
Registered: Oct 2002
Posts: 377 (0.04 al dì)
Location:
Corso: informatica
Anno:
Time Online: 4 Days, 7:49:11 [...]
Status: Offline
Edit | Report | IP: Logged |
Polsy, tu come stai implementando il tutto? con un grafo o altro?
|
|
13-02-2005 20:14 |
|
|
| |
|
| virtual |
| [QUOTE][i]Originally posted by Polsy [/i]
... |
13-02-2005 20:14 |
|
|
virtual |
Scheggia Impazzita
Registered: Feb 2004
Posts: 167 (0.02 al dì)
Location: [MI]
Corso: Informatica
Anno: FINITO!
Time Online: 3 Days, 14:30:20 [...]
Status: Offline
Edit | Report | IP: Logged |
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.
|
|
13-02-2005 20:14 |
|
|
| |
|
| Skilotto83 |
| come gia' detto da polsy la distanza o lunghezza d ... |
13-02-2005 20:27 |
|
|
Skilotto83 |
..Energia positiva...
Registered: Jun 2003
Posts: 1608 (0.19 al dì)
Location: Arconate
Corso: Informatica
Anno: LAUREATO!!!
Time Online: 15 Days, 6:32:44 [...]
Status: Offline
Edit | Report | IP: Logged |
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
|
|
13-02-2005 20:27 |
|
|
| |
|
| Polsy |
| [QUOTE][i]Originally posted by p2p [/i]
... |
13-02-2005 20:47 |
|
|
Polsy |
.arcimaestro.
Registered: Dec 2003
Posts: 477 (0.06 al dì)
Location:
Corso: Info phd
Anno:
Time Online: 17 Days, 17:11:50 [...]
Status: Offline
Edit | Report | IP: Logged |
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?
|
|
13-02-2005 20:47 |
|
|
| |
|
| All times are GMT. The time now is 20:41. |
|
|
 |
|
 |
|
|
| |
Forum Rules:
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts
|
HTML code is OFF
vB code is ON
Smilies are ON
[IMG] code is ON
|
|
|
|
|
|
elpampero
