PublicouBrian Lessa Alterado mais de 4 anos atrás
18 Complexidade? |E|lg(|E|)
20 Que tal esta: Partindo da base, percorra as arestas que levam a vértices não visitados. Após visitar todos os vértices, una o último visitado ao primeiro. ... em princípio é uma heurística e apresenta uma solução...
21 Uma heurística apresenta uma solução...
4 9 4 1 5 3 9 10 9 2 6 4 8 2 9 Base 3 18 8 9 9 custo=53 é possível dizer mais sobre a solução? por exemplo, quão longe do ótimo está?
No caso de um grafo euclidiano (em que o custo por um caminho direto sempre é menor que o custo por um caminho indireto, ou seja, vale a desigualdade triangular e a noção de custo coincide com a noção de distância euclidiana) é possível demonstrar que custo_AGM<custo_otimo<= custo_encontrado<=2*custo_AGM<2*custo_otimo ... esta heurística é uma aproximação!!!
27 Aproximações Um algoritmo aproximativo (ou algoritmo de aproximação) é heurístico, ou seja, utiliza informação e intuição a respeito da instância do problema e da sua estrutura para resolvê-lo de forma rápida. Entretanto, nem todo algoritmo heurístico é aproximativo, ou seja, nem toda heurística tem uma razão de qualidade comprovada matematicamente ou prova formal de convergência. Por este motivo, em várias referências bibliográficas distingue-se os termos algoritmo aproximativo e heurística: aproximativo é a denominação do algoritmo que fornece soluções dentro de um limite de qualidade absoluto ou assintótico, assim como um limite assintótico polinomial de complexidade (pior caso) comprovado matematicamente; heurística e método heurístico são denominações para o algoritmo que fornece soluções sem um limite formal de qualidade, tipicamente avaliado empiricamente em termos de complexidade (média) e qualidade das soluções.