Use este identificador para citar ou linkar para este item:
http://repositorio.ufc.br/handle/riufc/49589| Tipo: | TCC |
| Título: | Uma abordagem heurística ao problema de infecção em grafos submetido à regras P3 e P4 |
| Autor(es): | Oliveira, Kainan Faria de. |
| Orientador: | Santos, Marcio Costa |
| Palavras-chave: | Otimização;Infecção de Grafos;Regras de infecção |
| Data do documento: | 2019 |
| Citação: | OLIVEIRA, Kainan Faria de. Uma abordagem heurística ao problema de infecção em grafos submetido à regras P3 e P4. 2019. 43 f. Trabalho de Conclusão de Curso ( Graduação em Ciência da Camputação). - Universidade Federal do Ceará, Campus de Russas, Russas, 2019. |
| Resumo: | O problema de infecção em grafos, pode ser visto como um conjunto de vértices infectados S espalhando um vírus em um grafo G = (V;E). Nos problemas de infecção em grafos, vértices não infectados serão infectados em um tempo i se respeitarem as regras de infecção previamente definidas de acordo com o problema no tempo i - 1 (DRAIEF; GANESH, 2010). Foi estudado o problema de determinar o menor conjunto de vértices infectados do grafo que consiga infectar todo o grafo. É proposto um modelo matemático relativo a cada regra de infecção estudada, no caso, P3 e P4, depois partiu-se para a implementação dos algoritmos utilizando a biblioteca PuLP da linguagem de programação Python para manuseio do solver ILOG IBM CPLEX. Ao final das implementações, pode-se perceber que o modelo obteve resultados promissores. Também é apresentado uma heurística construtiva para o problema que também foi testada com resultados promissores, obtendo muitas vezes, resultados que superam os valores obtidos nos algoritmos exatos implementados, em relação a instâncias com quantidades elevadas de vértices |
| Abstract: | The graph infection problem can be seen as a set of S infected vertices spreading a virus on a graph G = (V;E). In graph infection problems, uninfected vertices will be infected at a time i if they comply with the infection rules previously defined according to the time problem i - 1 (DRAIEF; GANESH, 2010). We studied the problem of determining the smallest set of infected graph vertices that can infect the entire graph. A mathematical model is proposed for each infection rule studied, in this case, P3 and P4, and then we started to implement the algorithms using the Python programming language PuLP library for handling the ILOG IBM CPLEX solver. At the end of the implementations, it can be seen that the model obtained promising results. Also presented is a constructive heuristic for the problem that was also tested with promising results, often obtaining results that exceed the values obtained in the optimal algorithms implemented, in relation to instances with high quantities of vertices.. |
| URI: | http://www.repositorio.ufc.br/handle/riufc/49589 |
| Aparece nas coleções: | CIÊNCIA DA COMPUTAÇÃO - RUSSAS - Monografias |
Arquivos associados a este item:
| Arquivo | Descrição | Tamanho | Formato | |
|---|---|---|---|---|
| 2019_tcc_oliveirakf.pdf | 704,49 kB | Adobe PDF | Visualizar/Abrir |
Os itens no repositório estão protegidos por copyright, com todos os direitos reservados, salvo quando é indicado o contrário.