Qual é a diferença entre uma heurística e um algoritmo?

Question

Qual é a diferença entre uma heurística e um algoritmo?

Answer 1

Um algoritmo é a descrição de um solução automatizada para um problema. O que o algoritmo faz é definido com precisão. A solução poderia ou não ser a melhor possível, mas você sabe desde o início que tipo de resultado você obterá. Você implementa o algoritmo usando alguma linguagem de programação para obter (uma parte) um programa.

Agora, alguns problemas são difíceis e você pode não conseguir obter uma solução aceitável em um tempo aceitável. Nesses casos, muitas vezes você pode obter uma solução não muito ruim muito mais rápido, aplicando algumas escolhas arbitrárias (suposições educadas): isso é um heurística.

Uma heurística ainda é uma espécie de algoritmo, mas que não explorará todos os estados possíveis do problema ou começará explorando os mais prováveis.

Exemplos típicos são de jogos. Ao escrever um programa de jogo de xadrez, você pode imaginar experimentar todos os movimentos possíveis em algum nível de profundidade e aplicar alguma função de avaliação na placa. Uma heurística excluiria galhos completos que começam com movimentos obviamente ruins.

Em alguns casos, você não está procurando a melhor solução, mas para qualquer solução ajustando alguma restrição. Uma boa heurística ajudaria a encontrar uma solução em pouco tempo, mas também pode não encontrar alguma se as únicas soluções estiverem nos estados que optar por não tentar.

Answer 2

• Um algoritmo é tipicamente determinístico e comprovado para produzir um resultado ideal
• Uma heurística não tem prova de correção, geralmente envolve elementos aleatórios e pode não produzir resultados ideais.

Muitos problemas para os quais nenhum algoritmo eficiente para encontrar uma solução ideal é conhecida, têm abordagens heurísticas que produzem resultados quase ideais muito rapidamente.

Existem algumas sobreposições: "algoritmos genéticos" é um termo aceito, mas estritamente falando, essas são heurísticas, não algoritmos.

Answer 3

A heurística, em poucas palavras, é um "palpite". A Wikipedia explica bem. No final, um método de "aceitação geral" é considerado uma solução ideal para o problema especificado.

A heurística é um adjetivo para técnicas baseadas na experiência que ajudam na solução, aprendizado e descoberta de problemas. Um método heurístico é usado para chegar rapidamente a uma solução que se espera estar próxima da melhor resposta possível ou 'solução ideal'. As heurísticas são "regras práticas", suposições educadas, julgamentos intuitivos ou simplesmente senso comum. Uma heurística é uma maneira geral de resolver um problema. As heurísticas como substantivas são outro nome para métodos heurísticos.

Em termos mais precisos, as heurísticas representam estratégias usando informações prontamente acessíveis, embora vagamente aplicáveis, para controlar a solução de problemas em seres humanos e máquinas.

Enquanto um algoritmo é um método que contém conjunto de instruções finitas usadas para resolver um problema. O método foi comprovado matematicamente ou cientificamente para trabalhar para o problema. Existem métodos e provas formais.

Algoritmo heurístico é um algoritmo capaz de produzir uma solução aceitável para um problema em muitos cenários práticos, na moda de uma heurística geral, mas para a qual não há prova formal de sua correção.

Answer 4

Na verdade, não acho que haja muito em comum entre eles. Alguns algoritmos usam heurísticas em sua lógica (geralmente para fazer menos cálculos ou obter resultados mais rápidos). Geralmente, as heurísticas são usadas nos chamados algoritmos gananciosos.

As heurísticas são algum "conhecimento" que assumimos que é bom usar para obter a melhor escolha em nosso algoritmo (quando uma escolha deve ser tomada). Por exemplo ... uma heurística no xadrez poderia ser (sempre leve a rainha dos oponentes, se puder, já que você sabe que essa é a figura mais forte). As heurísticas não garantem que você o leve à resposta correta, mas (se as suposições estiverem corretas) geralmente obtenha a resposta que é próxima do melhor em tempo muito mais curto.

Answer 5

Um algoritmo é um conjunto de operações passo a passo independente a ser realizado 4, normalmente interpretado como uma sequência finita de instruções (computador ou humano) para determinar uma solução para um problema como: Existe um caminho de A a B, ou qual é o menor caminho entre a e B. neste último caso, você Também poderia estar satisfeito com uma solução alternativa 'razoavelmente próxima'.

Existem certas categorias de algoritmos, dos quais o algoritmo heurístico é um. Dependendo das propriedades (comprovadas) do algoritmo neste caso, ele se enquadra em uma dessas três categorias (Nota 1):

• Exato: A solução é comprovada como um ideal (ou exato solução) para o problema de entrada
• Aproximação: O desvio do valor da solução é comprovado que nunca está mais longe do valor ideal do que algum limite predefinido (por exemplo, nunca mais que 50% maior que o valor ideal)
• Heurística: O algoritmo não provou ser ideal, nem dentro de um limite predefinido da solução ideal

Observe que um algoritmo de aproximação também é uma heurística, mas com a propriedade mais forte que existe um vinculado comprovado à solução (valor) que produz.

Para alguns problemas, ninguém jamais encontrou um algoritmo 'eficiente' para calcular as soluções ideais (nota 2). Um desses problemas é o conhecido problema de vendedor ambulante. O algoritmo de Christophides para o problema do vendedor ambulante, por exemplo, costumava ser chamado de heurística, como não foi comprovado que estava dentro de 50% da solução ideal. Como foi comprovado, no entanto, o algoritmo de Christophides é referido com mais precisão como um algoritmo de aproximação.

