 | |
Il progetto dsy.it è l'unofficial support site dei corsi di laurea del Dipartimento di Scienze dell'Informazione e del Dipartimento di Informatica e Comunicazione della Statale di Milano. E' un servizio degli studenti per gli studenti, curato in modo no-profit da un gruppo di essi. I nostri servizi comprendono aree di discussione per ogni Corso di Laurea, un'area download per lo scambio file, una raccolta di link e un motore di ricerca, il supporto agli studenti lavoratori, il forum hosting per Professori e studenti, i blog, e molto altro...
In questa sezione è indicizzato in textonly il contenuto del nostro forum |
[Algoritmi] Progetto "RICHIAMI"
Clicca QUI per vedere il messaggio nel forum |
| luca8684 |
Originally posted by mark
da tastiera ?
ma tutte le coordinate degli ostacoli e degli atomi etc... vengono inseriti a mano da chi testerà il nostro programma ?
io sto lavorando con i file
cavolo, non ditemi che sto lavorando per niente
non usare i file leggi da tastiera, cos' se dopo vuoi leggere da file basta fare la redirezione e leggi comunque da file per non riscrivere tutto ogni volta |
| mark |
Originally posted by luca8684
non usare i file leggi da tastiera, cos' se dopo vuoi leggere da file basta fare la redirezione e leggi comunque da file per non riscrivere tutto ogni volta
allora non ho capito una mazza.....
per capire; viene digitato da tastiera ad esempio:
o -8 5 -2 2
ed io non faccio(cioè visualizzo) nulla ** sino a quando non leggo il carattere 'f' ?
** in realtà faccio la mia chiamata al mio qualcosa ma non si dire qui a cosa :) |
| Granito |
Scusate la domande. Usando delle liste per l'inserimento degli automi e degli ostacoli, secondo voi c'è un modo per implementare la procedura tortuosità senza usare l'algoritmo di backtracking che di suo visita alberi?
Grazie mille a chi risponderà!
Granito |
| wingzero |
Stavo riguardando la griglia/mappa d'esempio data dal professore.
E non so se mi sbaglio io a leggerla.. ma , l'automa 101 secondo le regole del progetto non dovrebbe stare fermo ?
Allora. 110 non si può spostare verso il segnale X perchè il percorso minimo con tortuosità 0 verso X è bloccato dall'ostacolo e quindi non può raggiungerlo spostandosi direttamente a sinistra.
Per 101.. viene detto che sceglie il percorso di lunghezza 8 con tortuosità 2 , due cambi di direzione.
Tuttavia, 101 se non vi fosse lo stesso ostacolo che impedisce a 110 di raggiungere X raggiungerebbe il segnale medesimo sempre con 8 mosse ed 1 solo cambio direzione, o no? in basso di tre, a sinistra di 5 , no ? e quindi il cambio di direzione minimo sarebbe 1 e quindi non dovrebbe scegliere nessuno degli altri percorsi minimi sempre di lunghezza 8 ma con tortuosità 2 che gli fanno raggiungere il segnale X, giusto ?
Per 110 il percorso a distanza minima è bloccato dall'ostacolo e mi sta bene. Ma per 101 ci sono più percorsi di lunghezza 8 e diversa tortuosità che lo collegano ad X.
Infatti 101 potrebbe raggiungere X sempre con 1 solo cambio direzione , tortuosità 1, spostandosi a sinistra di 5 ed in basso di 8 .. giusto ?
Quindi perchè sull'esempio c'è scritto che può muoversi con tortuosità 2 e distanza 8 ?
Sbaglio io a leggere o c'è un errore ?
Probabilmente sbaglio io, devo solo considerare i percorsi minimi liberi e quindi anche la tortuosità degli stessi ?
E quindi 110 se avesse avuto un altro percorso verso X ma libero senza ostacoli di medesima lunghezza e maggiore tortuosità lo avrebbe scelto così come ha fatto 101 ?
|
| p2p |
Originally posted by Granito
Scusate la domande. Usando delle liste per l'inserimento degli automi e degli ostacoli, secondo voi c'è un modo per implementare la procedura tortuosità senza usare l'algoritmo di backtracking che di suo visita alberi?
Grazie mille a chi risponderà!
Granito
backtracking funziona "come" se stesse visitando un albero, ma non è che devi usarlo solo con gli alberi, basta che gli passi i punti adiacenti per continuare la ricorsione, almeno io sto cercando di farlo cosi' |
| Jacoposki |
| diomio.... sentite, cercate di capirmi, io ho appena finito di seguire il corso di programmazione (primo anno) e ho ancora la testa che pensa in Java... non è che in questi giorni trovo al silab qualcuno di voi che possa darmi una mano sulle cose più futili del C? sigh sigh |
| wingzero |
Originally posted by p2p
backtracking funziona "come" se stesse visitando un albero, ma non è che devi usarlo solo con gli alberi, basta che gli passi i punti adiacenti per continuare la ricorsione, almeno io sto cercando di farlo cosi'
Ma allora non c'è già il DFS (Depth First Search) per i grafi che fa già la stessa cosa di suo ? |
| mattcobain |
backtracking, dfs?!?!
....ma fiorentini quando mai ha pronunciato (non dico nemmeno spiegato) queste cose!?!?!? |
| p2p |
il problema che si presentava con i grafi era che bisogna memorizzare nel grafo tutti i punto compresi nel rettangolo tra automa e sorgente, generando un grafo anche molto grande... quindi si cercava di fare qualcosa di alternativo... solo che ti dico, con il backtracking non è che sia cosi facile come sembra perchè inanzitutto se dentro alla funzione di backtracking si fa un ciclo per vedere se il punto è un ostacolo o meno(la checkpos del prof) bisogna considerare che le coordinate a partite dalla x e la y dell automa, potrebbero aver bisogno di essere incrementate o decrementate a seconda di dove si trova l automa rispetto la sorgente, e gia' qui un doppio for puo' coprire solo uno dei 4 casi.. non so se mi sono spiegato... insomma ci sono un po' di problematiche...
se qualcuno volesse dire come sta facendo.... |
| p2p |
Originally posted by mattcobain
backtracking, dfs?!?!
....ma fiorentini quando mai ha pronunciato (non dico nemmeno spiegato) queste cose!?!?!?
MAII!!! |
| wingzero |
Sto ancora riguardando il testo del progetto...
Prima ho capito di essermi sbagliato ad interpretare le specifiche a quanto sembra su come devono muoversi questi automi e l'ho detto nel post.
Ora però, o è troppo tempo che lo rileggo.. tuttavia..
sull'esempio di input.. sbaglio anche questa volta o l'utente non immette alcun comando per il segnale fino alla fine ?
Io non lo vedo nella lista dei comandi.
Allora se non c'è, come faccio a calcolarmi i comandi e e t per esistePercorso e tortuosità ?
Se non viene immesso un segnale prima, come posso calcolare percorsi liberi e tortuosità ? E' tutto lì il problema.. ma se i segnali vengono immessi alla fine di tutti i comandi in input .. l'esempio sbaglio anche questa volta o semplicemente è impossibile che funzioni così ?
Io non leggo nessun comando s fino alla fine dei comandi in input... |
| wingzero |
Originally posted by wingzero
Sto ancora riguardando il testo del progetto...
Prima ho capito di essermi sbagliato ad interpretare le specifiche a quanto sembra su come devono muoversi questi automi e l'ho detto nel post.
Ora però, o è troppo tempo che lo rileggo.. tuttavia..
sull'esempio di input.. sbaglio anche questa volta o l'utente non immette alcun comando per il segnale fino alla fine ?
Io non lo vedo nella lista dei comandi.
Allora se non c'è, come faccio a calcolarmi i comandi e e t per esistePercorso e tortuosità ?
Se non viene immesso un segnale prima, come posso calcolare percorsi liberi e tortuosità ? E' tutto lì il problema.. ma se i segnali vengono immessi alla fine di tutti i comandi in input .. l'esempio sbaglio anche questa volta o semplicemente è impossibile che funzioni così ?
Io non leggo nessun comando s fino alla fine dei comandi in input...
Mmmh... forse mi sono risbagliato io a leggere.. :cool:
Vabbè. Ho capito che esistePercorso e tortuosità funzionano comunque perchè calcolano su coordinate immesse che possono essere solo potenziali per un eventuale comando segnale. Questo credo sia giusto.
Poi il comando segnale fa effettivamente spostare gli automi che si spostano.
Il tutto così diventa più caotico da programmare ad occhio..
Ok, spero di aver chiarito eventuali dubbi ad altri oltre che a me stesso, ma il testo mi è apparso criptico in più punti, sinceramente. :-o |
| Jacoposki |
mah, a logica è:
- arriva il segnale
- vedo la posizione da cui arriva
- prendo gli automi interessati
- per ognuno di questi controllo esistePercorso
- se esistePercorso cambio la posizione degli automi con la posizione da cui arriva il segnale
Mi pare che la tortuosità non contribuisca a determinare se gli automi si muovono o meno... si muovono solo se esiste un percorso di lunghezza minima, la tortuosità è un punto a parte... nessuno ci chiede di dire quale percorso segue l'automa per spostarsi, mi pare.
Comunque rinnovo il disperato appello... nessuno passa o passerebbe al silab in questi giorni a parlare un po' di questo progetto? <;-( |
| wingzero |
Originally posted by Jacoposki
mah, a logica è:
- arriva il segnale
- vedo la posizione da cui arriva
- prendo gli automi interessati
- per ognuno di questi controllo esistePercorso
- se esistePercorso cambio la posizione degli automi con la posizione da cui arriva il segnale
Mi pare che la tortuosità non contribuisca a determinare se gli automi si muovono o meno... si muovono solo se esiste un percorso di lunghezza minima, la tortuosità è un punto a parte... nessuno ci chiede di dire quale percorso segue l'automa per spostarsi, mi pare.
Comunque rinnovo il disperato appello... nessuno passa o passerebbe al silab in questi giorni a parlare un po' di questo progetto? <;-(
Riguardo la tortuosità.. rileggi la definizione perchè c'è scritto chiaramente che l'automa fra i percorsi liberi deve scegliere quello a tortuosità minore (minor numero di cambi direzione).
Io avevo all'inizio pensato ad una restrizione al riguardo un pò diversa, poi ho capito che non voleva quello, tuttavia la tortuosità è comunque un parametro necessario per scegliere quale percorso far seguire all'automa. |
| p2p |
ragazzi, io dopo un po' di elucubrazioni sono giunto alla conclusione che "forse" il breadth-first search è la cosa piu' fattibile, perchè:
1) individua qualsiasi punto raggiungibile dalla sorgente(e quindi basta controllare se uno dei nostri automi è posizionato nei punti trovati dall' algoritmo,e poi si eseguono i controlli riguardanti le distanze);
2)il backtracking mi sembra un casino e non sono ancora riuscito ad implementarlo decentemente.
aspetti negativi:
1)bisogna costruire un grafo con tutti i punti compresi tra i vari automi e la sorgente cercando di eliminare i punti doppi, ovviamente.... anche qui non che sia poi cosi uno spreco di risorse xchè se devi vedere tutti i percorsi possibili non hai molte altre scelte.
2)bisogna fare una cifra di confronti... per vedere i punti, per vedere se gli automi ricadono nei punti, per gli ostacoli, ecc...
problema: come tengo traccia dei cambi di direzione???non saprei...
vorrei qualche commento da parte di chi si sta spaccando il cervello come me...
:)
voi che ne dite? cosa state facendo? |
| luca8684 |
| :alsono: :alsono: :alsono: :alsono: :alsono: :? :? :? :? :pccrash: :pccrash: :pccrash: |
| mark |
mi spiegate cosa intende con l'output
SI
4
NO
-1
etc.. ?
grazie 1000 |
| mark |
| pardon, trovato; mi era sfuggito |
| Jacoposki |
Originally posted by wingzero
Riguardo la tortuosità.. rileggi la definizione perchè c'è scritto chiaramente che l'automa fra i percorsi liberi deve scegliere quello a tortuosità minore (minor numero di cambi direzione).
Io avevo all'inizio pensato ad una restrizione al riguardo un pò diversa, poi ho capito che non voleva quello, tuttavia la tortuosità è comunque un parametro necessario per scegliere quale percorso far seguire all'automa.
Scusami se insisto... ma nessuno ci chiede di dire quale percorso segue l'automa. Il metodo tortuosità restituisce solo la tortuosità minima sui percorsi liberi, ma il movimento dell'automa consiste solo nel cambiare le variabili che indicano la posizione dell'automa se esiste un percorso libero di lunghezza minima.
....
proprio nessuno al silab, eh? :( |
| mark |
scusate ma non ho capito come lavora esistePercorso()
Il testo del progetto recita: se esiste un percorso libero di lunghezza D(P(n) , (x,y))
cosa vuol dire ?
altra particolarità: ma il programma dovrà generare l'output solo quando viene inserito il carattere 'f' ?? |
| wingzero |
Originally posted by mark
scusate ma non ho capito come lavora esistePercorso()
Il testo del progetto recita: se esiste un percorso libero di lunghezza D(P(n) , (x,y))
cosa vuol dire ?
altra particolarità: ma il programma dovrà generare l'output solo quando viene inserito il carattere 'f' ??
Spero non intenda quello altrimenti tener traccia di tutto l'history dei comandi e di ciò che fanno sulle strutture dati diventa una cosa assurda. Già è difficilissimo gestire il tutto in maniera dinamica su un mondo quadrato di signed int 32bit in C... |
| mark |
Originally posted by wingzero
Spero non intenda quello altrimenti tener traccia di tutto l'history dei comandi e di ciò che fanno sulle strutture dati diventa una cosa assurda. Già è difficilissimo gestire il tutto in maniera dinamica su un mondo quadrato di signed int 32bit in C...
io ho inteso che l'output viene generato nel momento in cui si digita 'f'
a mio avviso, prima non avrebbe molto senso |
| wingzero |
Originally posted by mark
io ho inteso che l'output viene generato nel momento in cui si digita 'f'
a mio avviso, prima non avrebbe molto senso
Io non credo sia come dici tu, perchè sul comando f viene solo detto che termina il programma. Se fosse come dici tu il professore avrebbero dovuto scrivere per il comando qualcosa del tipo : "Termina l'esecuzione del programma e genera l'output eseguendo tutti i comandi inseriti dall'utente nell'ordine dato".
O qualcosa del genere.
Visto che per il comando f viene solo detto che termina il programma, significa solo che interrompe il codice e torna al sistema operativo/prompt dei comandi. |
| p2p |
non si stampa alla fine. l esecuzione di ogni comando è immediata x cui se un comando deve stampare stampa se no esegue le se operazioni e basta, la f serve solo per uscire dal programma, in pratica nel tuo ciclo
case 'f':
/* Fine del programma. */
return 0;
break; |
| mark |
ma l'input non avviene riga per riga completa ?
esempio:
o 10 -5 8 12
non penso che uno si deve aspettare una cosa del tipo:
digitare un comando: o
e poi....
inserire le coordinate dell'ostacolo (x1,y1,x2,y2):
etc.....
in questo modo l'input sarebbe interminabile |
| p2p |
Originally posted by mark
ma l'input non avviene riga per riga completa ?
esempio:
o 10 -5 8 12
non penso che uno si deve aspettare una cosa del tipo:
digitare un comando: o
e poi....
inserire le coordinate dell'ostacolo (x1,y1,x2,y2):
etc.....
in questo modo l'input sarebbe interminabile
scusa , ma certo che se il comando o deve prendere dei parametri glieli devi dare subito, se non come fa ad andare in esecuzione??
leggi l esempio:
c //invio --> esecuzione del comando c;
o 12 12 12 12 // invio --> esecuzione del comando crea_ostacolo
ecc ecc
capito? |
| mark |
Originally posted by p2p
scusa , ma certo che se il comando o deve prendere dei parametri glieli devi dare subito, se non come fa ad andare in esecuzione??
leggi l esempio:
c //invio --> esecuzione del comando c;
o 12 12 12 12 // invio --> esecuzione del comando crea_ostacolo
ecc ecc
capito?
scusa ma non ci stiamo capendo
io posso tranquillamente digitare:
o 12 -8 15 67
e sapere gia dove memorizzare la linea di comando che farà qualche cosa, nel caso sopra costruire un ostacolo.
Tu invece, sembra che mi stai dicendo che un utente dovra vedere una cosa del tipo:
Menu principale
0) "c" per inizializzare
1) digita "o" per inserire un ostacolo
2) digita "a" per inserire un automa
3) ..........
n) "f" per terminare il programma
dopo aver scelto "a" ad esempio mostri il messagio che ti chiede di inserire i parametri per gli automi, del tipo:
inserire ora (a, b, alfa) separati da uno spazio:
quindi uno inserisce i 3 dati e si ritorna al menu principale
è così che intendi ? |
| p2p |
no
intendo che i comandi devono essere inseriti ed eseguiti subito.non si deve stampare niente a parte esistePercorso che deve stampare o Si o NO e tortuosita' |
| mark |
allora intendi una sorta di interprete tipo:
c:\digita una comando:
che rimane attivo ed elabora al volo sino a quando gli passi il carattere 'f' |
| Skilotto83 |
ma ke problemi sono???
la scanf o quel cazzius ke avete usato legge direttamente i caratteri e li passa alla funzione che vi serve...quando mandi invio esegue la funzione...se la funzione stampa qlks allora bene, altrimenti nulla... |
| mark |
| ok, è tutto chiarito :) |
| Jacoposki |
sarà tutto chiarito... ma possibile che nessuno abbia bisogno di uno con cui lavorare, da prendere a calci e da cui farsi prendere a calci a mo' di sprone al lavoro?
Io da solo 'sto progetto non lo riesco a fare... insisto: nessuno nessuno nessuno al silab? ;( |
| elpampero |
A quanto ho capito siamo fermi tutti allo stesso punto.
Direi però di orientarci verso questi tre algoritmi:
Kruskal
Prim
Dijkstra
In particolare l'ultimo è per la determinazione dei cammini minimi.
Torelli aveva chiaramente detto "QUESTI TRE ALGORITMI NON SARANNO CHIESTI ALL'ORALE MA SARANNO UTILI PER IL PROGETTO"!!!!!!! |
| 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
per cui credo ke un modo di risolvere la questione sarebbe crearmi una matrice di valori ke mi rappresenta l'ideale rettangolo tra l'automa e la sorgente (con opportuni flag se la cella in questione è occupata) e tenere una variabile int tor in cui alla fine avrò la tortuosità minore di tutte
faccio un algoritmo di backtracking calcolando ricorsivamente TUTTI i percorsi possibili su quella matrice (tenendo conto in una variabile temp ad ogni passo della tortuosità che ho raggiunto nel cammino corrente fino a quella cella) e ogni volta ke arrivo nella cella della sorgente se tor è vuota (metterò un valore convenzionale tipo -1) oppure se temp<tor allora assegno a tor il valore di temp
e vado avanti fino alla fine, quando ho esaurito tutti i cammini tor conterrà il valore della tortuosità del cammino ottimale, anke se alla fine non ho la + pallida idea di quale sia questo cammino :)
lo so provare tutti i cammini possibili non è bello in termini di tempo, ma x ora questa è stata l'unica idea ke ho avuto x cui funziona la storia delle tortuosità, suggerimenti e consigli a proposito sono ovviamente ben accetti :) |
| fdecollibus |
| scusate ragazzi, una cosa un po' più bassa.... come si fa il valore assoluto in c? E se ho allocato dinamicamente un array, come faccio a sapere quando è finito? |
| holylaw |
prova a fare una cosa del genere:
valore_assoluto_di_x= (x<0) ? -x : x; |
| wingzero |
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. |
| Polsy |
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? |
| fdecollibus |
| Mercoledì 15-16 |
| wingzero |
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. |
| wingzero |
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. |
| Polsy |
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 |
| wingzero |
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. |
| Polsy |
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 |
| 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... |
| elpampero |
| Prima domanda: come lo costruiamo un grafo? |
| wingzero |
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. |
| p2p |
| 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. |
| 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 |
| p2p |
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'. |
| elpampero |
| Ok p2p! Cosa intendi però per punti doppi? Come lo costruiamo un grafo? |
| wingzero |
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. |
| 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! |
| wingzero |
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. |
| elpampero |
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 |
| wingzero |
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. |
| Polsy |
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 |
| 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.... |
| 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 |
| Polsy |
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 |
| Polsy |
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
) |
| p2p |
| Polsy, tu come stai implementando il tutto? con un grafo o altro? |
| virtual |
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. |
| Skilotto83 |
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... |
| Polsy |
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? |
| p2p |
| comunque per il grafo basterebbe crearne uno con le liste di adiacenza eliminando i punti occupati da ostacoli, e poi fare una passata di bfs, no?certo bisogna anche vedere, come diceva virtual di tener traccia dei cambi di direzione |
| p2p |
Originally posted by Polsy
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?
senti ma per riempire le liste di adiacenza, come fai? |
| elpampero |
| io direi di fare un ciclo per ogni nodo e in ogni nodo prendiamo il puntatore alla struttura nodo e ci mettiamo i nodi collegati |
| mark |
io di esistePercorso non ho capito cosa vuole
- ho le coordinate dell'automa
- mi vengono passate delle nuove coordinate più nome automa
da queste due, posso calcolarmi la distanza con la formula indicata nelle PDF
e mo che si fa ?
si prova a spostare l'automa della distanza D calcolata in tutte le direzioni possibili per vedere se non entra in collisione con nessun ostacolo ? |
| elpampero |
| Ti devi costruire un grafo con liste di adiacenza. Il grafo ha tanti nodi quanto sono i punti del rettangolo inscritto tra l'automa e i punti passati come parametro |
| mark |
Originally posted by elpampero
Ti devi costruire un grafo con liste di adiacenza. Il grafo ha tanti nodi quanto sono i punti del rettangolo inscritto tra l'automa e i punti passati come parametro
ok, ma il concetto è quello che ho espresso io ?
non mi interessa conoscere il metodo ma solo capire se dobbiamo vedere se l'automa può muoversi dal suo punto iniziale (xa,ya) al punto
D=|x0,y0|+|xa,ya|
senza entrare in collisione
grazie 1000 :) |
| nothingman7 |
| grazie polsy, non avevo capito che c'era da calcolare la distanza minima.. |
| nothingman7 |
altro dubbio...
nel testo il prof dice che se vogliamo inserire un ostacolo su un automa, NON COMPIE NESSUNA OPERAZIONE..
io mi chiedo..ma neanche una printf per avvertire l'utente??
strano..chi mette l'input dovrà pur sapere se l'inserimento dell'ostacolo ha avuto buon fine o no..
illuminatemi.. |
| mark |
Originally posted by nothingman7
altro dubbio...
nel testo il prof dice che se vogliamo inserire un ostacolo su un automa, NON COMPIE NESSUNA OPERAZIONE..
io mi chiedo..ma neanche una printf per avvertire l'utente??
strano..chi mette l'input dovrà pur sapere se l'inserimento dell'ostacolo ha avuto buon fine o no..
illuminatemi..
non è richiesta, quindi non mettere nulla |
| Jacoposki |
| Domani fiorentini riceve... io gli vado a parlare ma in realtà non so bene cosa chiedergli visto che finora ci ho capito ben poco. Dopo le 10 nel suo ufficio in Comelico, comunque. |
| mark |
riprovo, casomai qualche volenteroso ha voglia di rispondere a questo mio dubbio
Originally posted by mark
io di esistePercorso non ho capito cosa vuole
- ho le coordinate dell'automa
- mi vengono passate delle nuove coordinate più nome automa
da queste due, posso calcolarmi la distanza con la formula indicata nelle PDF
e mo che si fa ?
si prova a spostare l'automa della distanza D calcolata in tutte le direzioni possibili per vedere se non entra in collisione con nessun ostacolo ? |
| p2p |
| una volta fatte le liste di adiacenza e usato il bfs so se è raggiungibile con il percorso minimo la sorgente dal mio automa, e fin qui ok. ma per la totuosita'?? con l uso dei grafi e del bfs so solo se è raggiungibile ma non quale strada è stata fatta! idee?? suggerimenti? soldi?:) |
| mattcobain |
ragazzi, qualcuno è cosi gentile da accennarmi un minimo cosa siano le liste di adiacenza ed il bfs!?!?
le liste di adiacenza sarebbe delle liste concatenate!?!?
io mi sono perso...ho fatto tutto tranne segnale, esiste percorso e tortuosità perché non so dove sbattere la testa... |
| mark |
ok, mi sono risposto da solo
ora so cosa intende per distanza cammino minimo, tortuosità etc...
certo che siete pigri a rispondere :D |
| elpampero |
| le liste di adiacenza sono liste puntate in testa una cella di un array |
| mattcobain |
| grazie...si in effetti stupidamente non avevo neanche aperto il libro prima di chiedere...ho trovato tutto sul libro scusatemi...anche se ancora sto macinando per capire cosa fare |
| vlaste |
Originally posted by Jacoposki
ma possibile che nessuno abbia bisogno di uno con cui lavorare, da prendere a calci e da cui farsi prendere a calci a mo' di sprone al lavoro?
Io da solo 'sto progetto non lo riesco a fare... insisto: nessuno nessuno nessuno al silab? ;(
Raga, io sto cadendo nello sconforto, ho difficoltà anche col comando Crea, non so da dove cominciare, nonostante abbia seguito quasi tutto il corso e abbia fatto un anno di C alle superiori!!!
Un aiuto sarebbe gradito |
| Polsy |
Originally posted by vlaste
Raga, io sto cadendo nello sconforto, ho difficoltà anche col comando Crea, non so da dove cominciare, nonostante abbia seguito quasi tutto il corso e abbia fatto un anno di C alle superiori!!!
Un aiuto sarebbe gradito
hai pensato a delle strutture in cui organizzare gli automi e gli ostacoli? queste strutture avranno un puntatore all'inizio (root se è un albero, testa se è una lista, etc...), la funzione crea fa questo: se le strutture non sono ancora state create le crea inizializzando i puntatori, se sono già presenti dealloca la memoria occupata da esse (cioè cancella gli automi e gli ostacoli del campo precedente) lasciando solo i puntatori iniziali (ke rappresentano un nuovo campo vuoto)
nota come in tutto ciò non crei il campo, ma quello che sta dentro al campo :) |
| Skilotto83 |
Originally posted by Polsy
hai pensato a delle strutture in cui organizzare gli automi e gli ostacoli? queste strutture avranno un puntatore all'inizio (root se è un albero, testa se è una lista, etc...), la funzione crea fa questo: se le strutture non sono ancora state create le crea inizializzando i puntatori, se sono già presenti dealloca la memoria occupata da esse (cioè cancella gli automi e gli ostacoli del campo precedente) lasciando solo i puntatori iniziali (ke rappresentano un nuovo campo vuoto)
nota come in tutto ciò non crei il campo, ma quello che sta dentro al campo :)
in realta' fa solo la cancellazione dell'albero etc se chiamata....
perkè nn inizializza...
infatti nell'esempio parte subito con l'inserimento... |
| Skilotto83 |
ops...sbagliato....
skusa...
si'...inizializza le strutture di memorizzazione...
devo sistemarlo... |
| Jacoposki |
la funzione crea io l'ho fatta che crea due puntatori, come hai detto tu... uno a NodoRobot, l'altro a NodoOstacolo, e li inizializza a NULL. Non che sia sicuro che si possa fare... mi è sembrata la cosa più sensata, ma sto combattendo con errori di compilazione senza senso.
Oltre a non aver la benchè minima idea di come mettere giù esistePercorso e Tortuosità.... |
| mattcobain |
Originally posted by p2p
una volta fatte le liste di adiacenza e usato il bfs so se è raggiungibile con il percorso minimo la sorgente dal mio automa, e fin qui ok. ma per la totuosita'?? con l uso dei grafi e del bfs so solo se è raggiungibile ma non quale strada è stata fatta! idee?? suggerimenti? soldi?:)
scusami, ma in questo modo tu con le liste di adiacenza rappresenti tutti i nodi contenuti nel "rettangolo dei cammini minimi" avente come estremi opposti la sorgente e l'automa vero?!
fra i comandi del prof compare un "e -10000 6 11" e l'automa 11 si trova in (-3,6)....questo significa che la sorgente si trova nel punto (-10000,6), cioè "in linea" con l'automa, ma spostato piu a sinistra lungo le x di ben 9997 nodi (o celle/punti che dir si voglia)....quindi tu costruisci altrettanti nodi nella lista di adiacenza!?!?
e questo caso è "moderato" perché il rettangolo che collega sorgente-automa in realtà è solo un segmento, ma se fosse stato il famoso "rettangolo dei cammini minimi" figurati quanti altri nodi ci sarebbero stati in mezzo.....
cioè, tu stai andando avanti cosi!?....se ho capito male potresti spiegarmi un po come hai agito?!
ti ringrazio.....
io non capisco che dannazione fare!!!!! |
| elpampero |
| Sinceramente non vedo altro modo.... |
| mattcobain |
quindi come intende lui è quello che ho detto io!?!...cioè memorizza tutti i nodi contenuti fra la sorgente e l'automa!?.....ommioddio è una cosa troppo dispendiosa, anzi, troppo è dire poco (scusatemi il gioco di parole)....deve assolutamente esserci almeno un'altra soluzione decisamente più efficente!!!!
anche perché cosi facendo tutti i nodi compresi nel rettangolo fra l'automa e la sorgente vengono "memorizzati" nella/e liste di adiacenza, ma tutti quei nodi non hanno informazioni "utili" per noi....è uno spreco davvero vistoso di spazio, ed il caso che avevo citato dell'esempio del prof è anche abbastanza contenuto, e sono almeno 9997 nodi....figuriamoci se anziché essere sulla stessa ordinata i 2 elementi si fossero trovati in posti completamente opposti e molto distanti....
odddiooooooo :wall: |
| elpampero |
| OK. Chi si prende la briga di scrivere a Fiorentini? Ci darà una dritta o no? |
| Jacoposki |
sono passato stamattina da fiorentini.... oltre ad avermi fatto capire che non so una ceppa di C, che sono un coglione, che non ho speranze, che prima di fare il progetto devo affrontare i problemi elementari ecc ecc (simpatico come al solito, insomma), mi ha fatto capire che una soluzione possibile sarebbe l'uso di un algoritmo ricorsivo... vedo come è messa la sorgente rispetto al robot (esempio a destra in basso), allora mi muovo di uno a destra e di uno in basso e vedo se i punti che trovo sono validi, cioè non appartengono ad ostacoli. Se sono validi ripeto ricorsivamente il procedimento sui nuovi punti trovati. Se alla fine arrivo alla sorgente allora esiste un percorso minimo, se mi ritrovo a sbattere contro ostacoli o a uscire dal rettangolo automa-sorgente non esiste un percorso minimo.
Almeno è quanto posso capire io... ha fatto riferimento al capitolo sulla programmazione dinamica per ridurre il carico di lavoro evitando di calcolare più volte gli stessi percorsi.
Ovviamente scarse speranze di potere implementare questa cosa in modo sensato e in tempi ragionevoli... mai cercare di seguire C e Java contemporaneamente... sigh. |
| mattcobain |
Originally posted by Jacoposki
...vedo come è messa la sorgente rispetto al robot (esempio a destra in basso), allora mi muovo di uno a destra e di uno in basso e vedo se i punti che trovo sono validi, cioè non appartengono ad ostacoli. Se sono validi ripeto ricorsivamente il procedimento sui nuovi punti trovati....
ma scusa in questo modo ad ogni passo aumenti di uno la tortuosità....non mi sembra molto furba come cosa....ma ha detto così il prof!?!?!? :? |
| mattcobain |
Originally posted by Jacoposki
...mai cercare di seguire C e Java contemporaneamente...
Off-Topic:
hai troppa ragione!
|
| Jacoposki |
Originally posted by mattcobain
ma scusa in questo modo ad ogni passo aumenti di uno la tortuosità....non mi sembra molto furba come cosa....ma ha detto così il prof!?!?!? :?
dovrebbe essere solo per verificare l'esistenza del percorso... la tortuosità non so se può venire calcolata insieme o se verrà calcolata a parte in un altro modo.
Più che altro mi preoccupa lo spazio e il tempo che si rischia di dover gestire in questo modo, ma mi pare che a buon senso dovrebbe funzionare. Ripeto che non lo so implementare, in questo momento, ma a muzzo mi pare che sia sensata, come cosa. |
| lino |
| qualcuno è riuscito ad implementate tortuosità? |
| wingzero |
Originally posted by mattcobain
scusami, ma in questo modo tu con le liste di adiacenza rappresenti tutti i nodi contenuti nel "rettangolo dei cammini minimi" avente come estremi opposti la sorgente e l'automa vero?!
fra i comandi del prof compare un "e -10000 6 11" e l'automa 11 si trova in (-3,6)....questo significa che la sorgente si trova nel punto (-10000,6), cioè "in linea" con l'automa, ma spostato piu a sinistra lungo le x di ben 9997 nodi (o celle/punti che dir si voglia)....quindi tu costruisci altrettanti nodi nella lista di adiacenza!?!?
e questo caso è "moderato" perché il rettangolo che collega sorgente-automa in realtà è solo un segmento, ma se fosse stato il famoso "rettangolo dei cammini minimi" figurati quanti altri nodi ci sarebbero stati in mezzo.....
cioè, tu stai andando avanti cosi!?....se ho capito male potresti spiegarmi un po come hai agito?!
ti ringrazio.....
io non capisco che dannazione fare!!!!!
Sull'input di esempio c'è il comando per calcolo tortuosità , coordinate 1000,2000 per automa 01 (che è su x=8,y=-4). Sono la bellezza di 992*1996 celle di rettangolo da scansionare. Neanche ho provato a simulare l'input su carta per vedere esattamente dove sono gli ostacoli, tuttavia gli algoritmi devono funzionare anche in casi estremi con decine di ostacoli sovrapposti nell'area...
Il tempo rimasto è veramente poco per trovare una soluzione valida ed anche per provare a programmarne una alla meno peggio. |
| Skilotto83 |
mi sorge un dubbio...
Io ho utilizzato le liste per fare l'inserimento degli automi, e presumibilmente(anche se ho semi-pronta una versione ad albero)vorrei usare una lista anche per gli ostacoli....
Il problema è ke per una serie di motivi...abbastanza lungo da spiegare..io la lista non la creo allocando ogni volta lo spazio di una strutture e poi muovendo i puntatori...
Ma creando un array di dimensione fissa contenente per ogni cella la struttura automa(e quindi alloco tutto lo spazio subito, tanto lo so quant'è)..poi assegnando valori di testa e coda all'array la gestisco come se fosse una lista....e nel caso ci fosse bisogno alloca nuovo spazio automatikamente....
Dite ke c'è qualke problema??
semplicemente nn uso pratikamente nulla delle strutture viste a lezione..o almeno uso le liste ma non come intende lui...visto ke nn sono di dimensione infinita.... |
| elpampero |
| Scusa lino ma sei riuscito a implementare esistePercorso()?? |
| mattcobain |
Originally posted by Skilotto83
mi sorge un dubbio...
Io ho utilizzato le liste per fare l'inserimento degli automi, e presumibilmente(anche se ho semi-pronta una versione ad albero)vorrei usare una lista anche per gli ostacoli....
Il problema è ke per una serie di motivi...abbastanza lungo da spiegare..io la lista non la creo allocando ogni volta lo spazio di una strutture e poi muovendo i puntatori...
Ma creando un array di dimensione fissa contenente per ogni cella la struttura automa(e quindi alloco tutto lo spazio subito, tanto lo so quant'è)..poi assegnando valori di testa e coda all'array la gestisco come se fosse una lista....e nel caso ci fosse bisogno alloca nuovo spazio automatikamente....
Dite ke c'è qualke problema??
semplicemente nn uso pratikamente nulla delle strutture viste a lezione..o almeno uso le liste ma non come intende lui...visto ke nn sono di dimensione infinita....
secondo me non è una cosa molto saggia implementare una lista con un array....cmq oramai secondo me è gia tanto se si riesce a fare il progetto funzionante....quindi il fine giustifica i mezzi, fai come pensi/trovi meglio, l'importante è che alla fine funzioni!!!!
ma una cosa mi ha lasciato perplesso:
... creando un array di dimensione fissa contenente per ogni cella la struttura automa(e quindi alloco tutto lo spazio subito, tanto lo so quant'è)...
tu dici di sapere quanto è lo spazio da allocare....ma scusa come fai a saperlo!?!? a priori non sai quanti automi ci saranno nel piano!!!! |
| Novalis |
(non ho letto le pagine centrali del thread, perdonate eventuali scoperte dell'acqua calda:D)
Nessuno ha pensato di utilizzare gli alberi di ricerca per gli ostacoli?
Pensavo di utilizzare il valore di ascissa come chiave, ordinare gli elementi in base a questo, e inserire come dato satellite il valore di ordinata.
Una volta individuato il "rettangolo di cammino", possiamo eliminare immediatamente gli ostacoli che non ne fanno parte semplicemente non considerando i sottoalberi che non contengono chiavi comprese tra i due estremi del rettangolo di cammino.
In questo modo, teniamo traccia di tutte le caselle occupate. Quello che non fa parte della nostra "lista nera", è libero e percorribile.
Lo stesso discorso vale per gli automi... un albero di ricerca (e possono essere inseriti in una sola posizione) ci consente di individuare quelli sensibili al richiamo perchè, una volta percorso l'albero seguendo la stringa del messaggio, tutti gli automi presenti nel sottoalbero sono candidati a raggiungere la sorgente.
Ho detto qualcosa di sensato, o avevate già vagliato e scartato l'ipotesi?:) |
|
|
|
|
