Jump to content
  • Revista PROGRAMAR: Já está disponível a edição #60 da revista programar. Faz já o download aqui!

Sign in to follow this  
| Blasted |

Bipartite graph matching - Algoritmo Hungaro

Recommended Posts

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

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
Sign in to follow this  

×

Important Information

By using this site you accept our Terms of Use and Privacy Policy. We have placed cookies on your device to help make this website better. You can adjust your cookie settings, otherwise we'll assume you're okay to continue.