No decorrer do curso, é muito provável que todos precisaram, em algum momento, trabalhar com o conceito de caminhamento em matrizes de forma gulosa, ou seja, optando por um dado caminho e não mais olhando para trás ou para decisões já tomadas. Neste trabalho vamos caminhar por um conjunto de matrizes fornecidas como entrada, objetivando encontrar o maior valor final segundo um conjunto de regras preestabelecidas, objetivando com isso: (1) revisar os conceitos de programação básica com matrizes, (2) iniciar um cenário de questionamentos para identificar se realmente a implementação realizada é a forma otimizada e; (3) iniciar uma busca para uma boa estruturação de código.
Os algoritmos gulosos, de uma maneira geral, buscam a melhor opção disponível no momento, a fim de conseguir atingir uma solução ótima global. Sem se importar com as consequências das decisões tomadas, os algoritmos gulosos nunca reconsideram decisões já feitas, os tornando bastante eficientes, devido a sua simplicidade.
O algoritmo deste programa é considerado guloso porque ele sempre busca os elementos que possuem maior valor, sem refazer suas decisões. No arquivo main.c, o programa tenta abrir o arquivo "input.data" no diretório atual (linha 6). Caso a tentativa falhe, o programa fecha com exit code 1 (linhas 8-11). Caso contrário, a primeira string do programa é lida e armazenada como o tamanho da matriz (linha 13). O tamanho é então usado para alocar a memória dinâmica para o ponteiro mat (linha 15).
Para mostrar um exemplo de execução do programa, foi utilizado o arquivo input.data. A matriz testada, de tamanho quadrado quarto por quatro (4x4), possuia apenas números positivos. É importante destacar que a matriz não deverá apresentar nenhum valor zero, pois este valor será utilizado para orientar o algoritmo quando este for percorrer a matriz. A entrada utilizada foi a seguinte:
| 478 | 664 | 153 | 268 |
| 903 | 762 | 253 | 590 |
| 707 | 409 | 87 | 351 |
| 485 | 564 | 114 | 584 |
Em seguida, o programa entra em um loop (linhas 17-28) que continua até que a leitura do arquivo chegue ao fim. Os valores das matrizes foram lidos e atribuídos aos elementos da matriz (linha 20). Após ler a primeira matriz e, caso o arquivo não tenha chegado ao fim, os valores da nova matriz são sobrescritos na matriz mat.
No arquivo matrix.c, a função greedyAlg faz a verificação da matriz a partir de um loop que continua até que o programa chegue até a última linha (linhas 11-39). O algoritmo começa a verificar a matriz a partir do elemento disposto na primeira coluna da primeira linha. Com isso, ele procura verificar qual é o maior valor dentre os elementos das colunas próxima e anterior, para a linha de baixo e para as diagonais para baixo. O programa avalia qual é o maior valor dentre cinco direções na seguinte ordem:
- A linha de baixo
- A coluna anterior
- A diagonal baixo-esquerda
- A próxima coluna
- A diagonal baixo-direita
O algoritmo leva em conta o maior valor que aparecer primeiro. Por exemplo, em caso de empate entre os valores da linha de baixo e da coluna anterior, o algoritmo daria prioridade à próxima linha, pois ele possui maior prioridade. Segue abaixo uma representação mais visual dos possíveis caminhos em que o algoritmo pode andar.
| ⇐ | ⇒ | |
| ⇙ | ⇓ | ⇘ |
Determinado o maior valor, o algoritmo move para a direção de maior valor, marcando o valor anterior como zero (linha 35), para que o algoritmo não possa voltar a esse elemento.
Em seguida, é chamada a função joystick (linhas 52-72), onde um switch case define, a partir de um argumento char passado para a função, para qual direção o algoritmo deve se mover.
Foram acrescentadas duas condições (linhas 15 e 25), a fim de garantir que o programa não exceda os limites da matriz, causando assim um erro na execução do programa. As condições são:
- Se a variável j for igual a 0, o programa não tenta acessar uma coluna anterior
- Se a variável i + 1 for igual a variável mat_sz, o programa não tenta acessar a próxima coluna
Assim que o algoritmo chega a última linha da matriz, é realizado mais um loop para que o algoritmo chegue até a última coluna (linhas 41-45). Portanto, o programa apenas move para a próxima coluna até o fim do loop. Ao fim, a função retorna a soma do caminho. Segue abaixo o caminho percorrido pelo algoritmo:
| 664 | 153 | 268 | |
| 253 | 590 | ||
| 409 | 87 | 351 | |
| 485 |
O resultado da soma foi 4112. Vale-se destacar que o programa imprime, para o exemplo dado, dois resultados: o local e o global. O resultado local refere-se ao resultado da soma do caminho percorrido pela matriz, enquanto o global mostra a soma das somas das matrizes. Como o arquivo input.data possui apenas uma matriz, os resultados local e global possuem o mesmo valor. Segue abaixo as direções tomadas pelo algoritmo:
| ⇓ | |||
| ⇒ | ⇙ | ||
| ⇘ | |||
| ⇒ | ⇒ | ⇒ |
O exemplo aqui exposto foi compilado com o GNU Compiler Collection (gcc) versão 4:11.2.0-1ubuntu1, no sistema operacional Ubuntu 22.04.2 LTS (Jammy Jellyfish). O computador possuia uma placa-mãe ASUS AM1M-A/BR, 8 GB de memória RAM DDR3 e um processador AMD Athlon 5150 (arquitetura x86_64).
O algoritmo do caminho guloso disponibilizado possui um arquivo Makefile que realiza todo o procedimento de compilação e execução. Para tanto, temos as seguintes diretrizes de execução:
| Comando | Função |
|---|---|
make clean |
Apaga a última compilação realizada contida na pasta build |
make |
Executa a compilação do programa utilizando o gcc, e o resultado vai para a pasta build |
make run |
Executa o programa da pasta build após a realização da compilação |