Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
Algoritmi - Non so che titolo dare a questo thread...
Forum - Algoritmi - Non so che titolo dare a questo thread...

Pagine: [ 1 2 ] Precedente | Prossimo
Avatar
AldoBaldo (Member)
Guru


Messaggi: 699
Iscritto: 08/01/2015

Segnala al moderatore
Postato alle 15:12
Sabato, 26/08/2017
Perdonatemi se ho messo un titolo tanto idiota, ma è la verità: non so che titolo dare a un thread che parte da una domanda come quella che sto per fare.

Sto (provando a) realizzare un giochino che consiste nel raggruppare caselle di colore diverso in "aree" di colore uniforme, per cui dovrei a un certo punto verificare quanti e quali caselle sono contenute in ciascuna area di colore uniforme (ad esempio, nell'immagine in coda è mostrata la situazione dello schema in un certo momento d'una ipotetica partita).

I numeri corrispondono alla quantità degli spostamenti che il giocatore ha posto in essere per spostare le varie caselle dalla posizione di partenza a quella corrente, e in base a quei numeri dovrò in qualche modo (che non ho ancora pensato) calcolare il punteggio.

Per il momento, non riesco a farmi venire in mente un metodo SEMPLICE (anche a costo di rimetterci qualcosa in termini di prestazioni, che non sono importanti) e COMPRENSIBILE per rilevare le aree di colore uniforme e poterle poi analizzare in termini di dimensioni (quante caselle) e valore (con che punteggio). Vorrei rilevare solo le aree costituite da una quantità minima arbitraria di caselle in su, ad esempio 5. Nello schema d'esempio si possono vedere, per dire, un'area rossa di cinque caselle, piuttosto compatta, una gialla molto articolata con 19 caselle, due aree arancioni da 7 caselle ciascuna, alcune caselle "annullate" per aver esaurito le mosse a disposizione e così via.

Pensavo di generare dei vettori di strutture che descrivano le caselle "scelte", uno per ogni area, ma fatico a capire come individuare le caselle da inserirci.

E' possibile una soluzione iterativa o dovrò ricorrere a una ricorsiva (le ricorsioni ancora mi confondono)?

Che tipo di algoritmo posso provare a seguire? Fino ad ora mi son venute in mente solo soluzioni cervellotiche che temo siano più stupide del dovuto.

Non è un problema che dia luogo a questioni di vita o di morte, anzi, non è proprio un problema. Diciamo piuttosto che è un rompicapo che mi piacerebbe riuscire a risolvere ma rispetto al quale sono bloccato.



AldoBaldo ha allegato un file: screenshot.png (105157 bytes)
Clicca qui per guardare l'immagine

Ultima modifica effettuata da AldoBaldo il 26/08/2017 alle 15:21


ATTENZIONE! Sono un hobbista e l'affidabilità delle mie conoscenze informatiche è molto limitata. Non prendere come esempio il codice che scrivo, perché non ho alcuna formazione accademica e rischieresti di apprendere pratiche controproducenti.
PM Quote
Avatar
AldoBaldo (Member)
Guru


Messaggi: 699
Iscritto: 08/01/2015

Segnala al moderatore
Postato alle 15:23
Sabato, 26/08/2017
Già che ci sono, per chi si fidasse e volesse vedere dove sono arrivato fin'ora, allego anche un exe provvisorio (per Windows, 123 KB).


AldoBaldo ha allegato un file: colori.zip (56401 bytes)
Clicca qui per scaricare il file


ATTENZIONE! Sono un hobbista e l'affidabilità delle mie conoscenze informatiche è molto limitata. Non prendere come esempio il codice che scrivo, perché non ho alcuna formazione accademica e rischieresti di apprendere pratiche controproducenti.
PM Quote
Avatar
Roby94 (Member)
Guru


Messaggi: 1170
Iscritto: 28/12/2009

Segnala al moderatore
Postato alle 15:36
Sabato, 26/08/2017
Testo quotato

Postato originariamente da AldoBaldo:
(le ricorsioni ancora mi confondono)


Mettiti sotto a fare esercizi perché le funzioni ricorsive sono fondamentali nello sviluppo di algoritmi e quindi non andrebbero assolutamente lasciate come buco formativo.

