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

Acesso à informação
Transparência Pública

© 2013 Universidade Federal do Espírito Santo. Todos os direitos reservados.
Av. Fernando Ferrari, 514 - Goiabeiras, Vitória - ES | CEP 29075-910