Este repositório apresenta a solução implementada para um desafio da disciplina de Algoritmos e Estruturas de Dados. Há com isso o propósito de testar a implementação de um algoritmo guloso que faça pesquisa em uma matriz. Para melhor entendimento deste trabalho, considere as sentenças à seguir:

• $K$ - Número de matrizes de entrada.

• $N$ - Ordem de uma matriz tal que $N \in \mathbb{Z}$ e $N\geq 0$.

• $i$ - Índice de uma linha que pertence à uma matriz específica, também pode ser abstraído como deslocamento na vertical, tal que $i \geq 0$ e $i \in \mathbb{Z}$.

• $j$ - Índice de uma coluna que pertence à uma matriz específica, também pode ser abstraído como deslocamento na horizontal, tal que $j \geq 0$ e $j \in \mathbb{Z}$.

• $a_{ij}$ - Elemento encontrado quando há deslocamento até a linha de índice $i$ e coluna de índice $j$.

• Nomes de diretórios, ou arquivos serão referênciados da seguinte forma: Nome.txt ou Diretório_2.

• Nomes de comandos digitados no terminal,funções ou variáveis serão referênciados da seguinte forma: touch main.cpp, make run, ShowResults(), variableA.

• Para as Figuras de 1 à 10, considere a legenda de cores:

  • Azul:Uma posição futura possível.
  • Cinza: Uma posição futura impossível.
  • Laranja: Posição atual ou inicial.
  • Rosa: Posição futura escolhida.
    
    

A problemática proposta incita os alunos da disciplina a desenvolverem um programa que leia $K$ matrizes de ordem $N$. Considerando essa proposição algumas exigências de desenvolvimento solicitadas foram:

• As matrizes deverão estar préviamente organizadas para processamento.

• A pesquisa ou percorrimento na matriz iniciará à partir da entrada de dados do usuário ou de um arquivo. Esta entrada é o ponto de onde caminhada ou pesquisa pela matriz se inicia.

• Os movimentos válidos para deslocamento pela matriz são listados à seguir e visualizados de azul na Figura 1, considerando o ponto de partida atual sendo o elemento colorido de laranja:

  • Avançar para a próxima coluna.

  • Retroceder a coluna anterior.

  • Avançar para a linha de baixo.

  • Avançar em diagonal esquerda, ou direita para baixo.

Figura 1 - Movimentos possíveis

Fonte: Construção pelo autor¹.
____________________________________________
¹Criada usando o Google Sheets, Disponível em Planilha.

• Os movimentos devem ser realizados em direção às casas adjascentes de maior valor possível. No caso da Figura 1 essa opção representa o elemento em $i=1$ e $j=4$, portanto o próximo movimento se desloca até $a_{14}$.
• Caso haja um valor em comum entre as direções de maior valor, é necessário que uma regra de caminhamento seja estabelecida. E que esta enquanto padrão seja a melhor decisão de caminhamento.
• Ao ter como posição atual o elemento de uma matriz posicionado na última linha e coluna simultâneamente, ou seja o elemento na coordenada de maior valor referente a $i$ e $j$, tais que, $i,j \in \mathbb{Z}$ onde $ 0 \leq i\leq N$ e $0 \leq j \leq N$, considera-se que a matriz foi percorrida até o final com isso o programa recebe uma nova entrada referênte ao ponto inicial de caminhada para a próxima matriz. Caso o programa tenha lido a última matriz, isso não acontece.
  
  

Os arquivos para funcionamento do projeto são:

• input.data : Um arquivo que armazena na sua primeira linha a ordem das matrizes que estão dispostas nas linhas subsequentes.

Figura 2 - input.data

Fonte: Captura de tel feita pelo autor².
____________________________________________
²Captura de tela do computador do autor. Disponível em: Imagem 2.

• Makefile : Controla a geração dos executáveis e compilação dos mesmos(FREE SOFTWARE FOUNDATION, GNU make, 2023).
• functions.cpp : Contém as funções criadas para execução no main.cpp.
• structures.hpp : Contém as estruturas e chamadas de bibliotecas utilizadas no programa.
• main.cpp : Contém uma série de funções e declaração de variáveis que façam com que a busca pela matriz seja realizada devidamente.
  
  

A leitura das entradas do arquivo input.data são realizadas em 2 etapas, na primeira etapa é executada a função SizeRecon.

