piccola sfida

[angelica]

sono sinceramente meravigliata!

a2000...30 righe...

io non mi ci sono messa, ché ho ripreso il C da pochi giorni, e tra un po' sotto col C++!

ma...sono sicura che qualcuno qui riuscirà a tirar fuori un proggie scritto in C/C++ bello efficiente!
su ragazzi, sono con voi!

@a2000: complimenti! davvero!
io la teoria dei grafi l'ho studiata nell'esame di RicercaOperativa...ma non ricordo molto!

[a2000]

grazie delle belle parole angy !

ma sono già impegnato con monky !

(ancora per poco, però)

[NA01]

primo tentativo fallito
troppi 3d, il sistema non ha retto nemmeno in modalità console
modificarlo per farlo andare non sarebbe un problema, ma non capisco come adottare la via che mi sembra che tu abbia imboccato.
il mio programma (per ora non fà niente, ma ho già in mente le modifiche del caso per alleggerire il tutto) calcola tutte le combinazioni possibili (non tutte le strade, ma tutte le soluzioni possibli) e le segue fino in fondo arrivando a tantissime soluzioni.

non ho la più pallida idea di come far scegliere una strada che deve per forza essere giusta

chiedo l'aiuto da casa
conoscevi a priori il metodo da adottare (cioè: lo sapevi fare anche su carta)?

cmq ora continuo a provare a calcolare tute le combinazioni possibili, poi volgio però anche riuscire a far arrivare il pc a 1 SOLA soluzione, non a tutte.

ciao

[a2000]

calcolare tutte le combinazioni (cammini) possibili è ... impossibile

ossia mooolto oneroso e praticamente impossibile con il crescere del numero di elementi della matrice.

in questa ottica è meglio costruire il grafo del gioco, ossia assegnare ad ogni cella un nodo e collegarlo con quelle connesse secondo le regole di spostamento assegnate.
una volta costruito il grafo si applica un algoritmo standard di cammino minimo ..... ma non sono 30 righe

l'altra strada è (ma forse è la stessa ... ):

devi visitare tutte le città d'Italia una sola volta,
ti trovi a Bologna e sai che Firenze ha 8 vie d'accesso residue, Verona 5, Modena 4, Imola 2
quale visiti ?

[a2000]

siccome l'ottimo è nemico del bene, il quale sta in mezzo, le risposte possibili sono 2: o Firenze o Imola.

a te la scelta.

[a2000]

che devi fare !

non mi partire ancora col percorso binario invece che ottenario !

[bsummer]

Originariamente inviato da a2000
non potete spazzolare tutte le possibilità di spostamento a n passi (magari con le ricursive che vi piacciono tanto): dovete determinare un criterio semplice con cui scegliere tra i vari spostamenti possibili.

Ah, io credevo che si stesse giocando a chi lo fa più corto

altra strada, esaustiva ma costosa, è quella del cammino minimo sul grafo di stato.

Ricerca operativa è un esame che ho dato anch'io
Tuttavia non mi sentirei di definire il problema come uno di "cammino minimo". Ma forse mi sbaglio, è passato un po' di tempo...

Aloha!

[bsummer]

[b]
l'altra strada è (ma forse è la stessa ... ):

devi visitare tutte le città d'Italia una sola volta,
ti trovi a Bologna e sai che Firenze ha 8 vie d'accesso residue, Verona 5, Modena 4, Imola 2
quale visiti ?

Esatto... lo vedo di più come la ricerca di un algoritmo di copertura minimo con in più l'imposizione che un nodo può avere al massimo una solo uscita (una sola entrata è implicita in quanto l'albero è di copertura minima, fatta eccezione per la radice che non ha entrate).

Personalmente andrei a Imola...è meno probabile che andando avanti trovi altre strade che mi portino là.

Aloha!

[cionci]

Originariamente inviato da a2000
ecco qui le prime cento righe degli spostamenti della 1000x1000 (in 1 secondo):


Legenda:
1 = E
2 = NE
3 = N
4 = NW
5 = W
6 = SW
7 = S
8 = SE

Azzz.non avevo pensato a memorizzare solamente gli spostamenti...

[lombardp]

Originariamente inviato da a2000
confermo le 30 righe di codice

250 x 250 in 0.07 secondi, 1000 x 1000 in 1.1 s, 10000 x 10000 in 112 s.
non ottimizzato.

questa è una 250x250 in 0.07 s

Domani ti mando il mio programmino... conto di eguagliare almeno le 30 righe... per la velocità non so.

[a2000]

OK, ti abbuono anche le graffe !

[Strat]

Da quello che ho capito si usa il metodo del cammino ottimale, o meglio l'idea deriva da questo,o mi sbaglio gia?

Cioè prendo un nodo di partenza e percorro l'arco con peso minore, in questo caso il peso è il numero di scelte che ho nel caso successivo.

La mia domanda è quando si deve scegliere fra due archi dello stesso peso si guardano i due passi successivi o si va a caso e se si sbaglia si torna indietro?

PS.: Per la prima volta l'ho risolto su carta anche se non in questo modo. ( un po' a caso....)

Ciao

[a2000]

Originariamente inviato da Strat
...

