Problema da afectação de tarefas

[skcratch]

Viva!

Tenho o seguinte problema para resolver:

"Dada uma matriz quadrada de custos C, em que cada elemento cij representa o custo do funcionário fi realizar a tarefa tj, determinar uma atribuição que minimiza o custo total."

O livro aconselhado para obter ajuda para encontrar a solução é o Levitin. Como este livro raramente se encontra disponível na biblioteca, será que alguém me poderia fornecer ajuda/documentação para resolver o problema?

Grato desde já pela ajuda!

Cumps!

🙂

[Warrior]

Quando li pela primeira vez, achei que dava para resolver com Programação Dinâmica, mas lendo mais atentamente, parece-me claramente um problema de min-cost max-flow.

Não tenho a certeza, posso estar a ver min-cost max-flow em todo o lado (este fim de semana saiu um num concurso e não consegui resolver..), mas parece-me que podes modelar os funcionários e as tarefas como nós.

Crias um node "source", ao qual ligas todos os funcionários com uma aresta de tamanho 1, de seguida, crias ligações entre os funcionários e as tarefas, com o tamanho correspondente ao custo. Por último, ligas todas as tarefas a uma "sink", com cada aresta de tamanho 1.

Pretendes maximizar o fluxo minimizando o custo. Não faltam textos a explicar o procedimento melhor do que eu na net, portanto google it.

PS: Parece-me claramente um problema de min-cost, mas como já disse, não tenho a certeza.

Já agora, este tópico parece-me claramente da secção de Algoritmia e Lógica.

[Rui Carlos]

Se percebi bem o problema, penso que é o tipo de problema para o qual (normalmente) se usa o Algoritmo Húngaro. Existem mais uma série de abordagens a este tipo de problemas, mas penso que esta é a que está mais optimizada para a afectação de recursos.

[skcratch]

Viva!

Peço desde já desculpa pela incorrecção do tópico na secção errada e quero desde já agradecer a ajuda que foi até agora prestada!

Cumps!

🙂

[Warrior]

A solução do Rui Carlos é a correcta.

O Hungarian Method serve para isso mesmo. Mais informações aqui:

http://www.ee.oulu.fi/~mpa/matreng/ematr1_2.htm

[mogers]

Eu ainda não sei implementar o algoritmo hungaro, mas pelo que ouvi dizer, provavelmente é a forma mais fácil de resolver o problema.

Podes resolver o problema mais eficientemente com um "Minimum Cost Maximum Flow" modificado, mas este é mais dificil de explicar.

Tal como o Warrior disse, saiu um problema este fim de semana que necessitava de uma das abordagens. Deixo aqui a minha solução ( há implementações muito mais eficientes do algoritmo, mas esta é simples)

Nota: Segundo o que sei, o algoritmo hungaro tem um tempo de execução de O(N^3) , esta implementação do mincost maxflow penso que tem um worst case de O( E * N^3 ) , E sendo o número de ligações ... as implementações mais rápidas têm muito mais código :\

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std; 

#define MAX 1000   //  numero maximo de nodos no grafo

int capacity[MAX][MAX];
int cost[MAX][MAX];

int dist[MAX];
int how[MAX];

int bellman_ford( int source, int sink, int n ) {
memset( dist, 0x3F, sizeof dist );
memset( how, -1, sizeof how );

dist[source] = 0;

for( int tt = 0; tt < n; ++tt ) {
	for( int i = 0; i < n; ++i ) 
		for( int j = 0; j < n; ++j ) {
			if( !capacity[i][j] ) continue;

			if( dist[i] + cost[i][j] < dist[j] ) {
				dist[j] = dist[i] + cost[i][j];
				how[j] = i;
			}
		}
}

if( dist[sink] < 1000000 ) return 1;
return 0;
}

int min_cost_max_flow( int source, int sink, int n ) {
int ret = 0;
while( bellman_ford( source, sink, n ) ) {
	for( int x = sink; x != source; x = how[x] ) {
		capacity[how[x]][x] -= 1;
		capacity[x][how[x]] += 1;
		ret += cost[how[x]][x];
	}
}

return ret;
}

int main()
{
int N , E , i , j , k , p;

cin >> N >> E >> p;   // N = numero de cozinheiros , E = numero de facilities , p = numero de ligações às facilities 

// min cost
memset( capacity, 0, sizeof capacity );
memset( cost, 0, sizeof cost );
int source = 0 , sink = E+N+1;

while (p--)
{
	cin >> i >> j >> k;

	capacity[i+1][N+j+1] = 1;
	cost[i+1][N+j+1]     = k; 
	cost[N+j+1][i+1]     = -k;
}
for (i = 1 ; i <= N ; i++)	capacity[source][i] = 1;	// ligar source aos cozinheiros
for (i = 1 ; i <= E ; i++)	capacity[i+N][sink] = 1;	// ligar facilities ao sink

cout << min_cost_max_flow(source , sink , E+N+2) << endl;
return 0;
}

[skcratch]

Viva!

Uma das estratégias aconselhadas para a resolução deste problema é realizar a permutação dos índices numa determinada solução candidata.

Por exemplo, dado uma solução candidata:

<A_1j, A_2k, A_3l, A_4m>, matriz nxn (neste caso n = 4)

