Perché l'alpinismo è chiamato algoritmo in qualsiasi momento?

Question

Perché l'alpinismo è chiamato algoritmo in qualsiasi momento?

#1 da (12 voti)
#2 da (6 voti)

4

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.

L'algoritmo di salita alla collina può essere bloccato in optima o cresta locale, dopo di che, anche se viene eseguito un tempo infinito, il risultato non sarà migliore. Allora, perché la salita in collina è chiamata algoritmo anytime?

algorithms wikipedia

posta user 21.03.2012 - 17:01

fonte

2 risposte

Leggi altre domande sui tag algorithms wikipedia

come faccio a sapere che ho diviso il mio programma in parti troppo piccole? È una cattiva pratica usare i condizionali con funzioni che cambiano lo stato del programma?

score 12 · Answer 1

All'inizio dell'arrampicata, hai già una soluzione, quindi può restituire una soluzione valida anche se interrotta, soddisfacendo una parte dei requisiti in qualsiasi momento.

La salita in salita normalmente produce anche risultati migliori, più l'algoritmo funziona, sebbene il tempo necessario per trovare una soluzione migliore possa avvicinarsi all'infinito se l'algoritmo si blocca. Tuttavia, la definizione di un algoritmo anytime dice che è previsto per produrre risultati migliori e ci aspettiamo che gli algoritmi di hill hill producano risultati migliori, anche se a volte no.

Quindi un algoritmo anytime:

Richiede: una soluzione valida per essere disponibile anche se l'algoritmo viene interrotto prima del completamento.
Aspetti: miglioramenti nella soluzione con il passare del tempo.

L'alpinismo soddisfa sia i requisiti che le aspettative, quindi può essere descritto come un algoritmo anytime.

score 6 · Answer 2

La risposta alla tua domanda è nascosta nella parte di testo citato:

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

La parte importante è nella definizione di valido in questo contesto - che soddisfa tutti i vincoli ed è migliore o almeno non peggiore di quello che hai già.

Questi algoritmi non sono chiamati Anytime perché il miglioramento del suo risultato è garantito come una funzione che sale in modo monotono. Sono chiamati così, perché puoi ottenere un risultato utilizzabile (valido, coerente, abbastanza buono ...) ogni volta che li fermi. Ciò significa anche che puoi chiedere un risultato finora migliore a in qualsiasi momento , utilizzarlo nel tuo business e lasciare che l'algoritmo continui a migliorarlo ancora di più (o meno).