Devido a restrições sobre o que os computadores podem fazer, nem sempre é possível eficientemente encontre o melhor solução possível. Se houver estrutura suficiente em um problema, pode haver uma maneira eficiente de atravessar o espaço da solução, mesmo que o espaço da solução seja enorme (ou seja, no problema mais curto do caminho).

As heurísticas são normalmente aplicadas para melhorar o tempo de execução dos algoritmos, adicionando 'informações especializadas' ou 'suposições educadas' para orientar a direção da pesquisa. Na prática, uma heurística também pode ser uma sub-rotina para um algoritmo ideal, para determinar onde procurar primeiro.

(nota 1): Além disso, os algoritmos são caracterizados por incluir elementos aleatórios ou não determinísticos. Um algoritmo que sempre executa da mesma maneira e produz a mesma resposta é chamado determinístico.

(nota 2): Isso é chamado de problema de P vs NP, e é improvável que os problemas classificados como NP-completos e NP-difusos tenham um algoritmo 'eficiente'. Observação; Como @kriss mencionado nos comentários, existem tipos de problemas até 'pior', que podem precisar de tempo ou espaço exponencial para calcular.

Existem várias respostas que respondem parte da pergunta. Eu os considerei menos completos e não precisos o suficiente e decidi não editar a resposta aceita feita por @kriss

Answer 6

As heurísticas são algoritmos, portanto, nesse sentido, não há nenhuma, no entanto, as heurísticas adotam uma abordagem de 'palpite' para a solução de problemas, produzindo uma resposta 'boa o suficiente', em vez de encontrar uma solução 'melhor possível'.

Um bom exemplo é para onde você tem um problema muito difícil (leia-se NP-completo) para o qual deseja uma solução, mas não tem tempo para chegar a ele, então tem que usar uma solução suficientemente boa com base em um algoritmo heurístico, como como Encontrar uma solução para um problema de vendedor ambulante usando um algoritmo genético.

Answer 7

O algoritmo é uma sequência de algumas operações que recebem uma entrada calcula algo (uma função) e produz um resultado.

O algoritmo pode produzir valores exatos ou aproximados.

Ele também pode calcular um valor aleatório com alta probabilidade próximo ao valor exato.

Um algoritmo heurístico usa algumas informações sobre valores de entrada e calcula o valor exato (mas pode estar próximo do ideal). Em alguns casos especiais, a heurística pode encontrar uma solução exata.

Answer 8

Um algoritmo é um conjunto claramente definido de instruções para resolver um problema, as heurísticas envolvem a utilização de uma abordagem de aprendizado e descoberta para alcançar uma solução.

Portanto, se você souber como resolver um problema, use um algoritmo. Se você precisa desenvolver uma solução, é heurística.

Answer 9

Uma heurística é geralmente uma otimização ou uma estratégia que geralmente fornece uma resposta boa o suficiente, mas nem sempre e raramente a melhor resposta. Por exemplo, se você resolve o problema do vendedor ambulante com força bruta, descartar uma solução parcial quando seu custo exceder o da melhor solução atual é uma heurística: às vezes ajuda, outras vezes não, e definitivamente não é t melhorar a teórica (notação big-oh) tempo de execução do algoritmo

Answer 10

Acho que a Heurística é mais uma restrição usada no Modelo Baseado em Aprendizagem em Inteligência Artificial, uma vez que os estados futuros da solução são difíceis de prever.

Mas então minha dúvida depois de ler as respostas é "Como a heurística pode ser aplicada com sucesso usando técnicas de otimização estocástica?ou eles podem funcionar como algoritmos completos quando usados ​​com Otimização Estocástica?"

http://en.wikipedia.org/wiki/Stochastic_optimization

Answer 11

Uma das melhores explicações que li vem do grande livro Código completo, que agora cito:

Uma heurística é uma técnica que ajuda você a procurar uma resposta. Seus resultados estão sujeitos a acaso porque uma heurística diz apenas como se parecer, não o que encontrar. Não diz a você como obter diretamente do ponto A ao ponto B; Pode nem saber onde estão os pontos A e o ponto B. Com efeito, uma heurística é um algoritmo em um traje de palhaço. É menos previsível, é mais divertido e vem sem uma garantia de devolução do dinheiro de 30 dias.

Aqui está um algoritmo para dirigir para a casa de alguém: pegue a estrada 167 ao sul até Puy-Allup. Pegue a saída do South Hill Mall e dirija a 4,5 milhas até a colina. Vire à direita na luz do supermercado e depois pegue a primeira esquerda. Transforme -se na garagem da grande casa bronzeada à esquerda, no 714 North Cedar.

Aqui está uma heurística para chegar à casa de alguém: encontre a última carta que enviamos por correio. Dirija até a cidade no endereço de retorno. Quando você chegar à cidade, pergunte a alguém onde está nossa casa. Todo mundo nos conhece - alguém ficará feliz em ajudá -lo. Se você não conseguir encontrar ninguém, ligue para nós de um telefone público e vamos buscá -lo.

A diferença entre um algoritmo e uma heurística é sutil, e os dois termos se arremessarem um pouco. Para os propósitos deste livro, a principal diferença entre os dois é o nível de indireção da solução. Um algoritmo fornece as instruções diretamente. Uma heurística diz a você como descobrir as instruções por si mesmo, ou pelo menos onde procurá -las.

Answer 12

Eles encontram uma solução subótima sem garantia quanto à qualidade da solução encontrada, é óbvio que faz sentido para o desenvolvimento de heurísticas apenas polinomiais. A aplicação desses métodos é adequada para resolver problemas do mundo real ou grandes problemas tão estranhos do ponto de vista computacional que, para eles, não há nem um algoritmo capaz de encontrar uma solução aproximada no tempo polinomial.