Helena Muniz Nogueira

Formação complementar

Idiomas

Áreas de atuação

Participação em eventos

Projetos de pesquisa

• 2019 - 2020

  Algoritmos em Grafos para o Problema do Distritamento Político, Descrição: Neste trabalho foi desenvolvido um algoritmo de distritamento de arestas aplicado a um grafos. O grafo trabalhado neste estudo é conexo e não direcionado, nele haverá vértices que foram tratados como depósito. O algoritmo será um algoritmo expansão, expandindo a partir dos vértices de depósitos, trabalhado com auxílio de algumas estruturas de dados sendo, elas heap de depósitos, lista de vértices que estão naquele distrito, lista de arestas selecionadas, heap com todas as possíveis arestas a serem selecionadas e hash com todas as arestas. A heap de depósitos é base da solução, pois a estratégia se baseia em um expansão a partir de cada depósito, para que assim possam ser formados os distritos. Cada posição dessa lista de depósito estarão ligadas a outras três estruturas sendo elas lista de vértices que estão naquele distrito, lista de arestas selecionadas e heap com todas as possíveis arestas a serem selecionadas. Cada posição terá um atributo com o tamanho da rota já definida a cada distrito e por esse atributo será ordenada heap, tendo sempre prioridade de expansão o distrito com menor rota. A lista de vértices que estão naquele distrito tem como ideia guardar todos os vértices alcançados por aquele distrito. A lista de arestas selecionadas tem como objetivo salvar a rota selecionada de cada distrito e também impossibilitar que uma aresta seja selecionada novamente. A heap com todas as possíveis arestas a serem selecionadas têm como base facilitar a expansão do distrito apresentando a menor aresta a ser selecionada para que consigamos a menor rota. Nessa estrutura cada posição do vetor da heap tem três variáveis, uma variável salva o vértice inicial, a segunda variável salva um vértice que está ligado ao vértice inicial e a terceira variável é a distância desse vértice. Ela será ordenada pela terceira variável. Nessa estrutura só terá as arestas possíveis de expansão para aquele distrito. A hash com todas as arestas possui todas as arestas do grafo que ainda não foram selecionadas. O trabalho teve como base a pesquisa ?A novel model for arc territory design: promoting eulerian districts? da autora Gabriela García-Ayala, e também foi utilizado seu banco de dados para testes.. , Situação: Concluído; Natureza: Pesquisa. , Alunos envolvidos: Graduação: (1) / Especialização: (0) / Mestrado acadêmico: (0) / Mestrado profissional: (0) / Doutorado: (0) . , Integrantes: Helena Muniz Nogueira - Integrante / Mayron Cesar de Oliveira Moreira - Coordenador.