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

[Algoritmi] Progetto "RICHIAMI"

E' in uscita il nuovo progetto di algoritmi valido per l'appello dell'8 Febbraio 2005. In bocca al lupo

Vengono dati 3 giorni in meno rispetto all'appello di Gennaio a quanto sembra
Il che fa 15gg invece di 18gg disponibili.

Sì, ho notato anch'io. Speriamo almeno sia più semplice :-)

Originally posted by elpampero
Sì, ho notato anch'io. Speriamo almeno sia più semplice :-)

Da una prima lettura non sembra più semplice, anzi il calcolo delle tortuosità non mi sembra banale. Però vedremo! ciao

e infatti anche a me nn sembra piu' semplice..direi che è kome il precedente ma on in piu' il calcolo della tortuosita'..che deve essere un bel macello...
speriamo...ora si vedra'...

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

io mi kiedo poi con quale fottutissima logica decida di dare 4 giorni in meno per un progetto che è molto piu' difficile del precedente...

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

Già, perchè 4 giorni in meno? Perchè diavolo darci 4 giorni in meno?

progetto facile, vedo... esistePercorso e tortuosità già mi mettono in difficoltà al solo pensiero...

ma più che altro davvero si aspettano che nel modo in cui abbiamo fatto il C a lezione noi si sia in grado di fare un progetto del genere? bah.

__________________
Mai sottovalutare l'ampiezza di banda di una station wagon piena di nastri lanciata a tutta velocità lungo l'autostrada. - Andrew S. Tanenbaum - Reti di Calcolatori

tra l'altro, cominciamo bene... qualcuno si ricorda le operazioni per far funzionare gcc?

C'era un "gocs - qualcosa" da mettere da qualche parte nel prompt... non ricordo il "qualcosa" e dove andava scritto... nella cartella che contiene il codice? in C:\? Da qualsiasi parte? Nella cartella del compilatore? 'iuto!

__________________
Mai sottovalutare l'ampiezza di banda di una station wagon piena di nastri lanciata a tutta velocità lungo l'autostrada. - Andrew S. Tanenbaum - Reti di Calcolatori

Gli automi come li organizzate? io direi in un albero binario di ricerca...

Come lo creiamo un piano?

il piano direi che è l'ultima cosa da fare nel senso che crei una struttura che contiene gli automi e gii ostacoli e tutto cio che serve. La funzione crea praticamente svuota tutto il contenuto delle strutture ottenendo quindi un "piano" vuoto.

Una domanda: come mai all'istruzione e -10000 6 11 da come output SI ?

Ho capito, pensavo la stringa -10000 fossa la stringa binaria. (che pirla)

Ciao

Perchè esiste un percorso libero che l'automa P(11) puo' fare verso il punto(-10000,6)

Gli automi li gestisci con un albero binario di ricerca?

io pensavo semplicemente di metterli in una lista, così come gli ostacoli. Non sarà la cosa più efficiente ma sicuramente da implementare è molto semplice.

bisogna fare attenzione anche al nome dell'automa e al segnale. il testo dice che è una stringa finita ma non dice che è anche limitata superiormente. Con questo voglio dire che non si può memorizzare in un semplice array anche se molto grande. O no?

Non puoi metterla in un array perchè non sai a priori quanto è grande l'array..devi per forza allocare memoria dinamica...Io comunque metto gli automi in un albero. E' più difficile da implementare ma è sicuramente più efficiente

Ok allora uso la realloc per l'input, metto gli automi in una lista, gli ostacoli in un' altra lista. Fin qui ok, ora devo capire come calcolare la tortuosità.

Scusate, qualcuno sa se per il progetto c'e' bisogno di iscriversi al sifa (per il fatto dei registri elettronici)?

__________________
"Io odio questo posto,questo zoo,questa prigione,questa..realtà o come diavolo la chiamate voi,la odio non la sopporto più...l'odore soprattutto"
(Agente Smith, "Matrix")

Sì, bisogna iscriversi una settimana prima dell'uscita del progetto

