come fare la ricerca binaria in un modello di bugia?

Question

la domanda è come questa: esiste un elenco ordinato di n numeri. Dato x, trova un numero che è uguale a x nella lista ordinata. Qui assumiamo che x sia effettivamente nella lista. C'è un oracolo che può rispondere "sì" o "no" alla tua domanda "se x> = y?". A differenza della normale ricerca binaria, l'oracolo può mentire una volta alla tua domanda. Il modo più ingenuo per risolvere questo problema è che poni ogni domanda due volte all'oracolo. Se le due risposte sono le stesse, sai che l'orale non sta mentendo. Questo algoritmo ci serve confrontare 2log_2 (n) volte. Ma questa domanda mi chiede di trovare un algoritmo in grado di trovare x usando solo i confronti log_2 (n) + o (logn).

Ho provato molto duramente ma non ci sono riuscito. Qualcuno può darmi qualche consiglio su come risolvere questo problema? Grazie.

Answer 1

tenere traccia del dell'intervallo ci si trova. Se avete bisogno di un totale di k domande, verificare la presenza di consistenza (se si è nel frattempo si suppone di essere) ogni sqrt(k) passi. Mentre controlli la coerenza puoi chiedere a ciascuna domanda due volte per essere sicuro. Se rilevi un'incoerenza, torna indietro sqrt(k) passaggi. Non dovrai fare più di c*sqrt(k) domande aggiuntive.

Answer 2

Solo chiedere all'oracolo la domanda: "è x> = y?" una volta su ogni iterazione della tua ricerca binaria. Se ottieni la stessa risposta due volte, allora sai che l'oracolo non ha mentito per la prima volta.

Ad esempio, si sta cercando x = 1 e il primo test si prova contro y = a e l'oracolo risponde x < a. Nel secondo test si prova contro y = b e l'oracolo risponde x < b. Poiché stai usando la ricerca binaria e l'oracolo ha detto "<" e l'array è ordinato, sai che b < a. Pertanto, se x < b, sai anche che x < a, e la prima risposta non era una bugia. Se la seconda risposta è una bugia, e x> b, allora è ancora vero che x < a, poiché l'oracolo può mentire solo una volta.

Questo è vero anche se le risposte non tornano indietro. Ad esempio ottieni tre risposte: x < a, x> = b, x < c, sai che c < a, dalla tua ricerca binaria, e quindi deve essere stato vero che x < a, e l'oracolo non era mentire quando te l'ha detto.

Quindi cosa succede quando l'oracolo dice una bugia? Se la menzogna era x < y, allora la verità era x> = y. Pertanto, quando si continua la ricerca binaria, da quel momento in poi, i numeri che si verificano saranno tutti troppo piccoli e la risposta sarà sempre "> =", fino a raggiungere il fondo della ricerca binaria. A quel punto, ti rendi conto che se l'oracolo ha mentito, ha mentito l'ultima volta che ti ha detto qualcosa di diverso da "> =". Quindi riavvii la ricerca binaria nel punto in cui l'oracolo ti ha mentito e ha detto "x < y".

Questo utilizzerà sempre < 2 log_2 n confronti, ma se l'oracolo si trova all'inizio della ricerca, sarà necessario ripetere quasi log_2 n lavoro e quindi non si ottiene log_2 n + o (log n) risposta che stavi cercando. Quindi, dovresti incorporare l'idea suggerita da nm. Se ottieni la stessa risposta, ad esempio sqrt (log n) volte di seguito, allora sospetti che l'oracolo potrebbe aver mentito a te, e ti chiedi immediatamente di porre la domanda chiesto prima che le risposte inizino a ripetersi, invece di aspettare fino alla fine della ricerca binaria. Seguendo questa strategia, nel peggiore dei casi richiederete una domanda di log n/sqrt (log n) volte e troverete sempre la bugia con al massimo lo sqrt (log n) lavoro sprecato, che raggiunge il tempo di esecuzione che siete stati cercando.

Answer 3

Si consiglia di modificare la classica ricerca binaria per far funzionare tutto questo, come su di provare a chiedere l'oracolo in ogni iterazione per confrontare 2 indici differenti di matrice invece di 1, qualcosa come:

assume Oracle(x,y) returns "x>=y?", assume every division is returning floor integer. 
LyingOracleSearch(A,n,toFind) 
1. if (n==0) return not found 
2. if (A[0]==toFind) return found 
3. if (Oracle(A[n/4],toFind) and Oracle(toFind,A[3n/4]) then 
4.      return LyingOracleSearch(A[(n/4)...(3n/4)],3n/4-n/4,toFind) 
5. if (Oracle(A[n/4],toFind) and !Oracle(toFind,A[3n/4]) then 
6.      return LyingOracleSearch(A[0...(n/4)],n/4,toFind) 
7. if (!Oracle(A[n/4],toFind) and Oracle(toFind,A[3n/4]) then 
8.      return LyingOracleSearch(A[(3n/4)...n],n-3n/4,toFind) 
9. return LyingOracleSearch(A,n,toFind); \\orcale lied! 

Penso che unghie, potrebbe essere sbagliato tho.

la sua complessità è la stessa della BS originale, ma è meglio chiedere l'oracolo due o più volte. notate che un elemento non viene mai paragonato al doppio a meno che l'oracolo non si trovi, quindi se giace una volta o anche k volte in cui k è piccolo-o (logn) allora stiamo bene.

si può andare al vostro ambiente di codifica preferito e provare a codificarlo, ogni volta che un confronto fatto, contarlo. prova sia questo che l'ingenuo, e confronta il risultato, se non sbaglio, l'ingenuo dovrebbe confrontare il doppio di questo.

Avviso tho, non ero troppo attento con gli indici, è necessario fare un po 'il pensiero per assicurarsi che io wasnt manca un indice o non era la ripetizione di un indice accidentalmente.

Answer 4

Utilizzare il fatto che dopo che l'oracle ha mentito, la ricerca binaria diventa errata e non si ottiene alcuna modifica nella risposta dell'oracolo da quel momento (sempre o sempre <). Se non si ottiene alcuna modifica nella risposta dell'oracolo per i passaggi log(log(n)), verificare la coerenza dell'intervallo. Se l'intervallo corrente è incoerente, chiedere ancora una volta all'oracolo e, se ancora incoerente, tornare indietro ai passi log(log(n)) + 1 e continuare con la normale ricerca binaria.

Questa procedura richiede i controlli di coerenza O(log(log(n))) in media e fino a log(log(n)) passaggi di ricerca binaria aggiuntivi.

Numero medio di domande aggiuntive è c*log(log(n)), il numero massimo di domande aggiuntive è log(n)/(log(log(n))) + log(log(n)).

Answer 5

Credo che risolvere questa domanda in 3 * log(n) può essere semplice, ponendo la domanda di disuguaglianza tre volte ad ogni passaggio e la decisione è la maggioranza.