L'algoritmo più semplice è quello a ricerca in un labirinto mediante albero, ora non ricordo il nome ma il concetto è questo.
Prendi una cella e verifichi che le celle adiacenti siano valide per il tuo processo di ricerca(stesso colore) per ognuna di queste celle riesegui l'algoritmo.
Importante è tenere traccia delle celle già indicizzate e del numero di celle valide trovate(semplicemente il numero di chiamate della funzione). Ad ogni iterazione ti puoi trovare davanti a due casi: non ci sono caselle adiacenti dello stesso non visitate quindi la funzione termina, oppure c'è almeno una una cella dello stesso colore non visitata e allora come detto in precedenza rilanci la funzione su quelle celle.
Può andare?

PM Quote
Avatar
AldoBaldo (Member)
Guru


Messaggi: 699
Iscritto: 08/01/2015

Segnala al moderatore
Postato alle 15:45
Sabato, 26/08/2017
E' proprio quel che ho già provato a fare, anche se con formulazione iterativa anziché ricorsiva, e mi viene fuori una cosa piuttosto cervellotica. Diciamo "articolata", tò. Speravo potessero esistere soluzioni più lineari ma, se mi dici che non ne esistono, insisto a "spaccarmi" la testa su quella finché riesco. E ci riesco, vedrai! ("l'ottimismo è il sale della vita") Pensi che una soluzione ricorsiva sarebbe migliore di una iterativa? Giusto per sapere come mi conviene incamminanrmi.

Comunque mi hai già dato un bell'indirizzo segnalandomi l'affinità con la ricerca d'un percorso in un labirinto: ricordo d'aver trovato fior di articoli sul tema, quindi andare a rileggermeli potrebbe aiutarmi.

Ultima modifica effettuata da AldoBaldo il 26/08/2017 alle 15:46


ATTENZIONE! Sono un hobbista e l'affidabilità delle mie conoscenze informatiche è molto limitata. Non prendere come esempio il codice che scrivo, perché non ho alcuna formazione accademica e rischieresti di apprendere pratiche controproducenti.
PM Quote
Avatar
lumo (Member)
Expert


Messaggi: 449
Iscritto: 18/04/2010

Segnala al moderatore
Postato alle 16:43
Sabato, 26/08/2017
Se vuoi cercare l'argomento su uno dei tuoi libri di algoritmi, quello che vuoi fare è trovare le componenti connesse del grafo associato alla griglia: https://en.wikipedia.org/wiki/Connected_component_(graph_th ...

Le trovi facendo una breadth first search leggermente modificata, la ricorsione non serve anche se ti consiglio di studiarla ugualmente.

Ultima modifica effettuata da lumo il 26/08/2017 alle 16:47
PM Quote
Avatar
Roby94 (Member)
Guru


Messaggi: 1170
Iscritto: 28/12/2009

Segnala al moderatore
Postato alle 17:02
Sabato, 26/08/2017
Testo quotato

Postato originariamente da AldoBaldo:

Speravo potessero esistere soluzioni più lineari ma, se mi dici che non ne esistono,


Io non ho detto che non esistono, le funzioni ricorsive hanno sempre una rappresentazione iterativa, ma si perde la generalità della soluzione e si complica l'algoritmo con soli effetti negativi.

Le funzioni ricorsive sono importanti e sono un tassello indispensabile nel bagaglio formativo di un programmatore. Ostinarsi a non imparare questa tecnica è come lo studente di modellistica che continua imperterrito a non volere imparare il calcolo differenziale.

PM Quote
Avatar
AldoBaldo (Member)
Guru


Messaggi: 699
Iscritto: 08/01/2015

Segnala al moderatore
Postato alle 21:33
Sabato, 26/08/2017
Grazie Lumo! Da una primissima e superficiale occhiata credo proprio che quello che mi indichi sia quel che mi serve. Certo, ora si tratta di capirlo e vedere come usarlo, e questa è tutta un'altra faccenda. Ci provo questa sera stessa!!! Anzi, ora.
Ah, aggiungo che da solo non l'avrei mai scoperto, non sapendo cosa cercare.

Roby, non è che la ricorsione non so cos'è, è che ancora mi confonde, ovvero per usarla devo spaccarmi il cervello. In alcuni casi semplici l'ho anche usata (spaccandomi, appunto, il cervello). Dai e dai, imparerò ben, no? Il fatto è che già non sono sicuro di capire bene il procedimento, ancora che ci metto il "carico da undici" camminando sulle sabbie mobili d'un terreno sul quale mi sento instabile... ehm...


