Algoritmo guloso: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
Introdução de um exemplo e a explicação dele |
|||
Linha 4:
Desvantagens: Nem sempre conduz à soluções ótimas globais. Podem efetuar cálculos repetitivos.
Um exemplo de algoritmo guloso é o algoritmo do caixa eletrônico:
''o cliente pede para sacar o valor de R$ 65,00
Você tem as gavetas com os valores: 5, 10, 20, 50, 100.
65 < 100, portanto não dá para tirar da gaveta de 100
65 >= 50, portanto você tenta tirar da gaveta de 50
Se a gaveta de 50 tiver notas, você vai tirando uma nota de cada vez.
Digamos que a gaveta de 50 tenha notas.
65 - 50 = 15 (tirou uma nota de 50)
15 < 50, então não dá para tirar mais da gaveta de 50
15 >= 10, então dá para tirar da gaveta de 10
Se a gaveta de 10 tiver notas, você vai tirando uma nota de cada vez.
Digamos que a gaveta de 10 esteja vazia. Então você vai para a próxima gaveta, que é a de 5.
Digamos que a gaveta de 5 só tenha 2 notas.
15 - 5 = 10 (tirou uma nota de 5)
10 - 5 = 5 (tirou a última nota de 5)
Sobrou alguma coisa? Então você tem de desfazer tudo, e avisar ao usuário que não consegue dar 65 reais devido à falta de notas.''
Nesse exemplo podemos notar que apesar de o algoritmo fazer a melhor escolha local (que é retirar o maior numero de notas grandes possíveis), ele não tem um bom desempenho pois realiza todo o processamento desnecessariamente, e o resultado é diferente do esperado. Isso não parece muito, mas em um processo grande que envolve muitas variáveis, com valores altos, ou muitos dados para processar, gera um desperdício de tempo, que é crucial em uma aplicação do tipo.
{{mínimo sobre|matemática}}
| |||