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

Pages (33): « First ... « 6 7 8 9 [10] 11 12 13 14 » ... 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 holylaw on 13-02-2005 12:43:

prova a fare una cosa del genere:
valore_assoluto_di_x= (x<0) ? -x : x;

__________________
La mia epoca ed io non siamo fatti l'uno per l'altro:questo è chiaro. Ma è da vedere chi di noi due vincerà il processo di fronte al tribunale dei posteri.
AV MJØDEN VART DU VIS OG KLOK, SÅ DREKKA MER!!!!
Le persone sagge parlano perché hanno qualcosa da dire.
Le persone sciocche perché hanno da dire qualcosa.

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

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, se esiste un cammino allora quello è già minimo, e vale esattamente la distanza tra l'automa e la sorgente (intesa come differenza tra le y + differenza tra le x)
il problema è trovare la tortuosità minore, ke tra l'altro (mi è venuta l'illuminazione ieri sera) non significa trovare il cammino con tortuosità minore
mi spiego meglio: ho sclerato per 3-4 giorni sulla storia dei cammini perkè tentavo di trovare il singolo cammino con tortuosità minore di tutte e poi contarne la tortuosità, e poi mi sono accorta ke mi interessava solo la tortuosità, non lo specifico cammino ke me la facesse ottenere

Dal testo del progetto :

Quando un automa si sposta sceglie, fra
i percorsi a distanza minima, quello meno tortuoso. Ad esempio, 11 può andare direttamente in X con un percorso di tortuosità 0, l'unico percorso per 10 ha tortuosità 1 mentre la minima tortuosità di un percorso per 101 è 2.

Si richiede di implementare una struttura dati effciente che permetta di eseguire le operazioni seguenti
(si tenga presente che la minima porzione rettangolare di piano contenente tutti gli automi e tutti gli
ostacoli può essere molto grande rispetto al numero di automi e ostacoli presenti, quindi non è sicuramente
efficiente rappresentare il piano mediante una matrice).

Quindi sbagli a leggere quanto chiede il professore da quel che leggo io. Lui chiede chiaramente di trovare fra tutti i percorsi liberi a distanza minima quello meno tortuoso che sarà quello che l'automa dovrà scegliere (e se quelli a distanza minima sono bloccati da ostacoli non deve muoversi se ho letto bene gli esempi) Per come è il testo e come sono gli esempi è facile sbagliarsi e cercare scorciatoie per semplificare il problema, tuttavia non è semplificabile.
E l'uso di matrici estese lo sconsiglia, quindi potrebbe anche non accettare soluzioni di forza bruta di quel genere.

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

Originally posted by wingzero
Dal testo del progetto :

Quindi sbagli a leggere quanto chiede il professore da quel che leggo io. Lui chiede chiaramente di trovare fra tutti i percorsi liberi a distanza minima quello meno tortuoso che sarà quello che l'automa dovrà scegliere (e se quelli a distanza minima sono bloccati da ostacoli non deve muoversi se ho letto bene gli esempi) Per come è il testo e come sono gli esempi è facile sbagliarsi e cercare scorciatoie per semplificare il problema, tuttavia non è semplificabile.
E l'uso di matrici estese lo sconsiglia, quindi potrebbe anche non accettare soluzioni di forza bruta di quel genere.

hmm...potremmo andare al ricevimento di aguzzoli e chiedere
a) se nelle specifiche del progetto viene richiesto anke qual'è il singolo percorso con tortuosità minima (io ho assunto ke non fosse richiesto primo perkè non fa parte dell'output ma sembra solo una conoscenza di "supporto" x il calcolo delle tortuosità, secondo perkè potrebbero esserci + cammini con tortuosità minima, x cui avrei bisogno di un criterio x scegliere uno rispetto all'altro)
b) se è accettabile come tempi fare un brute force sui cammini

quand'è il ricevimento di aguzzoli?

Posted by fdecollibus on 13-02-2005 13:05:

Mercoledì 15-16

Posted by wingzero on 13-02-2005 13:06:

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, se esiste un cammino allora quello è già minimo, e vale esattamente la distanza tra l'automa e la sorgente (intesa come differenza tra le y + differenza tra le x)

Scusa ma quello che hai scritto qui è impossibile. Guarda bene gli esempi, l'automa 101 ha più di un cammino da distanza 8, di cui quello più diretto (in basso di 3 e sinistra di 5) è inaccessibile perchè c'è l'ostacolo...
L'automa 110 ha il cammino minimo con tortuosità 0 e distanza 8 (a sinistra di 8) ostruito dal medesimo ostacolo che blocca 101 e qualsiasi altro percorso libero ha maggiore tortuosità (quindi non andrebbe scelto) e maggiore distanza (quindi non deve muoversi anche se ha un cammino libero che è minimo fra quelli disponibili).
Per 101 il discorso è diverso perchè ci sono più cammini minimi con 8 di distanza come quello ostruito dall'ostacolo.
Insomma, è un bel problema creare un algoritmo funzionante per tenere conto di tutto quello che viene richiesto e non c'è una soluzione semplice per risolvere il problema.

Posted by wingzero on 13-02-2005 13:23:

Originally posted by holylaw
prova a fare una cosa del genere:
valore_assoluto_di_x= (x<0) ? -x : x;

stdlib.h dell' ANSI C standard contiene la funzione abs() che ritorna il valore assoluto di un intero.

