Cerca il numero (che si muove lentamente) con penalità per un valore di test troppo alto

Question

Cerca il numero (che si muove lentamente) con penalità per un valore di test troppo alto

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

3

Il tuo compito è progettare un algoritmo di ricerca che trovi il mio numero segreto, che è compreso tra 0 e 2 ^ 64. Se il valore del test è troppo basso, puoi eseguire nuovamente il test in 1 secondo. Se il tuo valore di test è troppo alto non ti è permesso testare nuovamente i successivi 300 secondi.

Ogni secondo aggiungo 1 o sottrai 1 dal numero. Non ti dirò cosa ho fatto e, anche se potrebbe essere casuale, potrebbe anche non essere casuale.

Come si può trovare il numero approssimativo veloce?

La risposta ovvia è usare una ricerca binaria, ma dal momento che la penalità è alta per indovinare troppo alto, penso che sia necessario un aggiustamento.

Sfondo

Ho bisogno di trovare la velocità di un sistema. La velocità cambia lentamente. Ci vuole 1 secondo per fare una supposizione. Se la mia ipotesi è troppo bassa: nessun problema. Se è troppo alto, il sistema si riavvia, provocando un ritardo di 5 minuti.

Il mio obiettivo è ottenere una stima decente della velocità relativamente veloce.

algorithms

posta Ole Tange 10.04.2014 - 21:54

fonte

2 risposte

Leggi altre domande sui tag algorithms

Dovrei considerare anche l'accoppiamento lento per i metodi di classe? [duplicare] Differenza tra loop di eventi e chiamate / interrupt di sistema

score 6 · Answer 1

Ho fatto alcune simulazioni empiriche di una versione semplificata di questo sistema. Sembra intuitivo che si possa usare una ricerca binaria, modificata con un fattore di peso per polarizzare la selezione del "punto medio" verso numeri più bassi. Un'altra risposta è stata proposta 300 (quindi scegliere un punto medio che è 1/300 della via da sinistra a destra), ma volevo controllare questo.

Ho scritto una simulazione ( codice qui ) che esegue 1000 prove per ogni fattore di ponderazione tra 2 (ricerca binaria standard il punto medio a 1/2) e 499 (prendendo il punto medio a 1/499). I risultati possono essere visualizzati in questo foglio di calcolo e il grafico risultante ha un aspetto simile al seguente:

Ciòchesembramostrareècheunaricercabinariastandardsicomportamale,comeprevisto.Tuttavia,ilfattoredipesoottimalesembraesserequalcosadicirca70(quindiscegliereilpuntomedioperlaricercabinariacome1/70dellaviadasinistraadestra).(Nonsonosicurodelmotivopercuiquestoèvero,forseunadomandaper link .)

Non ho tentato di modellare il comportamento "errante" di destinazione nella tua domanda. Puoi modificare la simulazione per aggiungere questa funzione.

score 2 · Answer 2

Non sono uno statistico, ma mi sembra che indovinare 1/300 dell'intervallo complessivo ti possa ottenere la risposta più rapidamente, una ricerca binaria ponderata.

Quindi, la prima ipotesi è (1/300) * 2 ^ 64

La seconda ipotesi è o

in caso di successo (1/300) * (1/300) * 2 ^ 64 o

in caso di errore (1/300) + (1/300) * (2 ^ 64 - (1/300))

ecc.