[C]Funzione incrocia vettori

di il
11 risposte

[C]Funzione incrocia vettori

Ciao a tutti!
Premetto che il post iniziale è lungo, ma perchè vi ho descritto minuzinosamente il problema, così da facilirare i volenterosi che vorranno aiutarmi!
Vi presento il problema:
devo realizzare una funzione che prende in ingresso 2 vettori ed effettua uno scambio (lo descrivo tra poco). I 2 vettori di lunghezza uguale "dim" sono composti da interi (0 e 1) e in particolare hanno un numero di 1 "num" che deve rimanere fisso anche dopo l'applicazione di questa funzione.
La funzione deve tagliare i due vettori (con un numero di taglio casuale) e scambiare le seconde parti di essi tra loro. Ecco un esempio:

v1:0101 v2: 1010
taglio: 2
v1: 0110 v2: 1001

Il problema sorge quando gli uni sono posizionati in maniera particolare, es:
v1: 1100 v2: 0011
taglio: 2
v1: 1111 v2: 0000

In questo caso il numero di 1 nei vettori è cambiato, e non va bene.

Voi come fareste???

Io ho pensato di fare così (sono aperto a qualsiasi altra idea da applicare):
creare altri 2 vettori che contengono gli indici di dove sono posizionati gli 1 e fare continui controlli che non vengano generati indici doppioni (in quel caso quando faccio la riconversione da vettore indici a vettore di 0 e 1 mi perdo un 1). Se trovo un doppione genero in maniera casuale un nuovo indice che rappresenta un valore 0 nei vettori primari così da preservare il numero di 1.
Ecco il mio codice:

void crossover(int* individuo1, int* individuo2, int dim, int num)
{
    int i,j,z,
        num_taglio,
        doppione;
    int *appoggio,
        *sottografo1,
        *sottografo2;
    
        appoggio = (int *) malloc(sizeof(int) * num); 
        sottografo1 =  (int *) malloc(sizeof(int) * num);    
        sottografo2 =  (int *) malloc(sizeof(int) * num);  
        
        for(i=0, j=0;i<dim;i++)
        { 
             if(individuo1[i] == 1)
             {
                 sottografo1[j] = i;
                 j++;
             }
             
        }
        for(i=0, z=0;i<dim;i++)
        { 
             if(individuo2[i] == 1)
             {
                 sottografo2[z] = i;
                 z++;
             }
        }
        /*devo generare un numero tra 1 e k-2*/
        /*così facendo genero un random tra 0 e (k-3) poi aggiungo uno al risultato*/
        num_taglio = (RANDOM((nodi_sottografo-2))+1);
        /*copio la seconda parte del primo individuo nell'array di appoggio*/
        for(i = num_taglio; i<num; i++)
        {
              appoggio[i]=sottografo1[i]; 
        }

        for(i=num_taglio;i<num;i++)
        {
            sottografo1[i] = sottografo2[i];
            /*controllo che non vi siano doppioni*/
            for(j=0;j<num_taglio;j++)
            {
                /*se trovo un doppione*/
                if(sottografo1[j] == sottografo2[i])
                {
                    /*prendo un altro nodo random, che non era già stato preso*/
                    do
                    {
                        doppione = RANDOM(dim);
                    }while(individuo1[doppione] == 1);
                    sottografo1[i] = doppione;
                }


            }
        }        
        for(i=num_taglio;i<num;i++)
        {
             sottografo2[i] = appoggio[i];
             /*controllo che non vi siano doppioni*/
            for(j=0;j<num_taglio;j++)
            {
                /*se trovo un doppione*/
                if(sottografo2[j] == appoggio[i])
                {
                    /*prendo un altro nodo random, che non era già stato preso*/
                    do
                    {
                        doppione = RANDOM(dim);
                    }while(individuo2[doppione] == 1);
                    sottografo2[i] = doppione;
                }
                
            }
        }    
        /*resetto gli individui*/
        for(i=0;i<dim;i++)
        {
           individuo1[i]=0;
           individuo2[i]=0;
        }          
        /*creo l'individuo finale*/
        for(i=0;i<num;i++)
        {
           individuo1[sottografo1[i]] = 1;
        }         
        /*creo l'individuo finale*/
        for(i=0;i<num;i++)
        {
           individuo2[sottografo2[i]] = 1;  
        }      

}
RANDOM(x) è:

