Banca de DEFESA: ELDER GONÇALVES PEREIRA

Uma banca de DEFESA de MESTRADO foi cadastrada pelo programa.
DISCENTE: ELDER GONÇALVES PEREIRA
DATA: 21/03/2014
HORA: 14:00
LOCAL: Auditório do CCET
TÍTULO:

 O Problema do Hiker Dice em Tabuleiro Compacto: Um Estudo Algoritmico

PALAVRAS-CHAVES:

O problema do Hiker Dice. Algoritmos Metaheurísticos

PÁGINAS: 110
GRANDE ÁREA: Ciências Exatas e da Terra
ÁREA: Ciência da Computação
SUBÁREA: Teoria da Computação
ESPECIALIDADE: Análise de Algoritmos e Complexidade de Computação
RESUMO:

O presente trabalho apresenta algoritmos que buscam as melhores soluções nos tabuleiros de ordem n e sem buracos (tabuleiro compacto) no problema Hiker Dice. Na Ciência da Computação é crescente o interesse em jogos lógicos como o Hiker Dice, devido à dificuldade de solução que esses jogos demandam, bem como suas aplicações em modelos para problemas do mundo real. A pesquisa presentemente relatada, modela o problema através de Grafos, e propõe duas classes de algoritmos de solução. A primeira classe, pertencente aos algoritmos exatos, é constituída por um algoritmo em backtracking aparelhado com um retorno realizado através de regras lógicas e limite da melhor solução encontrada. A segunda classe de algoritmos é constituída por metaheurísticas do tipo Computação Evolucionária, Busca Local Aleatorizada e GRASP (Greed Randomized Adaptative Search). Para os algoritmos metaheurísticos foram criados três operadores específicos da seguinte forma: de reestruturação, de recombinação com duas soluções e construtivo guloso aleatório. O algoritmo exato foi testado em tabuleiros de ordem 4 a 7 esgotando a possibilidade de tratamento computacional dos casos maiores em virtude da explosão em tempo de processamento. As metaheurísticas foram testadas nos tabuleiros 8x8 até 9x9. O processo de afinamento das metaheurísticas envolveu a consideração de até três diferentes parâmetros, adotando-se a configuração de melhor desempenho no tabuleiro 7x7 através do teste estatístico não-paramétrico (U de Mann-Whitney). Nesse processo de avaliação dos parâmetros foram utilizados os resultados obtidos nos algoritmos exatos. Os algoritmos afinados foram então aplicados na solução dos tabuleiros 8 e 9 e comparados pelo mesmo teste estatístico não-paramétrico. A comparação dos algoritmos sugere um melhor potencial de desempenho para o algoritmo de busca local aleatorizada. Ao final do documento é proposta a conclusão da pesquisa com a ampliação dos casos teste e o aperfeiçoamento dos algoritmos propostos.

MEMBROS DA BANCA:
Presidente - 1149561 - MARCO CESAR GOLDBARG
Interno - 1201268 - ELIZABETH FERREIRA GOUVEA
Externo ao Programa - 348094 - ILONEIDE CARLOS DE OLIVEIRA RAMOS
Externo à Instituição - HENRIQUE PACCA LOUREIRO LUNA - UFAL
Externo à Instituição - MYRIAM REGATTIERI DE BIASE DA SILVA DELGADO - UTFPR