Introdução | Sobre | Proposta | Execução | Conclusão | Licença
Inteligência Artificial tem sido muito utilizada para a resolução de diversos problemas, desde muitos complexos, como reconhecimento de variantes de alto risco da covid-19 até problemas mais simples, como a resolução de quebra-cabeças.
Apesar disso, as técnicas e abordagens são muito semelhantes, diferenciando (algumas situações) os algoritmos e suas técnicas necessárias. Redes Neurais, por exemplo, poderiam resolver o quebra-cabeças, mas exigem uma enorme quantidade de dados, a ter uma maior velocidade após aprender. Neste projeto, são implementadas a busca em profundidade (dfs) e a busca em largura (bfs), as quais apesar de não exigirem uma enorme quantidade de dados, a longo prazo, podem ser menos eficientes, mas resolvem o problema.
O trabalho proposto na disciplina de Inteligência Artifical pela professora Dra. Cláudia Aparecida Martins consiste em resolver um quebra-cabeças de 8 peças, com um espaço em branco para deslocar as peças, movendo cada peça possível a partir de um estado inicial até o estado desejado (final). Um exemplo disso está na imagem abaixo, com respectivamente o estado inicial e o final.
Além disso, deseja-se saber qual foi a solução encontrada (passos) e o custo da busca em número de passos, sendo que não podem haver repetições de estados do quebra-cabeças.
A diferença entre essas duas últimas é que o custo da solução é quantos passos mínimos são necessários para que seja possível alcançar a solução, enquanto o custo da busca representa o número total de passos até encontrar a solução.
Tanto a implementação da bfs quanto da dfs podem ser feitas de diferentes formas considerando diferentes situações. Um dos principais pontos a serem observados e que precisa de atenção é a não repetição dos estados, para evitar ficar preso na busca e não encontrar uma solução. Esse ponto resolvi da seguinte forma:
- Cada estado da matriz é uma string.
- Todos os estados (únicos) são armazenados.
- A busca ocorre somente se ao mover uma peça o estado já não ocorreu antes.
- O estado considera as peças como se o quebra-cabeças fosse achatado (1-dimensão).
O problema foi solucionado utilizando C++17, considere utilizar a mesma versão para não ter comportamentos inesperados para compilar.
O programa foi desenvolvido no windows, apesar de testado para compilar UNIX, algumas distribuições podem ter algum erro. Os usuários de MAC que tiverem problemas também podem criar uma issue alertando.
A busca em profundidade demonstrou ser bem mais eficiente que a busca em largura, isto pois não precisa armazenar toda a árvore de estados para checar a solução.
A busca em largura devido a checar cada possibilidade de movimento, consegue determinar a solução com menor custo, mas demora muito mais que a busca em profundidade para isso.
Distribuído sobre a licença MIT. Veja LICENSE para mais informações.