Posted by Polsy on 13-02-2005 13:30:

Originally posted by wingzero
Scusa ma quello che hai scritto qui è impossibile. Guarda bene gli esempi, l'automa 101 ha più di un cammino da distanza 8, di cui quello più diretto (in basso di 3 e sinistra di 5) è inaccessibile perchè c'è l'ostacolo...
L'automa 110 ha il cammino minimo con tortuosità 0 e distanza 8 (a sinistra di 8) ostruito dal medesimo ostacolo che blocca 101 e qualsiasi altro percorso libero ha maggiore tortuosità (quindi non andrebbe scelto) e maggiore distanza (quindi non deve muoversi anche se ha un cammino libero che è minimo fra quelli disponibili).
Per 101 il discorso è diverso perchè ci sono più cammini minimi con 8 di distanza come quello ostruito dall'ostacolo.
Insomma, è un bel problema creare un algoritmo funzionante per tenere conto di tutto quello che viene richiesto e non c'è una soluzione semplice per risolvere il problema.

scusa ma quello ke hai scritto non contraddice la mia tesi, anzi
110 come unico cammino avrebbe quello in linea retta, cioè l'unico cammino tracciabile all'interno dell'ipotetico "rettangolo" (ke in questo caso è un segmento) tra l'automa e la sorgente
tutti i presunti percorsi che hanno lunghezza maggiore presuppongono ke tu esca da questo rettangolo e/o ti allontani dalla sorgente rispetto al passo precedente, x cui non sono da considerare come cammini
se il percorso è un cammino invece, la sua lunghezza è x forza uguale alla distanza tra l'automa e la sorgente, x cui tutti i cammini esistenti hanno lunghezza uguale, ecco perkè non si deve parlare di cammino minimo

Posted by wingzero on 13-02-2005 13:34:

Originally posted by Polsy
se il percorso è un cammino invece, la sua lunghezza è x forza uguale alla distanza tra l'automa e la sorgente, x cui tutti i cammini esistenti hanno lunghezza uguale, ecco perkè non si deve parlare di cammino minimo

Dico solo questo, sbagli. La lunghezza dipende da quale fra le combinazioni degli spostamenti possibili viene scelta (combinazioni che cambiano in base agli ostacoli sulla mappa poi). Per quell'automa con più distanze minime uguali è solo perchè è un caso particolare.

Posted by Polsy on 13-02-2005 13:51:

Originally posted by wingzero
Dico solo questo, sbagli. La lunghezza dipende da quale fra le combinazioni degli spostamenti possibili viene scelta (combinazioni che cambiano in base agli ostacoli sulla mappa poi).

scusa, se tu poni come condizione ke ti puoi muovere solo in direzione della sorgente e mettiamo caso ke l'automa sia nel punto 0,0 e la sorgente nel punto 5,7
pongo come condizione ke l'automa si muova solo in direzione della sorgente, quindi scelgo come 2 uniche direzioni possibili la destra e l'alto
l'automa dovrà in totale fare 5 passi a dx e 7 in alto qualsiasi percorso scelga
te lo dimostro x assurdo
se facesse un percorso + breve allora avrei 3 casi: o ha fatto meno di 5 passi a dx o ha fatto meno di 7 passi in alto, o entrambe le cose, in ognuno del 3 casi è sempre un po' a sx e/o un po' in basso rispetto alla sorgente (= non l'ha raggiunta)
se facesse un percorso + lungo allora avrei 2 casi:
-ha fatto + di 5 passi a dx--> deve farne almeno 1 a sx per arrivare sull'ascissa della sorgente --> impossibile x ipotesi
-ha fatto + di 7 passi in alto--> deve farne almeno uno in basso x arrivare sull'ordinata della sorgente --> impossibile x ipotesi

di conseguenza per qualsiasi percorso esistente l'automa compie 5 passi a dx e 7 in alto, quindi 12 passi in totale
il realtà quello ke cambia non è il numero di passi, ma l'ordine

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

Scusate ma mi sto perdendo.
Prima accennavo a 3 algoritmi come idea. In effetti è vero che a noi non interessa il cammino minimo (in quanto la distanza minima è una sola).
Partiamo dall'inizio: tutti i punti appartenenti al rettangolo inscritto tra l'automa e il punto di arrivo fanno parte di un grafo orientato...

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

Prima domanda: come lo costruiamo un grafo?

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

Originally posted by elpampero
Scusate ma mi sto perdendo.
Prima accennavo a 3 algoritmi come idea. In effetti è vero che a noi non interessa il cammino minimo (in quanto la distanza minima è una sola).
Partiamo dall'inizio: tutti i punti appartenenti al rettangolo inscritto tra l'automa e il punto di arrivo fanno parte di un grafo orientato...

E' il testo del progetto che resta ambiguo ma è il cammino minimo ciò che interessa. Altrimenti Dijkstra ed il digrafo neanche li dovresti prendere in considerazione in pratica.

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

avevo gia' accennato ai grafi qualche post fa... io dicevo di costruirne uno che contenesse tutti i punti dei rettangoli tra la sorgente e i vari automi,ovviamente bisogna tirar via i punti doppi, poi bisogna eliminare i punti che fanno parte di ostacoli e alla fine si usa una vista in ampiezza.

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

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

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

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

esatto, serve per sapere se esiste un percorso, xo' bisogna tenere anche una variabile che mi indichi la tortuosita'.

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

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