O objectivo é então, gerar todas as permutações dos índices e depois realizar a consulta na matriz dos respectivos valores. Depois da analisadas todas as soluções candidatas, então escolhemos a melhor.

Será que alguém me poderia dar uma ajuda na geração da permutação dos índices?

Grato desde já pela ajuda!

Cumps!

😛

[Warrior]

Essa solução é extremamente menos eficiente do que aquelas referidas por nós anteriormente.. Para teres uma ideia, mais do que 12 tarefas já se começa a tornar impraticável.

Quanto ao teu problema das permutações, há uns tempos fiz um post sobre isso.

Podes ver aqui:

http://www.portugal-a-programar.pt/forums/topic/0-find-topic/?do=findComment&comment=41657

Caso tenhas alguma dúvida, estamos aqui para te esclarecer

PS: O código está em C.

[skcratch]

Viva!

Esta é o meu problema até ao momento. Ainda não gera nenhuma solução, mas após 2 iteraçõe, chega a uma matriz final que já possui uma solução válida.

#include <stdio.h>

#define MAX 4
#define MAX_LINHA 100
#define MAX_COLUNA 100

typedef struct indice
{
int linha;
int coluna;
int custo;
}INDICE;

/* Temos que colocar o nº de elementos das (n - 1) dimensões mais à direita */
void impressao(int matriz[][MAX]);


int main(int argc, char *argv[])
{
int i, j, linha, coluna, menorLinha, menorColuna;

int matriz[MAX][MAX]= {{5, 2, 1, 4}, {5, 2, 7, 8}, {9, 10, 7, 12}, {13, 14, 10, 16}};
INDICE solucao[MAX];

/* Encontrar o menor elemento em todas as linhas */	
for(i = 0; i < MAX; i++)
{
	menorLinha = 100;		
	for(j = 0; j < MAX; j++)
	{
		if(menorLinha > matriz[i][j])
		{
			menorLinha = matriz[i][j];
			coluna = j;
			linha = i;
		}

		/* Armazenamento do indice da linha e da coluna de menor valor */
		solucao[i].linha = linha;
		solucao[i].coluna = coluna;
		solucao[i].custo = menorLinha;
	}

	printf("[%d][%d] = %d\n", solucao[i].linha, solucao[i].coluna, solucao[i].custo);
}

/* Subtracção do menor elemento a cada linha */
for(i = 0; i < MAX; i++)
{
	for(j = 0; j < MAX; j++)
	{
		/* Caso este valor seja 0, esta é uma solução admissível */			
		matriz[i][j] -= solucao[i].custo;
	}
}

impressao(matriz);

/* Encontrar o menor elemento em todas as colunas */
for(j = 0; j < MAX; j++)
{
	menorColuna = 100;		
	for(i = 0; i < MAX; i++)
	{
		if(menorColuna > matriz[i][j])
		{
			menorColuna = matriz[i][j];
			coluna = j;
			linha = i;
		}

		/* Armazenamento do indice da linha e da coluna de menor valor */
		solucao[j].linha = linha;
		solucao[j].coluna = coluna;
		solucao[j].custo = menorColuna;


	}

	printf("[%d][%d] = %d\n", solucao[j].linha, solucao[j].coluna, solucao[j].custo);
}

/* Subtracção do menor elemento a cada coluna */
for(j = 0; j < MAX; j++)
{
	for(i = 0; i < MAX; i++)
	{
		/* Caso este valor seja 0, esta é uma solução admissível */			
		matriz[i][j] -= solucao[j].custo;
	}
}

impressao(matriz);

return 0;
}

void impressao(int matriz[][MAX])
{
int i, j;

for(i = 0; i < MAX; i++)
{
	for(j = 0; j < MAX; j++)
	{
		printf("\t%d", matriz[i][j]);
	}

	putchar('\n');
}	
}

As minhas questões são as seguintes:

- A ideia da estrutura de dados INDICE foi criada com o intuito de armazenar as soluções admissíveis; não me parece a mais correcta, principalmente porque é uma estrutura estática (alguma sugestão?) ou posso usar aquela estrutura mas com memória dinâmica?

- Existe alguma forma de escrever uma função genérica para determinar o menor quer seja no conjunto das linhas quer seja no conjunto das colunas?

- Quando temos mais do que uma linha ou mais do que uma coluna com zeros, quais os testes que se devem realizar para verificar que elemento da matriz é que pertence à solução óptima?

Grato desde já pela ajuda prestada até ao momento!

Cumps!

😛

[Warrior]

Ah, estou a ver que as tuas permutações eram para o algoritmo húngaro. Na altura que escrevi o post pensei que ias tentar brute-force, nem me lembrei que o algoritmo húngaro permutava entre todas as soluções óptimas possíveis no final.

Não estou a ver nenhuma função genérica para testar quer linhas quer colunas. Quer dizer, que dê pouco trabalho.

Podes criar uma função que recebe um apontador e um k. O ciclo dentro da função vai começar no apontador e andar de "k" em "k".

Para as colunas, k = 1, para as linhas, k = número de colunas..

Parece-me trabalho desnecessário sinceramente.

Julgo que esta página responde à tua 3ª pergunta:

http://www.ee.oulu.fi/~mpa/matreng/ematr1_2.htm

E já agora vê o exemplo no final.