Carla Rezende B. Bonin, Gustavo M. Novaes, Mauro Lúcio Ruy de Almeida Filho
Alex Fernandes da Veiga Machado (Orientador)
Centro Federal de Educação Tecnológica de Minas Gerais
Leopoldina, MG O projeto de Carla, Gustavo e Mauro Lúcio de Leopodlina, Minas Gerais, foi um dos vencedores da sexta edição da FEBRACE, que irá representar o Brasil na ISEF 2008. Eles enviaram este texto especialmente para o JJ. Confira!
Título original do projeto: “Heurísticas Para Resolução de Problemas NP-Completos no Domínio de Jogos”
Gustavo, Carla, Mauro Lúcio. Foto: Gerardo Lazzari
Este projeto baseia-se em viabilizar uma melhor solução para jogos eletrônicos de raciocínio fazendo uso da estrutura conhecida como árvore de buscas, e tem como principal objetivo em sua utilização no domínio de jogos, comparar a performance e a precisão das heurísticas (são idéias, propostas para solucionar determinado problema): Algoritmo Genético (AG), GRASP (Procedimento de Busca Adaptativa Gulosa e Randomizada) e AG-GRASP (trata-se de uma junção das melhores partes de cada para gerar uma heurística ainda melhor) para encontrar o conjunto solução de movimentos em um jogo de raciocínio (quebra-cabeças).
A principal contribuição consiste na proposta de um novo método baseado em uma modelagem integrando a estrutura de buscas do Algoritmo Genético com a geração elitista de soluções iniciais do GRASP. Outro ponto que se pode destacar deste projeto é a inédita implementação das heurísticas GRASP e AG-GRASP no ramo de jogos atuando como uma possível solução para a resolução de tais problemas.
Desse modo, foi criado o software “Kombat Heurístico” cujo principal objetivo era o de possibilitar o desenvolvimento e a implementação das heurísticas Algoritmo Genético, única utilizada no segmento de jogos, GRASP e AG-GRASP por meio da linguagem FreePascal, fazendo uso do programa Lazarus. O desenvolvimento com êxito de tal software permitiu também realizar inúmeros testes, que acabaram por gerar resultados de importância significativa visto que foi possível concluir, que as duas heurísticas, GRASP e AG-GRASP, apresentam resultados muito superiores em relação aos obtidos com Algoritmo Genético, tanto em velocidade final, quanto em precisão de busca de soluções. Assim sendo, o projeto conclui efetivamente seu objetivo: o de propor e desenvolver duas novas heurísticas capazes de resolver problemas NP - Completos no domínio de jogos, e que ainda apresentam resultados excepcionalmente melhores do que os que eram obtidos até então com o Algoritmo Genético.
Uma das contribuições proporcionadas por esta pesquisa foi a redução no tempo gasto com o processamento de dados, naquilo que diz respeito a encontrar soluções para problemas gerados em jogos de raciocínio.
Conquistas deste projeto
- Publicação na SBGames 2007 (VI Simpósio Brasileiro de Jogos para Computador e Entretenimento Digital), realizado em novembro na cidade de São Leopoldo, Rio Grande do Sul.
- Os alunos deste projeto foram contemplados pela Intel com o prêmio por excelência em Ciência da Computação e foram premiados pela Mu Alpha Theta pela aplicação da Matemática no contexto do projeto.
- 2º Lugar na Categoria Ciências Exatas e da Terra (FEBRACE 2008)
- Selecionado para participar da Intel/ISEF (Feira Internacional de Ciências e Engenharia) que ocorrerá em maio na cidade de Atlanta, Estados Unidos, por ter sido o melhor projeto em grupo da região Sul/Sudeste (exceto São Paulo).
Envie esta notícia para um amigo
|