ATTENZIONE! Sono un hobbista e l'affidabilità delle mie conoscenze informatiche è molto limitata. Non prendere come esempio il codice che scrivo, perché non ho alcuna formazione accademica e rischieresti di apprendere pratiche controproducenti.
PM Quote
Avatar
AldoBaldo (Member)
Guru


Messaggi: 699
Iscritto: 08/01/2015

Segnala al moderatore
Postato alle 2:12
Domenica, 27/08/2017
Allora... per prima cosa un invito alla clemenza, perché sto sondando un terreno del quale non so nulla, e lo faccio poggiando su basi non certo solide. Diciamo che il mio è un gesto di coraggio. :)

Ho letto un po' di cose sulla questione dei grafi e di come organizzare la loro analisi. M'è sembrato di capire che un primo passo che occorre fare per ottenere quel che mi serve (ma potrei sbagliarmi) consiste nel realizzare una "matrice d'adiacenza" da usare poi nell'algoritmo d'analisi. Dunque ho cercato di informarmi su cosa fosse questa sconosciuta "matrice d'adiacenza" e ne è emerso che è una specie di tabellina. Nella sua forma più semplice (che credo sia quella che mi serve) l'ho ottenuta così:

Codice sorgente - presumibilmente C++

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define QR  3 // quantita' delle righe   (nella matrice dei colori)
  5. #define QC  4 // quantita' delle colonne (nella matrice dei colori)
  6.  
  7. char mc[QR][QC] = { // mc = matrice dei colori
  8.     {'G','G','B','B'},
  9.     {'R','G','B','R'},
  10.     {'R','B','B','B'},
  11. };
  12.  
  13. int ma[QR*QC][QR*QC] = {{0},{0}}; // ma = matrice d'adiacenza
  14.  
  15. void esplora_adiacenze( int ra, int rc, int cc );
  16. void print_mc( void );
  17. void print_ma( void );
  18.  
  19. int main() {
  20.     int r, c;
  21.  
  22.     // analizza uno per uno i caratteri presenti nella matrice dei
  23.     // colori, al fine di compilare una matrice delle adiacenze
  24.  
  25.     for( r=0; r<QR; ++r )
  26.         for( c=0; c<QC; ++c )
  27.             esplora_adiacenze( r*QC+c, r, c );
  28.  
  29.     print_mc(); // mostra la matrice dei colori
  30.     printf( "\n" );
  31.     print_ma(); // mostra la matrice d'adiacenza
  32.  
  33.     return 0;
  34. }
  35.  
  36. /*==============================================================================
  37. ra = riga    nella matrice d'adiacenza
  38. ca = colonna nella matrice d'adiacenza
  39. rc = riga    nella matrice dei colori
  40. cc = colonna nella matrice dei colori
  41.  
  42. La funzione prende in considerazione un carattere della matrice dei colori e lo
  43. confronta con tutti gli altri caratteri della stessa matrice, inserendo i
  44. risultati dei confronti nella riga della matrice d'adiacenza che corrisponde al
  45. numero d'ordine del carattere nella matrice dei colori ottenuto seguendo questo
  46. schema:
  47.  
  48.      1  2  3  4
  49.      5  6  7  8
  50.      9 10 11 12
  51. ==============================================================================*/
  52.  
  53. void esplora_adiacenze( int ra, int rc, int cc ) {
  54.     int r, c, ca; // r = contatore righe; c = contatore colonne
  55.  
  56.     for( ca=0, r=0; r<QR; ++r ) {
  57.         for( c=0; c<QC; ++c, ++ca ) {
  58.             ma[ra][ca] =                  // l'adiacenza e' verificata se...
  59.                 (mc[r][c]==mc[rc][cc]) &&         // i colori sono uguali e...
  60.                 (((r==rc)&&(c==cc-1||c==cc+1)) || // condividono l'ascissa o...
  61.                 ((c==cc)&&(r==rc-1||r==rc+1)));   // condividono l'ordinata
  62.         }
  63.     }
  64. }
  65.  
  66. /*==============================================================================
  67. Visualizza la matrice dei colori.
  68. ==============================================================================*/
  69.  
  70. void print_mc( void ) {
  71.     const char bv[4] = {179,'\n','\0','\0'}; // bv = barra verticale;
  72.     int r, c, i;
  73.  
  74.     printf( "    " );
  75.     for( i=0; i<QC; ++i )
  76.         printf( "  %c ", 'A'+i );
  77.     printf( "\n" );
  78.  
  79.     for( r=0; r<QR; ++r ) {
  80.         printf( "    " );
  81.         for( i=0; i<QC; ++i )
  82.             printf( "%c%c%c%c", r!=0?(i!=0?197:195):(i!=0?194:218),196,196,196 );
  83.         printf( "%c\n", r==0?191:180 );
  84.  
  85.         printf( "  %c ", '1'+r );
  86.         for( c=0; c<QC; ++c )
  87.             printf( "%c %c %s", 179, mc[r][c], c<QC-1?"":bv );
  88.     }
  89.  
  90.     printf( "    " );
  91.     for( i=0; i<QC; ++i )
  92.         printf( "%c%c%c%c", r!=0?(i!=0?193:192):(i!=0?194:218),196,196,196 );
  93.     printf( "%c\n", r==0?191:217 );
  94. }
  95.  
  96. /*==============================================================================
  97. Visualizza la matrice d'adiacenza.
  98. ==============================================================================*/
  99.  
  100. void print_ma( void ) {
  101.     const char bv[4] = {179,'\n','\0','\0'}; // bv = barra verticale;
  102.     int r, c, i;
  103.  
  104.     printf( "    " );
  105.     for( i=0; i<QR*QC; ++i )
  106.         printf( " %c%c ", 'A'+(i%QC), '1'+(i/QC) );
  107.     printf( "\n" );
  108.  
  109.     for( r=0; r<QR*QC; ++r ) {
  110.         printf( "    " );
  111.         for( i=0; i<QR*QC; ++i )
  112.             printf( "%c%c%c%c", r!=0?(i!=0?197:195):(i!=0?194:218),196,196,196 );
  113.         printf( "%c\n", r==0?191:180 );
  114.  
  115.         printf( " %c%c ", 'A'+(r%QC), '1'+(r/QC) );
  116.         for( c=0; c<QR*QC; ++c )
  117.             printf( "%c %c %s", 179, ma[r][c]?254:' ', c<QR*QC-1?"":bv );
  118.     }
  119.  
  120.     printf( "    " );
  121.     for( i=0; i<QR*QC; ++i )
  122.         printf( "%c%c%c%c", r!=0?(i!=0?193:192):(i!=0?194:218),196,196,196 );
  123.     printf( "%c\n", r==0?191:217 );
  124. }