cavolo..ma la storia della tortuosita' è allucinante...
in pratica dalla posizione in cui è l'automa deve fare tutte le possibili combinazioni di movimenti..perchè per evitare l'ostacolo potrebbe dover fare 50 volte a zig zag....
e ogni tentativo che ha successo(cioè l'automa ariva a destinazione senza aver trovato ostacoli)deve essere memorizzato con il num di cambi di direzione(tortuosita')in modo da poter poi scegliere il percorso con minor cambi...
senza dimenticare che prima di tutto cio' deve aver scelto di muovere solo gli automi a distanza minima dalla destinazione...quindi bisogna tener traccia di tutte le distanze di tutti gli automi dalla destinazione...per poi scegliere solo quelli con distanza minore...
La vedo dura....

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

MSN andrea.poretti(at)hotmail.it

Originally posted by Skilotto83
io mi kiedo poi con quale fottutissima logica decida di dare 4 giorni in meno per un progetto che è molto piu' difficile del precedente...

Originally posted by mitnik
io pensavo semplicemente di metterli in una lista, così come gli ostacoli. Non sarà la cosa più efficiente ma sicuramente da implementare è molto semplice.

__________________
Non ti perdere di coraggio se ti tocca lavorare molto e raccogliere poco.....

Beh il main è la cosa piu' facile da fare, voi costruite un albero binario di ricerca?Secondo me è la cosa piu efficiente... 2 strutture per automa ed ostacolo.

scusate la domanda, ma, continuo a vedere proposte relative ad alberi di ricerca binari, ma ancora non riesco a capire quale sia la chave che vorreste usare per l'ordinamento del nodo: il nome comvertito in decimale? tenuto in binario? e se gli automi sono solo due: 01, 0000000001???

Scusate, ma nel testo viene specificato che un passo unitario orizzontale è un segmento della forma {(x,y0) | x0 <= x <= xo + 1}, così come un passo unitario verticale è un segmento della forma {(x0,y) | y0 <= y <= yo + 1}, e che un percorso è una successione di tali movimenti. Dalla forma, intuisco che siano ammessi solo spostamenti nel senso positivo delle ascisse e delle ordinate (ossia spostamenti "verso l'alto" e "verso destra"). Come è possibile che l'automa 11 dell'esempio possa raggiungere la sorgente spostandosi nel verso negativo delle ordinate?

Originally posted by ZeroByte
Scusate, ma nel testo viene specificato che un passo unitario orizzontale è un segmento della forma {(x,y0) | x0 <= x <= xo + 1}, così come un passo unitario verticale è un segmento della forma {(x0,y) | y0 <= y <= yo + 1}, e che un percorso è una successione di tali movimenti. Dalla forma, intuisco che siano ammessi solo spostamenti nel senso positivo delle ascisse e delle ordinate (ossia spostamenti "verso l'alto" e "verso destra"). Come è possibile che l'automa 11 dell'esempio possa raggiungere la sorgente spostandosi nel verso negativo delle ordinate?

si possono muovere solo in positivo...altrimenti nn vedo dove sia il problema per raggiungere una destinazione..basterebbe girare intorno a tutti gli ostacoli...

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

comunque a proposito del nome dell' automa anch io avevo pensato all' uso della realloc e effettivamente funziona, pero' agli orali scorsi Fiorentini aveva detto che questa soluzione non gli paceva molto e che preferiva usare getchar e scanf in un ciclo.
Pero' se funziona,amen, al limite mi dira' che avrei potuto fare diversamente.

Bhè ma se fosse come dite voi allora gli automi 10 11 100 101 si sposterebbero tutti in senso negativo. O sbaglio? Il problema di aggirare gli ostacoli è dato dal fatto che gli automi devono fare un percorso pari alla distanza minima. Gli automi considerati hanno infatti distanza 8 e 9 dal punto x e nei percorsi che poi vengono considerati rispettano tale distanza. Invece l'automa 110 ad esempio ha distanza minima 8. Per arrivare a x pero' deve aggirare l'ostacolo prima spostandosi in alto di uno (+1) successivamente a sinistra di 8 (+8) e poi in giu' di 1....va a finire che il percorso che deve fare è lungo 10 caselle...>8 e quindi non puo' spostarsi
io lo intendo cosi'

