Complexidade de algorítimos

Experimento de Complexidade de algoritmos

Alunos: Carlos Felipe Melies
Leonardo Antonio Pinheiro
Paulo Eduardo Martins

Experimento de Complexidade de Algoritmos 1.Objetivo O objetivo do experimento sera analisar a variação tempo média de tempo causada pela quantidade de entradas utilizadas para resolver o problema do Caixeiro Viajante utilizando os algoritmos de vizinho mais próximo e programação dinâmica. 2.Método Os tempos serão medidos em um software programado pelo grupo onde o mesmo encontra o menor caminho entre as cidades voltando a mesma (Um grafo representado por uma matriz de adjacência). Serão realizados 50testes com uma matriz de adjacência de ordem
20x20, pois a heurística de vizinho mais próximo faz de forma instantânea matrizes menores que 20x20. 3.Compilação dos dados Após todos os dados serem recolhidos foi montado o gráfico numa planilha com a média de tempo de todas as execuções com a matriz de adjacência de ordem 20x20 4.Gráfico Vizinho Mais
Proximo

Algoritmo de Brute
Force

20x20

20x20
0,011

2,752

0,009

2,013

0,021

1,761

0,011

1,849

0,013

1,764

0,016

1,904

0,013

1,958

0,015

1,935

0,012

1,896

0,019

1,625

0,003

1,82

0,002

3,52

0,015

2,298

0,013

2,048

0,012

2,074

0,03

2,217

0,025

1,969

0,020

1,802

0,018

1,934

0,023

1,92

0,014

1,65

0,022

1,653

0,026

1,815

0,008

1,646

0,01

1,76

0,025

1,64

0,02

1,801

0,013

1,509

0,011

1,759

0,009

1,67

0,012

1,706

0,016

1,443

0,018

1,781

0,019

1,612

0,013

1,786

0,016

1,528

0,014

1,749

0,016

1,548

0,015

1,774

0,017

1,596

0,016

1,768

0,009

1,548

0,012

1,769

0,013

1,569

0,016

1,756

0,018

1,625

0,023

1,738

0,021

1,525

0,032

1,741

0,016