Code-Bin #1150

daniel
Posted by: codigozim | March 2, 2011 @ 11:55pm

C++ Code

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <sstream>

#define MAXN 256

using namespace std;

const int maxiterruim = 10000; /* N�mero m�ximo de itera�es sem nenhuma melhora */
const int maxiter = 50000; /* N�mero m�ximo de itera�es */
const double e = 0.05; /* Tamanho m�ximo do grupo = (1+e)*N/k */
const double fatortaboo = 0.4; /* O tamanho da lista taboo � N * fatortaboo */
const int maxncand = 100; /* N�mero m�ximo de v�rtices candidatos a mover */

int nvertice;
int adj[MAXN][MAXN], peso[MAXN][MAXN];
int pesosoma[MAXN];

/* Inicializa com uma parti��o aleat�ria */
vector <int> particao_inicial(int k, int& custo, vector <int>& contrib, vector <int>& tamgrupo)
{
	const int n = nvertice;
	vector <int> particao = vector <int> (n, -1);

if (tamgrupo.size() != k)
		tamgrupo = vector <int> (k, 0);

/* V�rtices sem parti��o atribu�da */
	vector <int> faltam = vector <int> (n, -1);
	for (int i = 0; i < n; i++)
		faltam[i] = i;
	
	/* Atribuindo aleatoriamente */
	for (int i = 0; i < k; i++) {
		int tam = n/k;
		if (i < (n%k))
			tam ++;
		for (int j = 0; j < tam; j++) {
			int escolhe = rand()%faltam.size();
			particao[faltam[escolhe]] = i;

swap(faltam[escolhe], faltam[faltam.size()-1]);
			faltam.pop_back();
		}
		tamgrupo[i] = tam;
	}

/* Custo da solu��o */
	if (contrib.size() != n)
		contrib = vector <int> (n, 0);

custo = 0;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (particao[i] != particao[j] && adj[i][j]) {
				custo += peso[i][j];
				contrib[i] += peso[i][j];
			}
	custo /= 2; /* Cada arestra foi contada duas vezes */

return particao;
}

/* Qual a diferen�a de custo total se mover o v�rtice "i" do grupo atual "anterior" para o grupo "novo" */
int movimento(int i, int novo, vector <int>& particao)
{
	int ret = 0;
	for (int k = 0; k < nvertice; k++) {
		if (particao[k] == particao[i])
			ret += adj[i][k];
		if (particao[k] == novo)
			ret -= adj[i][k];
	}

return ret;
}

void atualizar_contrib(int i, int novo, vector <int>& particao, vector <int>& contrib)
{
	for (int k = 0; k < nvertice; k++) {
		if (particao[k] == particao[i]) {
			contrib[i] += adj[i][k];
			contrib[k] += adj[i][k];
		}
		if (particao[k] == novo) {
			contrib[i] -= adj[i][k];
			contrib[k] -= adj[i][k];
		}
	}
}