Originally posted by superfabius
Bhè ma se fosse come dite voi allora gli automi 10 11 100 101 si sposterebbero tutti in senso negativo. O sbaglio? Il problema di aggirare gli ostacoli è dato dal fatto che gli automi devono fare un percorso pari alla distanza minima. Gli automi considerati hanno infatti distanza 8 e 9 dal punto x e nei percorsi che poi vengono considerati rispettano tale distanza. Invece l'automa 110 ad esempio ha distanza minima 8. Per arrivare a x pero' deve aggirare l'ostacolo prima spostandosi in alto di uno (+1) successivamente a sinistra di 8 (+8) e poi in giu' di 1....va a finire che il percorso che deve fare è lungo 10 caselle...>8 e quindi non puo' spostarsi
io lo intendo cosi'

Per P2P. Non ti seguo molto sul nome dell'automa...Cosa centra il ciclo?

Intendi un ciclo while con all'interno uno switch-case?

Originally posted by elpampero
Per P2P. Non ti seguo molto sul nome dell'automa...Cosa centra il ciclo?

ah ok...Direi poero' che più che per l'intero va fatto per il char...

Mi sta venendo un altro dubbio: il nome dell'automa lo trattate come intero o come una stringa. Nel caso dell'intero diventa tutto più semplice anche per la creazione della struttura

Mi sta venendo un altro dubbio: il nome dell'automa lo trattate come intero o come una stringa. Nel caso dell'intero diventa tutto più semplice anche per la creazione della struttura

come stringa, io uso un *char per memorizzarlo

Perfetto, anch'io uso char* ma nella lettura dello standard input non mi trovo....

scusate ma cosa vuol dire nella prima pagina, qunado dice che un percorso è una successione di passi p1...pk tali che pi η pi+1 contiene un solo punto??
che cè un solo punto tra un passo e l altro?

E' un modo complicato per dire che quando esegui più passi il punto finale del passo precedente è il punto iniziale del successivo. Cioè sono passi unitari consecutivi

E' una brutta gatta da pelare questa tortuosità.

Beati voi che vi preoccupate della tortuosità io sono in difficoltà con lo standard input

idee per il calcolo del percorso libero?? che è qui il cuore di tutto...

Originally posted by p2p
idee per il calcolo del percorso libero?? che è qui il cuore di tutto...

Scusate l'insistenza, ma... se usarte un albero binario di ricerca per memorizzare gli automi, quale chiave utilizzate???

Io ho risolto con la realloc anche se prima si diceva che fiorenti non l'ha apprezzata, ma sinceramnete creare una lista per contenere un nome di un automa non mi va.

gli ostacoli li metto in una lista

il segnale lo leggo sempre con la realloc.

la funzione posizione è abbastanza semplice.

esistePercorso e tortuosità mi fanno diventare matto; voi avete qualche idea a proposito?

La chiave dei nodi dell'albero di ricerca è il nome

concordo.. anche se non gli piace funziona quindi io uso realloc (ho fatto una funzione apposita che richiamo ogni volta che devo leggere il nome di un automa, quindi la uso anche per la stampa dei prefissi, per esempio)
strutture: uso un RB-Albero per gli automi perchè è bilanciato... ma soprattutto, anche qui, xchè lo avevo gia' pronto dallo scorso progetto, altrimenti avrei usato un normalissmo albero di ricerca... anche se si puo' sbilanciare una cifra... amen;
uso una lista per gli ostacoli .
per il movimento sto cercando di pensare a qualcosa...

ragazzi...una domanda....
io alloco memoria per un puntatore ad una struttura...inizializzo i campi di questa struttura....poi per vedere se funziona li ho stampati a video....e si vede tutto come dovrebbe essere
poi ho usato free per deallocare lo spazio puntato dal puntatore che avevo creato....ho riprovato ad accedere ai campi della struttura che prima era puntata da tale puntatore, e non so perché ma riesco ancora ad accedervi, sia per modificarli, sia per visualizzarli!!!
è normale!?!?
cioè, se uso free quel puntatore non dovrebbe perdere la traccia della struttura che li ho fatto puntare?!!?
mah....la vedo sempre piu grigia!!!