#define RANDOM(x) rand() % x
Nella mia main richiamo questa funzione in un ciclo così da richiamarla più a più volte. Una volta ogni 10 lanci applicazione si blocca tutto perchè ad un certo punto quando vado a costruire i vettori finali perdo un 1 così all'iterazione successiva che prende quel vettore non riesco a scrivere tutto il vettore che contiene gli indici e andando a creare i vettori finali all'istruzione:
individuo1[sottografo] =1;
dove i vale num, ovviamente tento di accedere ad una porzione di memoria che non ho allocato.

ATTENDO AIUTOOOO!!!

11 Risposte

  • Re: [C]Funzione incrocia vettori

    Non hai spiegato bene la parte dei tagli. Se il taglio è uguale a 2 cosa significa? Devo scambiare solo due elementi (prendendo supponiamo un indice a caso dal vettore 2 e scambiarlo con un indice a caso del vettore 1 finche il numero degli elementi scambiati sia uguale a 2), oppure devo iniziare dall'indice 2 e fare gli scambi alla ciecca e cioè inidice 2 + due elementi scambio la seconda parte e basta. Se la seconda tu non hai controllo e avrai dati incongruenti dopo il taglio.
  • Re: [C]Funzione incrocia vettori

    Il taglio viene fatto in questo modo:
    genero il numero di taglio casualmente (senza prendere gli estremi) e utilizzo quel numero come indice di partenza da dove tagliare es:

    taglio 3
    v1: pos0: 2
    pos1: 4
    pos2: 5
    pos3: 7
    pos4: 9

    v2: pos0: 1
    pos1: 3
    pos2: 6
    pos3: 8
    pos4: 10
    nuovi vettori:
    v1: 2 4 5 | 8 10
    v2: 1 3 6 | 7 9

    Quindi questa penso ricada nella seconda tua opzione...puoi spiegarti meglio quando dici che perdo il controllo?
    E come potrei risolvere?
    Grazie
  • Re: [C]Funzione incrocia vettori

    Tu scegli solo l'indice del taglio non sai cosa contengono gli indici dal taglio in avanti, quindi non c'è modo di risolvere perche il problema è abbastanza rigido. Scegli solo il taglio e poi quel che viene viene.
  • Re: [C]Funzione incrocia vettori

    E' fondamentale che il numero di 1 rimanga inalterato, quel vincolo non posso toccarlo, il resto è tutta fantasia.

    skynet ha scritto:


    Tu scegli solo l'indice del taglio non sai cosa contengono gli indici dal taglio in avanti
    Io scelgo un numero di taglio e nient'altro, a cosa ti riferisci precisamente?
    Volevo farti notare che il taglio e lo scambio vien applicato sui vettori che contengono gli indici di dove sono posizionati gli 1.
    Non mi sembra di imporre forti vincoli e non capisco bene a cosa ti riferisci, puoi essere più chiaro e magari proporre una soluzione per il mio problema?
    Grazie
  • Re: [C]Funzione incrocia vettori

    Allora son io che non capisco il problema. Tu imponi l'indice di partenza. Ma se fai lo scambio il numero degli 1 nel vettore cambierá di certo perche dal taglio in poi il numero degli 1 sarà differente nei due vettori. Quindi non vedo una soluzione, se ho capito il problema bene.
  • Re: [C]Funzione incrocia vettori

    Da quello che ho capito io quando si opera il taglio casuale bisogna far si che risultino, già in questa fase, esclusi i tagli che poi porteranno alla situazione problematica di 1 in più o in meno. Sapere quindi in anticipo, nel momento del taglio, quali tagli non potranno essere effettuati e quindi lasciare che il caso scelga tra quelli rimanenti. A livello logico mi sembra la soluzione poichè è certamente impossibile che ogni taglio sia sempre possibile. O no?

    PS non ho guardato il codice ma ho visto l'evolversi dei messaggi, può darsi (e mi pare probabile) che io abbia appena detto la cosa più ovvia del mondo e che già ci avessi pensato.
  • Re: [C]Funzione incrocia vettori

    skynet ha scritto:


    Allora son io che non capisco il problema. Tu imponi l'indice di partenza. Ma se fai lo scambio il numero degli 1 nel vettore cambierá di certo perche dal taglio in poi il numero degli 1 sarà differente nei due vettori.
    No non cambia perchè io non faccio il taglio sul vettore contenente 0 e 1, leggi bene il mio primo post.
    Per ovviare al problema del taglio che cambia il numero di 1 io creo altri due vettori di interi, e li riempio con il valore degli indici, il cui valore è 1.
    Eempio:

    v1: 0 1 1 1 0 0 1 0 =>diventa=> v1': 1 2 3 6
    v2: 1 0 0 0 1 1 0 1=>diventa=> v2': 0 4 5 7

    così che ovunque sia il taglio io, occupandomi sempre di 1, garantisco il loro numero.

    supponendo un ipotetico taglio ad altezza 1:

    v1': 1 4 5 7
    v2': 0 2 3 6

    e facendo l'operazione di riconversione ottengo:

    v1: 0 1 0 0 1 1 0 1
    v2: 1 0 1 1 0 0 1 0

    Così garantisco il numero di 1...ma io questa cosa l'ho già scritta e nel codice si ragiona in questa maniera, il mio problema nasce quando ci sono indici doppioni.
    Leggete tutto con calma per favore.
  • Re: [C]Funzione incrocia vettori

    Io continuo a rabbidire che il tuo problema non ha soluzioni. Nei tuoi esempi funziona perche la distribuzione degli 1 è omogenea in tutti e due i vettori. Ovvunque fai il taglio avrai x 1 da una parte e y 1 dall'altra. Se prendi il caso generale questa distribuzione non sarà omogenea e se farai un solo taglio non riuscirai a manatenere il numero degli 1. Quindi non so se l'esempio prevede anche tagli consecutivi o meno.
    In questo esempio:

    v1: 1100 v2: 0011

    la distribuzione degli 1 non è omogenea nei due vettori. Nel primo è concentrato nei inidici iniziali, nel secondo nei inidci finali. Con un taglio non riesci a fare ciò che devi.
  • Re: [C]Funzione incrocia vettori

    skynet ha scritto:


    Io continuo a rabbidire che il tuo problema non ha soluzioni. Nei tuoi esempi funziona perche la distribuzione degli 1 è omogenea in tutti e due i vettori. Ovvunque fai il taglio avrai x 1 da una parte e y 1 dall'altra. Se prendi il caso generale questa distribuzione non sarà omogenea e se farai un solo taglio non riuscirai a manatenere il numero degli 1. Quindi non so se l'esempio prevede anche tagli consecutivi o meno.
    In questo esempio:

    v1: 1100 v2: 0011

    la distribuzione degli 1 non è omogenea nei due vettori. Nel primo è concentrato nei inidici iniziali, nel secondo nei inidci finali. Con un taglio non riesci a fare ciò che devi.
    Nel tuo esempio il mio algoritmo crea 2 vettori contenente gli indici di dove sono posizionati gli 1,quindi:
    v1': 0 1
    v2': 2 3
    Al taglio 0 (visto che in questo caso 1 non taglierebbe nulla) ottengo:
    v1'': 0 3
    v2'': 2 1
    E alla riconversione creo due individui vergini (tutti 0) e faccio:
    v1[0] = 1; v1[3] = 1; ottenendo un vettore si fatto: 1 0 0 1
    v2[2] = 1; v2[1] = 1; ottenendo un vettore si fatto: 0 1 1 0

    Ed ecco mantenuto il numero di 1.
  • Re: [C]Funzione incrocia vettori

    Ho capito ma il taglio hai detto che è casuale. Così è andare per tentativi. Poi qui il taglio lo stai applicando ai vettori convertiti non a quelli originali. Quindi o son io che non comprendo oppure ti sei spiegato male. I vettori che ho preso come esempio sono i tuoi d'inizio dove tu stesso hai applicato il taglio sugli originali, da cui la mia risposta sull'impossibilità della soluzione.
  • Re: [C]Funzione incrocia vettori

    Hai ragione...
Devi accedere o registrarti per scrivere nel forum
11 risposte