vector <int> taboo_search_k_partition(int k, int& custo)
{
	const int n = nvertice;

vector <int> melhor; /* Melhor solu��o */
	int customelhor; /* Custo dela */

vector <int> atual; /* Solu��o atual */
	int custoatual; /* E o custo dela */

int iter = 1, ultimamelhora = 1; /* Itera��o atual e �ltima vez que a solu��o melhorou */

vector <int> contrib(n, 0); /* Com quanto cada v�rtice contribue para o peso total da solu��o */
	deque <int> listataboo; /* V�rtices que temporariamente n�o podem ser movidos (v�rtices taboo) */
	vector <int> taboo(n, 0); /* Se pertence a lista taboo ou n�o */
	const int T = (int)(n * fatortaboo); /* Tamanho da lista taboo */

vector <int> tamgrupo(n, 0); /* Tamanho de cada grupo */
	const int maxgtam = (int)((1.0+e)*n/k); /* Tamanho m�ximo de cada grupo */

atual = particao_inicial(k, custoatual, contrib, tamgrupo);
	melhor = atual;
	customelhor = custoatual;

printf("Custo inicial: %d\n", custoatual);

while (iter-ultimamelhora <= maxiterruim && iter <= maxiter) {
		vector <pair <double, int> > potcands; /* Candidatos em potencial */
		
		for (int i = 0; i < n; i++)
			if (!taboo[i])
				potcands.push_back(make_pair(1.0*contrib[i]/pesosoma[i], i));

partial_sort(potcands.begin(), min(potcands.end(), potcands.begin()+maxncand), potcands.end(), greater <pair <int, int> >());

int mindiff = 2000000000; /* Inf */
		int ncand = min((int)potcands.size(), maxncand);
		pair <int, int> best = make_pair(-1, -1);

for (int i = 0; i < ncand; i++) {
			int cand = potcands[i].second;
			for (int j = 0; j < k; j++)
				if (tamgrupo[j] < maxgtam) {
					int diff = movimento(cand, j, atual);
					if (diff < mindiff) {
						mindiff = diff;
						best = make_pair(cand, j);
					}
				}
		}

if (best == make_pair(-1, -1)){
			printf("\n");
			printf("Sem movimentos.\n");
			break;
		}

int i = best.first, j = best.second;
		int anterior = atual[i];

int diff = movimento(i, j, atual);
		custoatual += diff;
		atual[i] = j;
		if (custoatual < customelhor) {
			customelhor = custoatual;
			melhor = atual;
			ultimamelhora = iter;
			printf("\nMELHORA: Custo atual: %d (iteracao %d)\n", custoatual, iter);
		}
		tamgrupo[anterior] --;
		tamgrupo[j] ++;
		
		taboo[i] = 1;
		listataboo.push_back(i);
		if ((int)listataboo.size() > T) {
			int v = listataboo.front();
			listataboo.pop_front();
			taboo[v] = 0;
		}

atualizar_contrib(i, j, atual, contrib);

if (diff) {
			printf(" %lld ", custoatual);
			fflush(stdout);
		}

iter ++;
	}
	printf("\n");
	if (iter-ultimamelhora > maxiterruim)
		printf("Muito tempo sem melhora.\n");
	if (iter > maxiter)
		printf("Numero maximo de iteracoes atingido.\n");

custo = customelhor;

return melhor;
}

char line[10240000];
int main(int argc, char ** argv)
{
	int k;
printf("Teste.\n");
system("pause");
 FILE * fin = fopen("input", "r");
 if (fin == NULL) {
         printf("Err.\n");
         system("pause");
         return 0;
         
         }
   /* Tenta ai */
   
   printf("ok.\n");

#if 1
	int narestra;
	fgets(line, 1024, fin);
	sscanf(line, "%d %d", &nvertice, &narestra);

const int n = nvertice;

memset(adj, 0, sizeof(adj));
	for (int i = 0; i < n; i++) {
		fgets(line, 1024, fin);
		istringstream iss(line);
		int j;
		pesosoma[i] = 0;
		while (iss >> j) {
			adj[i][j-1] = 1;
			pesosoma[i] += 1;
		}
	}
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (adj[i][j])
				peso[i][j] = 1;
			else
				peso[i][j] = 0;

k = 10;
#else /* Depois tem que atualizar isto aqui tambm */
	scanf("%d %d", &nvertice, &k);

const int n = nvertice;

for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			scanf("%d", &adj[i][j]);

for (int i = 0; i < n; i++) {
		pesosoma[i] = 0;
		for (int j = 0; j < n; j++) {
			scanf("%d", &peso[i][j]);
			pesosoma[i] += peso[i][j];
		}
	}
#endif

printf("Lido.\n");
system("pause");

srand(time(NULL));

int custo;
	vector <int> part = taboo_search_k_partition(k, custo);

for (int j = 0; j < k; j++) {
		int tam = 0;

for (int i = 0; i < n; i++)
			if (part[i] == j)
				tam ++;

printf("Grupo %d (tamanho = %d):", j+1, tam);
		for (int i = 0; i < n; i++)
			if (part[i] == j)
				printf(" %d", i+1);
		printf("\n");
	}
	printf("Custo total: %lld\n", custo);
	while (1) {}

system("sleep 10");
    system("pause");

return 0;
}

Syntax Highlighting

[Open in new window]

Author Comments

none

Rating

4.50 / 8
249 Votes