Originally posted by mitnik


esistePercorso e tortuosità mi fanno diventare matto; voi avete qualche idea a proposito?

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

MSN andrea.poretti(at)hotmail.it

Originally posted by Skilotto83
premettendo che secondo me non si diskute sul fatto che l'automa si possa muovere solo in positivo...e quindi le ascisse e le ordinate possono solo aumentare(come si vede dal testo dove spiega che x è compreso tra x0 e x0+1)....

ma allora perchè il 110 e il 111 nn possono ragg X???basta che salgono di un tot, vanno a sx e riscendono...
e perkè 1 nn puo'??? basta che ci gira attorno!!!....nn ha senso!!!!!!

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

io nn posso calcolare tutte i possibili percorsi anche per aggirare l'ostacolo.....
Altrimenti diventa un massacro!

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

MSN andrea.poretti(at)hotmail.it

Originally posted by Skilotto83
io nn posso calcolare tutte i possibili percorsi anche per aggirare l'ostacolo.....
Altrimenti diventa un massacro!

Originally posted by Skilotto83
ma allora perchè il 110 e il 111 nn possono ragg X???basta che salgono di un tot, vanno a sx e riscendono...
e perkè 1 nn puo'??? basta che ci gira attorno!!!....nn ha senso!!!!!!

Originally posted by Polsy
per intenderci, immagina di tracciare un rettangolo ke ha come vertici l'automa e la sorgente, il cammino non deve uscire da quel rettangolo

__________________
Mai sottovalutare l'ampiezza di banda di una station wagon piena di nastri lanciata a tutta velocità lungo l'autostrada. - Andrew S. Tanenbaum - Reti di Calcolatori

infatti l'avevo capito anhe io circa 10min fa...
il pecorso è quello del rettangolo inscitto tra i due vertici che sono dest e pos automa...
ora basta che riesko a dimostrare analitikamente un'ideuzza che ho per la tortuosita' e sono a cavallo...

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

MSN andrea.poretti(at)hotmail.it

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

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

MSN andrea.poretti(at)hotmail.it

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

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

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

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

MSN andrea.poretti(at)hotmail.it

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

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

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

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

MSN andrea.poretti(at)hotmail.it

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

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

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

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

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

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

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

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

Cosa ne pensate???

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

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

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

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

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

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

la lunghezza del nome....

Ho un problemino con la struct per memorizzare gli automi. Come me lo dichiaro il campo contente il nome? Per ora ho messo un bel char nome[100], ma non va proprio benone eh... se uso un bel char *nome potrebbe andare? Ho paura che mi faccia casino quando alloco dello spazio per aggiungere un'altro automa...

Re: la lunghezza del nome....

Originally posted by faxmaister
Ho un problemino con la struct per memorizzare gli automi. Come me lo dichiaro il campo contente il nome? Per ora ho messo un bel char nome[100], ma non va proprio benone eh... se uso un bel char *nome potrebbe andare? Ho paura che mi faccia casino quando alloco dello spazio per aggiungere un'altro automa...

__________________
{¯`·._)-•°o.O`·._.·´¯`•¸·´¯).·´¯`·-> IN DA EEKS <-·´¯`·.(¯`·¸•´¯`·._.·´O.o°•–(¯`·._}

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

Cosa ne pensate???

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

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

grafo da 300 nodi

Ma se non conviene usare un grafo, ne quindi una matrice 10x30, come fate seguire e provare i possibili cammini tra due punti??? se avete suggerimenti sono MOLTO ben accetti!!!

