Генетический алгоритм

[Sparky]

Необходимо реализовать 3 спосбоа решения задачи о покрытии:
1. жадный алгоритм
2. динамический алгоритм
3. генетический алгоритм.

Реализовала 2 первых, вот динамика:

// cover_dynamics.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"

/*====================================================================================================
				описание данных
====================================================================================================*/
int arr[10][10];	//матрица покрытия
int n,m;	//количество строк (станции) количетсво абонентов(столбцы)
int din[1024][10];	//матрица динамики
int count_str;	//количество строк в таблице динамики

/*====================================================================================================
				процедуры и функции
====================================================================================================*/
int bin_dec(int nstr)	//перевод двоичной строки в число(строка): число
{
	int res=0;
	int i=0;
	for(int j=m-1;j>=0;j--)
	{
		if(arr[nstr][j]==1)
			res=res+(1<<i);
		i++;
	}
	return res;
}

int calc_count_str(int nstr,int nstl)	//вычисление следующей строки(номер строки,номер столбца):номер строки
{
	return nstr-(bin_dec(nstl)&nstr);
}

void print_res(int nstr)	//вывод результата(номер строки)
{
	if(nstr>0)	//находим минимум в строке динамики и запускаем вывод от следующей строки	
	{
		int min=din[nstr][0];	
		int id=0;
		for(int i=1;i<n;i++)
			if ((min>din[nstr][i])&&(din[nstr][i]!=-1))
			{
				min=din[nstr][i];
				id=i;
			}
		printf("%d ",id);
		print_res(calc_count_str(nstr,id));
	}
	else;	//ограничивает рекурсию
}

int dinamica(int nstr,int nstl)	//вычисление чейки динамики(номер строки,номер столбца):значение ячейки
{
	int min=32767;
	for (int j=nstl+1;j<n;j++)
	{
		int temp=calc_count_str(nstr,nstl);
		if((j==n-1)&&((temp&bin_dec(n-1))==temp)&&(temp!=0))	//последний столбец и покрывает полностью
			din[temp][j]=1;

		else if((j==n-1)&&((temp&bin_dec(n-1))!=temp)&&(temp!=0))	//последний столбец не покрывает полностью
			din[temp][j]=-1;

		if((din[temp][j]==32767) && (din[temp][j]!=-1))	//ячейка встретилась первый раз
		{
			if(dinamica(temp,j)!=32767)
				din[temp][j]=dinamica(temp,j);
			else
				din[temp][j]=-1;	//если минимальный не нашёлся, значит покрытия не существует
		}

		if((din[temp][j]!=-1)&&(din[temp][j]+1<min))	//на ячейке которую нужно заполнить на основе предудущей
		{
			min=din[temp][j]+1;
		}
	}
	return min;
}

/*====================================================================================================
				главная прогармма
====================================================================================================*/
int _tmain(int argc, _TCHAR* argv[])
{
/*====================================================================================================
				ввод данных и их инициализация
====================================================================================================*/
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	scanf("%d",&n);
	scanf("%d",&m);
	
	for (int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			scanf("%d",&arr[i][j]);
	
	count_str=1<<m;	//вычислили количество строк в динамике
	
	for(int i=0;i<count_str;i++)
		for(int j=0;j<n;j++)
			din[i][j]=32767;

	for (int j=0;j<n;j++)
		din[0][j]=0;

	int min=32767;
/*====================================================================================================
				динамика
====================================================================================================*/
	int tmp;
	for (int i=0;i<n;i++)	//перебираем строку последнюю в динамике
	{
		tmp=dinamica(count_str-1,i);
		if(tmp==32767)	//если ничего хорошего не вернулось, вершина недоступна
		{
			din[count_str-1][i]=-1;
		}
		else	//иначе значением присваиваем
			din[count_str-1][i]=tmp;
		if (tmp<min)
		{
			min=tmp;	//количество станций которые покрывают
		}
	}
/*====================================================================================================
				вывод результата
====================================================================================================*/
	/*for(int i=0;i<count_str;i++)	//матрица динамики
	{
		for(int j=0;j<n;j++)
			printf("%d ",din[i][j]);
		printf("\n");
	} */

	printf("stations:\n");	//вывод странций, которые покрывают
	if(din[count_str-1][0]==-1) printf("no cover");
	else
	{		
		print_res(count_str-1);
		printf("\ncount: %d",min);
	}

	return 0;
}

[Sparky]

Нужен генетический, в голову ничего не приходит. Что будет являться особями? На основе чего проводить скрещивание?

[Mandrivnyk]

Глупый вопрос, конечно, но...
Тут ты смотрела?

[Sparky]

Да, смотрела

[Sparky]

набросала как поняла, но это, наверное, не правильно:

// cover_genetic.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "ctime"
#include "stdlib.h"
/*================================================================/*====================================================================================================
				описание данных
====================================================================================================*/
int arr[10][10];	//матрица покрытия
int n,m;	//количество строк (станции) количетсво абонентов(столбцы)
int j_id,i_id;

int raund;	//раунд
struct osb
	{
		int first;
		int last;
		int ves;
	};
osb history[100];	//хранит историю популяций

/*================================================================/*====================================================================================================
				процедуру и функции
====================================================================================================*/
void crossing(int n_raund)
{	
	int osb_1,osb_2;
	srand( (unsigned)time(NULL));
	osb_1 = rand()%n;
	srand( (unsigned)time(NULL));
	osb_2 = rand()%n;
	int temp=0;
	for(int j=0;j<m;j++)
	{
		if ((arr[osb_1][j]==arr[osb_2][j])&&(arr[osb_2][j]==1)) temp++;
		else if (arr[osb_1][j]!=arr[osb_2][j]) temp++;
	}
	history[n_raund].first=osb_1;
	history[n_raund].last=osb_2;
	history[n_raund].ves=temp;
}

/*================================================================/*====================================================================================================
				главная прогармма
====================================================================================================*/
int _tmain(int argc, _TCHAR* argv[])
{
/*================================================================/*====================================================================================================
				ввод данных и их инициализация
====================================================================================================*/
	freopen("input.txt","r",stdin);
	freopen("output.txt","w",stdout);
	scanf("%d",&raund);
	scanf("%d",&n);
	scanf("%d",&m);
	
	for (int i=0;i<n;i++)
		for(int j=0;j<m;j++)
			scanf("%d",&arr[i][j]);

/*================================================================/*====================================================================================================
				скрещивание столько раз сколько раундов
====================================================================================================*/
	for(int i=0;i<raund;i++)		
	{
		crossing(i);
	}

/*================================================================/*====================================================================================================
				опредление лучшей особи
====================================================================================================*/
	int max=0;
	for(int i=0;i<n;i++)
	{
		if(history[i].ves>max)
			max=i;
	}
	printf("%d ",history[max].first);
	printf("%d ",history[max].last);
	printf("\n%d",history[max].ves);
	return 0;
}

[Sparky]

как писать генетику поняла, что в данной задаче будет обычным перебором? Кто-то может просто описать алгоритм? Могу привести жадный