Per non perderci troppo tempo ho temporaneamente usato delle variabili globali, ma non è importante. Quel che vorrei sapere è: è corretto quel che ho fatto? Serve davvero o è un "vicolo cieco"?

P.S. print_mc() e print_ma() sono irrilevanti nel contesto del discorso: mi son servite solo per vedere cosa stavo facendo.


ATTENZIONE! Sono un hobbista e l'affidabilità delle mie conoscenze informatiche è molto limitata. Non prendere come esempio il codice che scrivo, perché non ho alcuna formazione accademica e rischieresti di apprendere pratiche controproducenti.
PM Quote
Avatar
lumo (Member)
Expert


Messaggi: 449
Iscritto: 18/04/2010

Segnala al moderatore
Postato alle 11:40
Domenica, 27/08/2017
Il codice non riesco a leggerlo, ti dico che con la matrice di adiacenza puoi di sicuro combinare qualcosa, anche se probabilmente qui non serve.
La matrice di adiacenza si usa quando vuoi rispondere in modo rapido alla domanda "il nodo X e Y sono connessi?".
Inoltre si usano di solito solo quando il grafo ha un numero di nodi prefissato, altrimenti devi aumentarne la dimensione, copiare tutto ecc... nel caso di grafi dinamici si usa infatti la lista di adiacenza di solito.

Detto questo, non ti serve a molto la matrice di adiacenza perché dovresti costruirla, ma per costruirla devi definire un concetto di connessione sulla tua griglia, e inizialmente questo sarà: ogni cella ha come vicini quelli che stanno sopra sotto, a sinistra a destra (o una cosa simile).
Quindi verrebbe fuori una matrice di adiacenza abbastanza scontata.
Ti consiglio invece di capire l'algoritmo per trovare le componenti connesse e dopo applicarlo direttamente sulla griglia, senza costruire esplicitamente il grafo associato: alla fine è esattamente quello che ti ha descritto Roby.

P.S.
Codice sorgente - presumibilmente Plain Text

  1. printf( "%c%c%c%c", r!=0?(i!=0?197:195):(i!=0?194:218),196,196,196 );


No.

Ultima modifica effettuata da lumo il 27/08/2017 alle 11:42
PM Quote
Pagine: [ 1 2 ] Precedente | Prossimo