| . | |
| A equipe: | |
| Andrei Goldchleger | 2936971 |
| Leo Kazuhiro Ueda | 2957467 |
| Wagner César Bruna | 1800794 |
Se a matriz A não é quadrada, isto é, se m <= n, o programa escolhe um elemento por linha; caso contrário, escolhe um elemento por coluna. De qualquer forma, nunca há mais do que um elemento escolhido em uma linha ou coluna.
Uma chamada à função tem o seguinte aspecto:
a) Da forma <parâmetro>=<valor>. Esses parâmetros
são repassados para a chamada da função lisa
e, como já foi explicado, são os seguintes:
m, n: respectivamente, número de linhas e colunas de A;
d: os números da matriz estão no intervalo [0..d];
d0, d1: no processo de geração da matriz
A, os valores (que Knuth chama de 'raw data') menores que
d0 serão convertidos para 0 e os maiores que d1
serão convertidos para d.
-e: usa somente a região dos olhos da Mona Lisa;
-c: troca as cores dos pontos da matriz pelos seus complementos (cada ponto com valor i recebe valor 255 - i);
-h: usa uma heurística para resolver o problema, se aplica quando m = n;
-v ou -V: modo verborrágico ou mais verborrágico ainda;
-p: imprime a matriz e a solução na tela;
-P: gera um postscript encapsulado com uma saída gráfica.
Brincando com o programa, achamos interessantes execuções
com saída gráfica, como por exemplo:
A solução implementada pelo programa resolve o clássico problema de achar um casamento perfeito em um grafo bipartido: dado um grafo simétrico bipartido, devemos associar todos os elementos de cada partição a somente um elemento da outra partição, sendo que essa associação deve respeitar as arestas do grafo.
Enxergando a matriz como um grafo bipartido simétrico (cada linha ou coluna representa um vértice, o conjunto de linhas representa uma das partições, o conjunto de colunas a outra, e uma aresta de u a v é um elemento da linha u e da coluna v que é igual a 0), um casamento perfeito determinaria elementos tal que há somente um deles em cada linha e coluna.
Knuth propõe então que troquemos o problema de maximização por minimização, pois este seria mais fácil de tratar, e poderia ser em seguida revertido no problema original. A facilidade em resolver o problema de minimização está justamente no fato que, em uma matriz de números não negativos, se encontrarmos um casamento perfeito conforme descrito acima, encontraremos os elementos tais que a soma é igual a 0, que certamente é mínima. Por isso, no início do programa cada elemento da matriz A recebe o seu complemento (a diferença entre ele e 255), a não ser que a opção -c tenha sido escolhida.
Para entendermos a solução problema, é importante o conceito de zeros independentes ou casamento. Dois zeros são chamados de independentes se eles não estão na mesma linha e coluna. Assim, é possivel observar que, em A(mxn), o número de zeros independentes é no máximo min{m,n}. Os matemáticos húngaros Egerváry e König provaram que o número de zeros independentes em uma matriz A(mxn) é igual ao número mínimo de linhas ou colunas que contém todos os zeros da matriz.
Dessa demonstração sai uma parte do algoritmo apresentado (chamaremos essa parte de algoritmo Húngaro). Suponha que a notação r(k)--c(l) denota um zero comum da matriz e r(k)==c(l) denota um zero independente da matriz ou um casamento entre r(k) e c(l). Diremos que escolhemos a coluna c da matriz somente se ela e atingível por um caminho da seguinte forma:
r(0)--c(1)==r(1)--c(2)==...--c(q)==r(q) (*)
onde c é c(q) e r(0) não está casada. Uma linha r da matriz só será escolhida se ela é casada com uma coluna não escolhida.
É possivel provar que nesse estágio ou já escolhemos todos os casamentos ou é possivel achar mais um zero independente:
Para algum c==r, já escolhemos c ou r (não
é possível aumentar o número de casamentos). Para
c--r, temos várias possibilidades:
2. r não está casada e c está casada com outro elemento, temos novamente algo como o caminho (*) (c escolhida, nada a fazer): r--c==r'
3. c e r não são casadas, podemos então casá-las (r será escolhida, aumentamos o número de casamentos): c--r => c==r
4. r está casada com c' (outro elemento).
Temos então mais possibilidades:
4b. c' foi escolhida, temos então um caminho da forma: r(0)--c(1)==r(1)--c(2)==...==r(q-1)--c'==r--c, onde r(0) não está casada e q >= 1.
Se c for casada temos o caminho (*), não há nada a fazer. Caso contrário, é possível aumentar o número de casamentos trocando os pares em cada casamento (temos um caminho de aumento):
r(0)==c(1)--r(1)==c(2)--...--r(q-1)==c'--r==c
Dessa forma aumentamos o número de casamentos (escolhemos mais
um zero independente).
Antes de descrevermos o artifício devemos confirmar uma pequena observação. Esta diz que se somarmos uma constante aos elementos de uma linha ou coluna, a solução permanece inalterada. É trivial perceber isso, uma vez que alguma posição daquela linha ou coluna será máxima, não importa se uma constante é somada a todas as posições dessa fileira (fileira é uma linha ou coluna).
Vamos agora ao tal artifício. Há ainda elementos da matriz que não estão em nenhuma linha ou coluna escolhidas. Diremos que esses elementos não estão cobertos. Suponha que o menor elemento não coberto tem valor x > 0 (estamos trabalhando com uma matriz de números positivos). O programa subtrai x de todas as linhas não escolhidas e soma x a todas as colunas escolhidas. Dentre os elementos não cobertos, aparecerá um novo zero; os elementos cobertos por linha e coluna aumentarão o seu valor e os elementos cobertos apenas por linha ou por coluna não serão alterados. Isso significa que foi criado um novo zero, mas os zeros independentes não foram mudados porque são cobertos ou por uma linha ou por uma coluna.
b) Discussão da implementação
O autor propõe o uso de uma heurística quando m=n. Esta consiste em achar o menor elemento de cada coluna e subtraí-lo de todos os elementos dessa coluna. Dessa maneira garantimos que existe pelo menos um zero em cada coluna, o que pode economizar criações artificiais de zero mais adiante. Esta heurística pode ou não ser proveitosa, mas isso depende de cada caso.
b.2) Estruturas de dados utilizadas
O programa faz uso de vários vetores.
Para encontrar colunas atingíveis por caminhos do tipo (*) o programa usa o vetor unchosen_row, que armazena as linhas que possivelmente formarão tal caminho. Os vetores col_mate e row_mate indicam, repespectivamente, o cônjuge de uma linha e coluna. parent_row[c] = r indica uma coluna c escolhida (portanto casada) ligada a uma linha r por um zero simples, representa uma ligação r--c em um caminho do tipo (*). t representa o numero total de linhas em unchosen_row.
Na prática o programa não faz as operações matemáticas para forçar zeros diretamente na matriz, ele mantém os vetores row_dec e col_inc, que respectivamente representam o número subtraído de uma linha e adicionado a uma coluna. Os elementos da matriz A são acessado sempre desta forma: A(k,l) - row_dec[k] + col_inc[l]. Para computar rapidamente o menor elemento não coberto, em slack guardamos o elemento mínimo de cada coluna, e em slack_row guardamos a linha em que ele ocorre.
Na fase inicial, o programa porta-se de maneira diferente do que no passo geral. A única coisa que ele faz é tentar achar o máximo de casamentos possíveis. Procede da seguinte forma:
para cada linha {
b.4) Passo geral
Depois da fase inicial, podem ocorrer dois casos. Se todos os vértices estão casados, o problema esta resolvido. Caso contrário, ainda existem fileiras não escolhidas, e é isso que o passo geral tenta resolver.
Nessa situação, temos linhas no vetor unchosen_row que poderão levar a um aumento no número de casamentos, conforme diz o algoritmo Húngaro. O programa então tenta encontrar um caminho de aumento analisando tais linhas não escolhidas. Caso isso não seja possível, o programa aplica a técnica de criar um zero em uma fileira não escolhida, até termos um casamento a mais.
A cada passo geral, portanto, casamos dois vértices de qualquer forma.
b.5) Saída
A resposta são os elementos da matriz A que representam os casamentos, mas como padrão o programa devolve apenas o número de 'mems'. Se o usuário especificou -p, o programa imprime a matriz A e os elementos do casamento perfeito na tela. Caso tenha especificado -P, o programa gera uma saída gráfica em formato PostScript, com os pontos (casamentos) marcados na própria imagem digitalizada. Esses pontos são justamente os com soma total de brilho máxima e tais que não há mais que um deles em uma mesma linha ou coluna.
Uso excessivo de goto's. Alguns são até perdoáveis e não sabemos exatamente como e se o programa poderia ser escrito sem eles, mas no BCC aprendemos que eles devem ser evitados a todo custo...
b) Coisas que tivemos dificuldade em entender
Quase tudo! Apesar de já conhecermos por cima o algoritmo Húngaro, esta versão é realmente intrincada. O CWEB até ajuda entender os pedaços, mas na hora de juntar tudo vira um pesadelo. Knuth optou por usar uma implementação eficiente, mas difícil de entender; como o assign_lisa é somente um programa de demonstração, achamos que isso não seria necessário. Por esse motivo não conseguimos nos aprofundar na compreensão dos códigos nos blocos onde é implementado o algoritmo. Na verdade conseguimos compreender cada bloco individualmente, mas não nos foi possível enxergar todo o código funcionando.
Não há função alguma no programa, o que dificulta bastante a compreensão do código; o uso de blocos CWEB não deixa explícito, por exemplo, quais variáveis estão sendo alteradas (além, é claro, do uso de goto's entre blocos, que achamos horrível). Passos fundamentais do algoritmo estão escondidos, como por exemplo o trecho onde ele altera a matriz, permitindo tratar a maximização como minimização. Finalmente, o algoritmo poderia ter sido melhor explicado. Algumas definições, como a fileira que é 'escolhida', foram muito difíceis de entender.
c) Coisas que faríamos diferente...
Tentaríamos programar de maneira mais estruturada, utilizando funções e abolindo os goto's. E colocaríamos alguns comentários a mais, pelo menos nas passagens mais obscuras do código.
Escrito em 10 de abril de 2000.