Problema da mochila em java

Disponível somente no TrabalhosFeitos
  • Páginas : 20 (4806 palavras )
  • Download(s) : 0
  • Publicado : 25 de fevereiro de 2013
Ler documento completo
Amostra do texto
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 emModelagem 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 1.2 Justificativas .................................................................................................................. 8 Objetivos....................................................................................................................... 9

2.

FUNDAMENTAÇÃO TEÓRICA ........................................................................................ 9 2.1 2.2 2.3 Método Greedy (Guloso) .............................................................................................. 9 Método Brute Force (Força Bruta).............................................................................. 10 Método Backtrack ....................................................................................................... 11

3. 4.

METODOLOGIA ............................................................................................................... 12 RESULTADOS EXPERIMENTAIS .................................................................................. 13 4.1 4.2Analise dos Métodos ................................................................................................... 15 Analise Estatística ....................................................................................................... 17

4.2.1 Média, variância dos dados Amostrais...................................................................... 17 4.2.1 4.2.2Histogramas......................................................................................................... 19 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 5. 6. ANOVA ................................................................................................................. 23

CONCLUSÃO .................................................................................................................... 24 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 apartir 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

Gráfico 1 – Resultado da solução dos métodos...
tracking img