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