Heurísticas de Busca de Grafos
Resumo: O GROOVE é uma ferramenta para análise/verificação formal de sistemas, baseada no conceito de transformação de grafos. Essa modificação de grafos é determinada por um conjunto de regras de transformação. A funcionalidade principal do GROOVE é a exploração exaustiva de todas as possíveis sequências de aplicação das regras de transformação de forma a enumerar todos os possíveis estados do sistema modelado (exploração do espaço de estados). No entanto, há casos onde uma busca exaustiva não é desejável e somente um grafo alvo deve ser encontrado. Técnicas de otimização bastante utilizadas envolvem heurísticas de busca no espaço de estados de forma a encontrar caminhos que levam ao estado (grafo) alvo.
Os objetivos desse projeto são estudar, propor e implementar heurísticas de busca para grafos na ferramenta GROOVE. Após a implementação ser concluída, experimentos computacionais serão realizados para ilustrar as ganhos de performance obtidos com os novos algoritmos.
Os resultados esperados desse projeto são: 1) o desenvolvimento de uma extensão da ferramenta computacional GROOVE; e 2) publicações em anais de congressos científicos da área de computação/otimização.
Data de início: 01/06/2013
Prazo (meses): 24