IMPLEMENTAÇÃO/TESTES GREEDY BRUTE FORCE BACKTRACK

UNIVERSIDADE FEDERAL DO TOCANTINS
Programa de Pós-Graduação em Modelagem Computacional de Sistemas
Mestrado Profissional Interdisciplinar em Modelagem Computacional de Sistemas
Campus Universitário de Palmas

VALERIA MOTA
DIEGO DE CASTRO RODRIGUES

IMPLEMENTAÇÃO/TESTES
GREEDY
BRUTE FORCE
BACKTRACK

PALMAS - TO
2013

UNIVERSIDADE FEDERAL DO TOCANTINS
Programa de Pós-Graduação em Modelagem Computacional de Sistemas
Mestrado Profissional Interdisciplinar em Modelagem Computacional de Sistemas
Campus Universitário de Palmas

VALERIA MOTA
DIEGO DE CASTRO RODRIGUES

IMPLEMENTAÇÃO/TESTES
GREEDY
BRUTE FORCE
BACKTRACK

Trabalho apresentado como requisito parcial para aprovação na disciplina de Fundamentos da Modelagem Computacional, orientado pelo professor Dr. Marcelo Lisboa.

PALMAS - TO
2013
SUMÁRIO

1. INTRODUÇÃO 7
1.1 Justificativas 8
1.2 Objetivos 9
2. FUNDAMENTAÇÃO TEÓRICA 9
2.1 Método Greedy (Guloso) 9
2.2 Método Brute Force (Força Bruta) 10
2.3 Método Backtrack 11
3. METODOLOGIA 12
4. RESULTADOS EXPERIMENTAIS 13
4.1 Analise dos Métodos 15
4.2 Analise Estatística 17
4.2.1 Média, variância dos dados Amostrais 17
4.2.1 Histogramas 19
4.2.2 Gráfico Quantil de dados da amostra 21
4.2.3 Comparar a distribuição dos dados contra a distribuição dos dados Força bruta, Greedy e Backtrack usando QQ-PLOT 22
4.2.4 ANOVA 23
5. CONCLUSÃO 24
6. REFERENCIAS 25

LISTAS DE FIGURAS Figura 1 – Representação Algébrica Problema da Mochila (FINCATTI, 2009, pag. 7) 7
Figura 2 – Arvore de Pesquisa Binária (FINCATTI, 2009, pag. 8) 12
Figura 3 – Dados para realização dos testes arquivo ex04.dat 13
Figura 4 – Dados gerados a partir do código 14
Figura 5 – Dados dos arquivos organizados em tabela 14
Figura 6 - Solução dos Métodos (força bruta, retrocesso e gulosa) 15

LISTAS DE GRÁFICOS