AEDs III 04/05/2011

Na ultima aula falamos de programação dinamica

Um conceito usado foi o principio de otimalidade

Para aplicar esse conceito de prog dinamica é preciso ter a capacidade de decompor,
e o principio da otimalidade.

Hoje a aula falará sobre algoritimos gulosos.
A característica de um algoritimo guloso são as decisões locais, ou seja, uma decisão tomada sem a contemplação do total
do espaço de soluções.

É o tipo de decisão se a<b e para todo c>b, a<c, não vou comparar se a<c, eu acredito firmemente que ele será menor.
Isso também se aplica a algoritimos não-ótimos, por exemplo em um algoritimo de caminhamento em uma cidade,
voce pode escolher o caminho mais curto, mas não pode prever se o trafego por lá será um problema ou não.

Nota do professor: Uma decisão local pode ser ótima sse o algoritimo possuir "sub-estrutura ótima".

CONCEITO:
Elementos importantes para se caracterizar um algoritimo guloso:
- Um Critério de seleção guloso.
- Um meio para Avaliar a viabilidade.
- Um meio para Identificar uma solução.

Para Casa:
Entenda as caracteristicas dos 3 conceitos:
Algoritimo
Algoritimo aproximado é uma Heurística que voce garantidadmente sabe que ela não vai ser X% pior que a ótima,
                      ou seja um algoritimo para uma solução menos exigente.
Heurística