A função SizeRecon é responsável por ler a primeira linha do arquivo de entrada e retornar à alguma variável o valor de $N$, este valor serve para todas as $K$ matrizes contidas no arquivo input.data.

Com $N$ armazenada na variável size o código, uma estrutura de tamanho $N$ do tipo MatrixElement denominada FinalMatrix é criada para que os valores do arquivo input.data sejam alocados em uma variável. A estrutura do tipo MatrixElement nesse caso será uma matriz com variávies do tipo unsigned short int como elementos $a_{ij}$.

Para a leitura das $K$ matrizes um laço percorre o arquivo armazenando cada elemento identificado em uma posição da estrutura FinalMatrix, essa mesma estrutura é reiniciada assim que: MatrixLines = $N-1$ . Considerando que MatrixLines é uma variável criada para armazenar o número de linhas preenchidas com entradas do arquivo.

Diante do que foi narrado, o programa recebe do usuário as coordenadas de $i$ e $j$ para inicializar a pesquisa através da martriz partindo do elemento $a_{ij}$. A entrada de i e j é requisitada através de CoordinateDefinition.

O programa usa $a_{ij}$ como posição em que está no presente, ele verifica a resposta para a seguinte pergunta:

• As posições adjascentes correspondem à espaços da memória alocados pela matriz?

A validação citada ocorre através do seguinte modo:

• Criação de hipóteses dentro de variáveis booleanas,sendo o resultádo dessas variáveis é dependente da posição atual.As variáveis booleanas criadas tem os nomes de pontos cardeais em inglês, são elas W,SW,S,SE,E e podem ser verdadeiras ou falsas de maneiras diferentes tornando diversos caminhos possíveis.

Por fim pode-se abstrair a situação acima nas seguintes ilustrações, considerando que o elemento de cor laranja é o local atual:

Figura 3 - 5 possíveis caminhos

Fonte: Construção pelo autor³.
____________________________________________
³Criada usando o Google Sheets, Disponível em Planilha.

Após analisar as hipóteses, a decisão de qual é o melhor caminho a seguir é feita considerando o $a_{ij}$ de maior valor, enquanto esta posição de maior valor seja diferente da última posição. Isso significa que em nenhum momento o próximo passo pode se o passo anterior, afinal isso faria com que duas casas próximas com o maior valor possível fossem as únicas escolhidas.

Para buscar a maior direção válida, o programa decide quais são os pontos cardeais válidos, à depender disso ele executa uma das seguintes funções possíveis:

• FivePossibleWays: Verifica qual o maior dentre 5 elementos, tendo uma posição de coordenadas $i$ e $j$ diferentes da posição passada. Exemplo na Figura 4.

Figura 4 - Maior valor entre 5

Fonte: Construção pelo autor⁴.
____________________________________________
⁴Criada usando o Google Sheets, Disponível em Planilha.

• SouthEastPossibleWays: Verifica qual o maior dentre 3 elementos, tendo uma posição de coordenadas $i$ e $j$ diferentes da posição passada. Estes elementos estão ao Sul, Leste ou Sudeste do $a_{ij}$ atual. Exemplo na Figura 5.

Figura 5 - 3 possíveis caminhos para Sul e Leste.

Fonte: Construção pelo autor⁵.
____________________________________________
⁵Criada usando o Google Sheets, Disponível em Planilha.

• SouthWestPossibleWays: Verifica qual o maior dentre 3 elementos, tendo uma posição de coordenadas $i$ e $j$ diferentes da posição passada. Estes elementos estão ao Sul, Oeste ou Sudoeste do $a_{ij}$ atual. Exemplo na Figura 6.

Figura 6 - 3 possíveis caminhos para Sul e Oeste.

Fonte: Construção pelo autor⁶.
____________________________________________
⁶Criada usando o Google Sheets, Disponível em Planilha.

Existem alguns casos particulares onde teremos os seguintes movimentos:

• Quando a posição atual como $a_{ij}$ tem seus valores de $i = N-1$ e $j =N-1 $, ou seja, quando a posição atual for a última posição.Nesse caso a pesquisa na matriz é finalizada.

• Quando a posição atual como $a_{ij}$ tem seus valores de $i = N-1$ com $j$ sendo qualquer valor, ou seja, quando a posição atual está na última linha da matriz. Nesse caso o único movimento possível é avançando em colunas, ou seja de forma que o próximo passo tenha o $i$ constante e o $j=j+1$ até que se chegue à última casa. Isso acontece pelo fato de que ao chegar à última linha realizar um movimento que não siga essas diretrizes resultará na impossibilidade de continuar caminhando sem ter chegado ao final da matriz.