La mia domanda è quando si deve scegliere fra due archi dello stesso peso si guardano i due passi successivi o si va a caso e se si sbaglia si torna indietro?
....

sì:

"quando si deve scegliere fra due archi dello stesso peso si guarda fino a un numero determinato (*) di passi successivi"

(*) anche 0.

[angelica]

non riesco a tirar fuori l'algoritmo...qualcuno di voi potrebbe passarlo?
greedy, backtracking o cosa?

un'altra cosa che mi viene un po' ostica da immaginare è la struttura dei nodi e delle liste di nodi...

in un semplice grafo orientato etichettato mi sono immaginata una struttura del genere:

typedef struct {
int etichetta;
listanodi *adiacente;
nodo *prossimo;
} nodo;

typedef struct {
nodo *nodo;
listanodi *prossimo;
} listanodi;

ma questa potrebbe andare per una situescion simile:


nel nostro caso non ho una lista data...la devo comporre; può essere pari al prodotto righe*colonne; ogni nodo può puntare fino a 8 diversi nodi, l'etichetta è la posizione sulla scacchiera...

azz, un vero casino...
scommetto che mi sto inutilmente scervellando, perché il problema può essere risolto altrimenti...o sbaglio?
certo, avere una struttura "su carta" sulla quale lavorare, sarebbe meglio...
qualcuno di voi c'è arrivato?

poi magari il grafo non è orientato ma semplicemente pesato, con il peso = mosse possibili dalla prossima posizione...

caos mentale supremoooo!

[lombardp]

Il programma effettua una ricerca di tutte le possibili soluzioni (almeno dovrebbe) e stampa il risultato a video o su file. Al crescere della matrice il tempo di esecuzione letteralmente esplode (come era prevedibile). Per esempio con una 5x5 partendo da (2,2) ci sono 352 possibili soluzioni e si conclude in frazioni di secondo, già con una 6x6 si misura in minuti.

Esempio di uso su video: brute 2 2
Esempio di uso su file: brute 2 2 > soluzioni.txt

Il LATO della matrice è definito da una #define, ma potrebbe essere anche incluso tra i parametri allocando la matrice dinamicamente.

#include <stdlib.h>
#define LATO 5

int p[LATO*LATO];
int i;

void piazza(int y,int x,int n=1) {
   if (p[y*LATO+x]==0)
   {
      p[y*LATO+x] = n;
      if (n==(LATO*LATO)) {
         for (i=0;i<(LATO*LATO);i++) if ((i%(LATO))==0) printf("\n%i ",p[i]); else printf("%i ",p[i]);
         printf("\n");
      }
      else {
         if (x<LATO-3)               piazza(y,x+3,n+1);
         if (y<LATO-3)               piazza(y+3,x,n+1);
         if (x>2)                    piazza(y,x-3,n+1);
         if (y>2)                    piazza(y-3,x,n+1);
         if ((x<LATO-2)&(y<LATO-2))  piazza(y+2,x+2,n+1);
         if ((x>1)&(y<LATO-2))       piazza(y+2,x-2,n+1);
         if ((x>1)&(y>1))            piazza(y-2,x-2,n+1);
         if ((x<LATO-2)&(y>1))       piazza(y-2,x+2,n+1);
      }
      p[y*LATO+x] = 0;
   }
}

void main(int argc, char* argv[])
{
   for (i=0;i<(LATO*LATO);i++) p[i]=0;
   piazza(atoi(argv[1]),atoi(argv[2]));
   printf("\n\nFINE");
}

PS: E' molto simile a quello di BSUMMER

[verloc]

L'algoritmo di a2000 è un problema di "spanning tree".
...nel caso specifico dovrebbe essere euristico (dico bene a2000 o sbaglio?)
quindi potrebbe esserci la possibilità che fallisca(?)



miseria,non ho tempo...mi piacerebbe cimentarmi.

Solo una curiosità(bisogna costruire la matrice di adiacenza)?

[verloc]

Originariamente inviato da angelica
non riesco a tirar fuori l'algoritmo...qualcuno di voi potrebbe passarlo?
greedy, backtracking o cosa?
...

tieni presente che a2000 lo ha fatto in fortran...
se lo conosco bene...solo matrici,vettori ...niente strutture...
trova una via + semplice... c'è(se no addio 30 righe)

[Strat]

Credo che strutture dati complessa tipo liste, code, ecc... non siano molto utili in questo caso, dall'idea che ci ha dato a2000 una matrice va benissimo, magari si può usare un vettore che tenga memoria di n alternative precedenti in caso di fallimento di un dato percorso.

Ciao

[cn73]

Quante soluzioni trovate per n=6 cominciando dalla cella 0,0??

Ma le vostre soluzioni si fermano appena ne trovano una o le trovano tutte?

[lombardp]

Originariamente inviato da cn73
Quante soluzioni trovate per n=6 cominciando dalla cella 0,0??

Matrice 5x5 partendo da 2,2 : 352 soluzioni
Matrice 6x6 partendo da 0,0 : 302'282 soluzioni

Ma le vostre soluzioni si fermano appena ne trovano una o le trovano tutte?

Il programmino che ho postato le trova tutte... ma basta poco per farlo fermare alla prima.