io ci sto pensando da un kasino..
il problema è ke per una ricerca esaustiva bisogna per forza controllare tutte le posizioni del rettangolo che ha vertici in posiz automa e sorgente....è l'uniko modo....
Pero' è un kasino....
se contiamo 10msec per ogni ricerca di nodo se il rettangolo ha lato 1000 x 1000 sono 1000000 di celle...a voi il calcolo di quanto ci vuole per visitare tutte le celle....
l'uniko vantaggio è ke una volta che ho un percorso con tortuosita' 0 o 1 posso fermarmi perkè menoi di cosi' nn si puo' fare...

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

MSN andrea.poretti(at)hotmail.it

Originally posted by maurozaninelli
Ma se non conviene usare un grafo, ne quindi una matrice 10x30, come fate seguire e provare i possibili cammini tra due punti??? se avete suggerimenti sono MOLTO ben accetti!!!

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

MSN andrea.poretti(at)hotmail.it

Originally posted by Skilotto83
sono una cifra di for innestati...come un puntatore che si sposta in tutte le posizioni possibili...

scusate, qualcuno è riuscito ad implementare l' idea dei grafi?
come fate a capire quali archi inserire nel grafo?
forse potrei inserire tutti gli archi possibili tra sorgente e automa eliminando i punti coperti da ostacoli.. giusto? pero' come?

Forse dico una stupidata.... ma se si facesse backtrack?

Originally posted by virtual
Forse dico una stupidata.... ma se si facesse backtrack?

è un po lunghina da spiegare, comunque è l'algoritmo delle mosse del cavallo che ha spiegato a lezione(lo trovi sulle slide).
Praticamente usi una funzione ricorsiva che ogni volta che incontra un ostacolo torna indietro di uno e cambia direzione.
Sto provando a farla... per ora è ancora in fase embrionale ma credo che l'idea ci sia....

Originally posted by virtual
è un po lunghina da spiegare, comunque è l'algoritmo delle mosse del cavallo che ha spiegato a lezione(lo trovi sulle slide).
Praticamente usi una funzione ricorsiva che ogni volta che incontra un ostacolo torna indietro di uno e cambia direzione.
Sto provando a farla... per ora è ancora in fase embrionale ma credo che l'idea ci sia....

Lo trovi sulle slide di aguzzoli, pagina 206 del file lucidi04.pdf
Se ci arrivi prima di me fammi un fischio n'è!

..... :-)

Sto portando avanti anch'io l'idea backtracking. Per adesso sono ancora in fase di adattamento. Comunque dovrebbe essere quella.
Granito.

Originally posted by elpampero
La chiave dei nodi dell'albero di ricerca è il nome

Originally posted by vlaste
Ma se il nome è memorizzato in un char*, come si comparano due nomi al fine di posizionarli correttamente nell'albero??

Re: Re: la lunghezza del nome....

Originally posted by luca8684
No facendo come hai fatto tu non va bene perchè non sai quanto è grossa la stinga del nome dell'automa!! Devi utilizzare il puntatore così puoi allocare quanta memoria vuoi dinamicamente.
Quindi usa char *nome!!

__________________
Non ti perdere di coraggio se ti tocca lavorare molto e raccogliere poco.....

in parole povere il nome puo' essere una sequenza di 1 o 0 lunga quanto si vuole.

puo' essere 1
oppure 0
oppure 10101001010100000010110010101010101010101010000001
1
oppure 11111111111111111111111111111111111111111111
........
capito?

Re: Re: Re: la lunghezza del nome....

Originally posted by mark
ma allora cosa intende con:

Ogni automa è identificato univocamente da un nome , che è una stringa finita sull'alfabeto {0,1}

io ho interpretato che i possibili nomi siano

00
01
10
11

__________________
{¯`·._)-•°o.O`·._.·´¯`•¸·´¯).·´¯`·-> IN DA EEKS <-·´¯`·.(¯`·¸•´¯`·._.·´O.o°•–(¯`·._}

Mi hai anticipato!!

__________________
{¯`·._)-•°o.O`·._.·´¯`•¸·´¯).·´¯`·-> IN DA EEKS <-·´¯`·.(¯`·¸•´¯`·._.·´O.o°•–(¯`·._}