• Em casos de execução das funções: SouthWestPossibleWays, SouthEastPossibleWays ou FivePossibleWays onde os valores de duas ou mais casas adjascentes são iguais, haverá sempre preferência pelas casas adjascentes de maior valor na seguinte ordem:

  • 1º Escolha do elemento com $i = i+1$ e $j = j$, ou seja, elemento abaixo.
  • 2º Escolha do elemento com $i = i+1$ e $j = j+1$, ou seja, elemento abaixo na diagonal direita.
  • 3º Escolha do elemento com $i = i+1$ e $j = j$, ou seja, à direita.
  • 4º Escolha do elemento com $i = i+1$ e $j = j-1$, ou seja, à direita.

Em função de representar é realizado pelo algoritmo diante da entrada no arquivo input.data, observe as imagens abaixo. Considere que nas saídas, números diferentes de 999 repersentam a ordem da caminhada realizada, sendo 999 uma forma de representar localizações fora do trajeto:

"Um algoritmo guloso sempre faz a escolha que parece ser a melhor no momento em questão. Isto é, faz uma escolha localmente ótima, na esperança de que essa escolha leve a uma solução globalmente ótima."
Algoritmos: teoria e prática, de Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest e Clifford Stein, tradução da 3ª edição

Reavaliando a Implementação de um Algoritmo Guloso

Com o intuito de preparar os alunos para a disciplina de Algoritmos e Estruturas de Dados dentro de um contexto onde os mesmos tivessem de ser avaliados em um período limitado de tempo, o desenvolvimento do desafio será avaliado diante da documentação e tentativa de construir um algoritmo guloso que resolvesse o problema apresentado.

Contudo, é importante ressaltar que a implementação de algoritmos gulosos necessita de um estudo aprofundado em outros cenários antes de ser implementado.

Considerando isso, são propostos por Cormen(2012) os Elementos da Estratégia Gulosa, ou seja, a projeção de algoritmos gulosos conta com a seguinte sequência de etapas:

1. "Projetar o problema [...] como um problema no qual fazemos uma escolha e ficamos com um único subproblema para resolver"(CORMEN, 2012, p.354).
   
   
2. "Provar que sempre existe uma solução ótima para o problema original que usa a escolha gulosa, de modo que a escolha gulosa é sempre segura"(CORMEN, 2012, p.354)."
   
   
3. "Demonstrar subestrutura ótima, mostrando que, tendo feito a escolha gulosa, o que resta é o subproblema com a seguinte propriedade: se combinamos uma solução ótima para o subproblema com a escolha que fizemos, chegamos a uma solução ótima para o problema original"(CORMEN, 2012, p.354).
   
   

## Compilação e Execução Para compilação e execução do código é necessário que seja criado um arquivo Makefile. Para uso deste arquivo da forma correta, siga as diretrizes de execução abaixo:

Comandos	Funções
make clean	Deleta o arquivo executável e todos os arquivos objetos do diretório. (FREE SOFTWARE FOUNDATION, GNU make, 2023)
make	Compila diferentes partes do programa através do g++ e cria um arquivo executável na pasta build.
make run	Executa o programa da pasta build após a realização da compilação. (PIRES, MICHEL, 2023)

Ambiente de desenvolvimento:

O código foi desenvolvido e testado no seguinte ambiente de desenvolvimento:

Peças	Especificações
Processador	Intel(R) Core(TM) i5-3340M CPU @ 2.70GHz
Memória RAM	8 GB
Sistema Operacional	Linux fedora 6.2.7-100.fc36.x86_64

Referências

[1] CORMEN, T. H. et al. Introduction to Algorithms, third edition. [s.l.] MIT Press, 2009. Acessador em 20 de Março de 2023.

[2] PIRES, MICHEL - Repositório GitHub, @mpiress: GenerateDataToMatrix - Disponível em: https://github.com/mpiress/GenerateDataToMatrix/blob/main/src/mat.h. Acessado em 15 de Março de 2023.

[3] GNU make. Disponível em: https://www.gnu.org/software/make/manual/make.html. Acessado em 21 de Março de 2023.

[4] GNU Make. Disponível em: https://www.gnu.org/software/make/. Acesso em: mar. 23DC.

‌

‌

Contato

✉️ [email protected]