Straight Line Distance

Sumário
1. Definição 2
2. Pontos Positivos 2
3. Pontos Negativos 3
4. Exemplos 4
4.1. Problema da mochila fracionária 5
4.2. Problema da árvore de Huffman 6
4.3. Problema da arborescência maximal de peso mínimo num digrafo simétrico 8
5. Straight line distance 9
6. Referências 9

1
1. Definição Numa visão mais técnica, a busca pelo melhor primeiro ou busca gulosa consiste na ideia de selecionar o caminho no qual o último nó está mais perto do objetivo, de acordo com uma função heurística. Uma função heurística, em poucas palavras, é uma função h(n) onde esta é uma estimativa do custo do caminho de um nó n até um nó objetivo. São exemplos de funções heurísticas: h(n) = distância em linha reta de n até o objetivo mais próximo; h(n) = número de átomos da query. Deste modo, esse método de otimização seleciona o caminho na fronteira com o menor valor de h(n), tratando a fronteira como uma fila de prioridade ordenada por h. Em outras palavras, as buscas gulosas tomam decisões com base apenas na informação disponível, sem se preocupar com os efeitos futuros de tais decisões, isto é, eles nunca reconsideram as decisões tomadas, independentemente das consequências. Não há, portanto, necessidade de avaliar as alternativas nem de empregar procedimentos elaborados permitindo que decisões anteriores sejam desfeitas.
2. Pontos Positivos Devido a sua característica de buscar sempre a primeira melhor decisão, de forma geral, os algoritmos que utilizam esse método, chamados de algoritmos gulosos, são fáceis de serem criados e implementados. Quando uma busca gulosa é bem sucedida num determinado problema, isto é, encontrou-se a solução ótima ou uma solução quase ótima nos casos em que ainda não se sabe uma solução ótima ainda, compararmos com alguns outros métodos de otimização nota-se que a busca gulosa é muito rápida e eficiente. Em alguns casos, como veremos na próxima sessão, os algoritmos gulosos não encontram a