Originally posted by p2p
in parole povere il nome puo' essere una sequenza di 1 o 0 lunga quanto si vuole.

puo' essere 1
oppure 0
oppure 10101001010100000010110010101010101010101010000001
1
oppure 11111111111111111111111111111111111111111111
........
capito?

__________________
Non ti perdere di coraggio se ti tocca lavorare molto e raccogliere poco.....

a questa stregua, quando si legge una stringa dal file, è meglio allocare un buffer dinamicamente per ogni parametro, o no ?

__________________
Non ti perdere di coraggio se ti tocca lavorare molto e raccogliere poco.....

Originally posted by mark
a questa stregua, quando si legge una stringa dal file, è meglio allocare un buffer dinamicamente per ogni parametro, o no ?

Originally posted by p2p
quale file? devi leggere da tastiera...

__________________
Non ti perdere di coraggio se ti tocca lavorare molto e raccogliere poco.....

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

__________________
{¯`·._)-•°o.O`·._.·´¯`•¸·´¯).·´¯`·-> IN DA EEKS <-·´¯`·.(¯`·¸•´¯`·._.·´O.o°•–(¯`·._}

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

__________________
Non ti perdere di coraggio se ti tocca lavorare molto e raccogliere poco.....

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

__________________
Statistica non è un esame, ma un accanimento terapeutico...staccatemi la spina!!!

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 ?

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

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

__________________
Mai sottovalutare l'ampiezza di banda di una station wagon piena di nastri lanciata a tutta velocità lungo l'autostrada. - Andrew S. Tanenbaum - Reti di Calcolatori

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'

backtracking, dfs?!?!
....ma fiorentini quando mai ha pronunciato (non dico nemmeno spiegato) queste cose!?!?!?

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

Originally posted by mattcobain
backtracking, dfs?!?!
....ma fiorentini quando mai ha pronunciato (non dico nemmeno spiegato) queste cose!?!?!?

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

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

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? <;-(

__________________
Mai sottovalutare l'ampiezza di banda di una station wagon piena di nastri lanciata a tutta velocità lungo l'autostrada. - Andrew S. Tanenbaum - Reti di Calcolatori

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? <;-(

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?

__________________
{¯`·._)-•°o.O`·._.·´¯`•¸·´¯).·´¯`·-> IN DA EEKS <-·´¯`·.(¯`·¸•´¯`·._.·´O.o°•–(¯`·._}

mi spiegate cosa intende con l'output


SI
4
NO
-1
etc.. ?

grazie 1000

__________________
Non ti perdere di coraggio se ti tocca lavorare molto e raccogliere poco.....

pardon, trovato; mi era sfuggito

__________________
Non ti perdere di coraggio se ti tocca lavorare molto e raccogliere poco.....

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.

__________________
Mai sottovalutare l'ampiezza di banda di una station wagon piena di nastri lanciata a tutta velocità lungo l'autostrada. - Andrew S. Tanenbaum - Reti di Calcolatori

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' ??

__________________
Non ti perdere di coraggio se ti tocca lavorare molto e raccogliere poco.....

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' ??

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

__________________
Non ti perdere di coraggio se ti tocca lavorare molto e raccogliere poco.....

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

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;

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

__________________
Non ti perdere di coraggio se ti tocca lavorare molto e raccogliere poco.....

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

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?

__________________
Non ti perdere di coraggio se ti tocca lavorare molto e raccogliere poco.....

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'

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'

__________________
Non ti perdere di coraggio se ti tocca lavorare molto e raccogliere poco.....

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

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

ok, è tutto chiarito

__________________
Non ti perdere di coraggio se ti tocca lavorare molto e raccogliere poco.....

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? ;(

__________________
Mai sottovalutare l'ampiezza di banda di una station wagon piena di nastri lanciata a tutta velocità lungo l'autostrada. - Andrew S. Tanenbaum - Reti di Calcolatori

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

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

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?

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.

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

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

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.

Mercoledì 15-16

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)

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

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.

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

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

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

Prima domanda: come lo costruiamo un grafo?

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

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.

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

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