Ir para o conteúdo
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

| Blasted |

Bipartite graph matching - Algoritmo Hungaro

Mensagens Recomendadas

| Blasted |

Boas!

Estou a desenvolver um trabalho em que preciso de implementar o algoritmo hungaro para encontrar a perfect matching num grafo bipartido.

Fui lendo descrições do algoritmo e comecei pelo primeiro passo que consiste em "reduzir" a matriz.

Fiz isto:

//encontra o menor elemento de cada linha e subtrai a cada elemento esse valor
	for(int i=0;i<matrizLucro.length;i++) {

		int menorValor = -9999;
		for(int j=0;j<matrizLucro[i].length;j++)
			if (matrizLucro[i][j] > menorValor)
				menorValor = matrizLucro[i][j];

		for(int j=0;j<matrizLucro[i].length;j++)
			matrizLucro[i][j] -= menorValor;		

	}

	//encontra o menor valor em cada coluna e subtrai esse valor a cada elemento
	for(int i=0;i<matrizLucro[0].length;i++) {

		int menorValor = -9999;
		for (int j=0;j<matrizLucro[i].length;j++) 
			if (matrizLucro[j][i] > menorValor)
				menorValor = matrizLucro[j][i];

		for (int j=0;j<matrizLucro[i].length;j++) 
			matrizLucro[j][i] -= menorValor;

	}

Os proximos passos é que não estou a compreender exactamente como implementar. Será que me conseguem dar uma ajuda no racciocinio?

Tenho-me guiado por aqui: http://www.wikihow.com/Use-the-Hungarian-Algorithm principalmente.

P.S: Estou a fazer para o maximum matching ao invés da minimum.

Partilhar esta mensagem


Ligação para a mensagem
Partilhar noutros sites

Crie uma conta ou ligue-se para comentar

Só membros podem comentar

Criar nova conta

Registe para ter uma conta na nossa comunidade. É fácil!

Registar nova conta

Entra

Já tem conta? Inicie sessão aqui.

Entrar Agora

×

Aviso Sobre Cookies

Ao usar este site você aceita os nossos Termos de Uso e Política de Privacidade. Este site usa cookies para disponibilizar funcionalidades personalizadas. Para mais informações visite esta página.