Por que o hill climbing é chamado de algoritmo anytime?

4

Na wikipedia, Algoritmo Anytime

In computer science an anytime algorithm is an algorithm that can return a valid solution to a problem even if it's interrupted at any time before it ends. The algorithm is expected to find better and better solutions the more time it keeps running.

Hill climbing

Hill climbing can often produce a better result than other algorithms when the amount of time available to perform a search is limited, such as with real-time systems. It is an anytime algorithm: it can return a valid solution even if it's interrupted at any time before it ends.

Algoritmo de escalada em montanhas pode ficar preso em locais ótimos ou em cordilheiras, depois disso, mesmo que ele execute um tempo infinito, o resultado não será melhor. Então, por que o hill climbing é chamado de algoritmo a qualquer hora?

    
por user 21.03.2012 / 17:01
fonte

2 respostas

12

No início da subida, você já tem uma solução, portanto, pode retornar uma solução válida mesmo que seja interrompida, cumprindo uma parte dos requisitos a qualquer momento.

O hill-climbing também produz normalmente melhores resultados quanto mais o algoritmo é executado, embora o tempo gasto para encontrar uma solução melhor possa se aproximar do infinito se o algoritmo ficar preso. No entanto, a definição de um algoritmo a qualquer hora diz que é esperado que produza melhores resultados, e esperamos que os algoritmos de subida de colina produzam melhores resultados, embora às vezes não o façam.

Então, um algoritmo a qualquer hora:

  • Requer: Uma solução válida para estar disponível mesmo se o algoritmo for interrompido antes da conclusão.
  • Espera: Melhorias na solução com o passar do tempo.

Hill climbing preenche tanto a exigência quanto a expectativa, então ele pode ser descrito como um algoritmo a qualquer hora.

    
por 21.03.2012 / 17:12
fonte
6

A resposta à sua pergunta está oculta no texto citado:

it can return a valid solution even if it's interrupted at any time before it ends.

A parte importante está na definição de válido neste contexto - que satisfaz todas as restrições e é melhor ou pelo menos não pior do que você já teve.

Esses algoritmos não são chamados Anytime porque a melhoria de seu resultado é garantida como uma função monotonamente crescente. Eles são chamados assim, porque você pode obter um resultado utilizável (válido, consistente, bom o suficiente ...) sempre que você os parar. Isso significa que você pode pedir um resultado muito melhor em qualquer momento , usá-lo em sua empresa e deixar o algoritmo continuar melhorando ainda mais (ou não).

    
por 21.03.2012 / 17:14
fonte