È simile al gioco Mastermind.

C'è molta letteratura su questo argomento.Per quel caso specifico (4 domande con ogni 6 opzioni) sono state ideate diverse strategie che riducono il numero medio di riprese a un po 'sopra 4,3.

Potresti scegliere una di queste strategie o crearne una nuova e applicarla al caso di $ n $ domande con $ 2 $ opzioni, che è la tua situazione.La domanda è troppo ampia per fornire una risposta dettagliata qui.

Questo è un problema di ottimizzazione in cui cerchi di trovare un numero binario a cifre $ n $ sconosciuto da ipotesi, in cui il feedback di tali ipotesi è che ricevinumero di cifre corrette.Questo è essenzialmente solo Mastermind binario, che viene anche esaminato in un problema computazionale chiamato "ottimizzazione della scatola nera" (vedi ad esempio, Doerr et al 2001).

Come altri hanno già detto, il problema è molto simile al gioco Mastermind. Supponi che le risposte corrette siano variabili binarie $ c_i $ per $ i = 1, \ ldots, n $ e che Rain fa il test $ k $ volte, alla volta $ j $ rispondendo $ x_ {i, j} $ alla $ i $ -th domanda ( $ i \ le n, j \ le k $ ). La risposta corretta totale alla $ j $ -esima volta è $ T_j $ .

Quelle che seguono sono solo alcune osservazioni e note, basate sulla richiesta esplicita dell'OP di fornire solo alcuni suggerimenti sul problema.

1. Tieni presente che un semplice limite inferiore "teorico dell'informazione" su $ k $ per una configurazione generica di risposte corrette è $ k \ ge O (n / \ log n) $ : ogni test fornisce a Rain un numero $ 0 \ le T_j \ le n $ , che equivale a $ \ le \ log n $ bit di conoscenza, mentre la conoscenza richiesta per conoscere tutte le risposte è ~ $ n $ (a causa delle $ n $ domande binarie).

2. Nel caso generale puoi definire le variabili $ z ^ Y_i $ e $ z ^ N_i $ essere $ 0 $ o $ 1 $ rispettivamente se $ i $ -esima risposta corretta è Sì o No. In tal modo il tuo problema è determinare il punto delle risposte corrette in uno spazio lineare "discreto" di dimensione $ 2n $ : per vedere perché consideralo secondo la definizione precedente di variabili hai i vincoli $$ z ^ Y_i + z ^ N_i = 1 $$

   Inoltre, alla tua $ j $ -esima parte dell'esame, stai testando una combinazione lineare di tali variabili e sai che la loro somma è $ T_j $ : $$ \ sum_ {i = 1} ^ n z ^ {S / N} _i = T_j $$

   Ciò evidenzia che è banale risolvere questo problema nelle query $ n $ perché eseguendo il test $ k $ volte che hai $ n + k $ equazioni che definiscono un punto in una dimensione $ 2n $ spazio, in modo che se sei abbastanza intelligente da non fare domande ridondanti (cambia semplicemente le tue risposte una alla volta) puoi prendere solo $ n $ volte il quiz.

3. In casi particolari (come quando il rapporto sì / no è particolarmente sbilanciato) dovrebbe essere facile trovare euristiche particolarmente adatte: supponi per esempio di sapere che c'è una sola risposta Sì nell'intero quiz . Puoi quindi trovarlo solo nelle $ \ log n $ query per bisezione standard sui set di risposte. Inoltre puoi verificare se ti trovi in ​​questo caso eseguendo una prima query "all-yes" (nel qual caso $ T_1 = 1 $ ).

4. Generalizzando l'idea nel precedente punto elenco, se il numero di risposte Sì è $ C $ (supponiamo che $ C \ le n / 2 $ ) (e questo può essere conosciuto da una singola query), stai fondamentalmente cercando un insieme di dimensioni $ C $ span> all'interno di un insieme di dimensioni $ n $ (quindi ci sono $ \ binom {n} {C} \ simeq n ^ C $ di loro) e la tua query consiste nel conoscere la cardinalità dell'intersezione di un insieme $ S $ di tua scelta con detto insieme di domande Sì , che penso sia un problema molto più studiato e su cui probabilmente puoi trovare molti riferimenti.

   Chiama l'insieme che stai cercando di trovare (risposte Sì) $ Y $ . Con una singola query puoi conoscerne la cardinalità $ | Y | = m $ . Ora un insieme selezionato a caso $ S $ utilizzato come query ti consente di conoscere la cardinalità dei due sottoinsiemi $ | Y \ cap S | = t $ e $ | Y \ cap S ^ c | = m - t $ e il tuo problema originale è stato ridotto a due sottoproblemi di circa la metà delle dimensioni (anche il numero di risposte Sì cercate di solito si dimezza ad ogni iterazione). Non scriverò dettagli espliciti, ma è solo una questione di semplici calcoli di probabilità.

   Sfruttando l'osservazione di cui sopra, dovresti trovare un algoritmo probabilitico che risolva il sottoproblema $ P (m, n) \ simeq \ le 1 + 2 * P (m / 2 , n / 2) $ , che dovrebbe ottenere un limite di $ O (m \ log n) $ . È possibile elaborare un algoritmo deterministico per tale problema utilizzando la tecnica delle aspettative massimizzate, ma non posso prevedere se funzionerà o meno.

Vuoi ridurre al minimo il numero massimo di ripetizioni? o ridurre al minimo il numero previsto di ripetizioni?

Potresti escogitare strategie molto diverse a seconda di quale desideri esaminare.

Un primo approccio ingenuo richiederebbe fino a $ n + 1 $ volte e consisterebbe nel fare il test la prima volta, poi la seconda volta nel prova cambia solo la prima risposta, se il punteggio aumenta, mantieni la nuova risposta, se scende torna alla prima risposta per tutti i passaggi futuri. La 3a volta (2a ripetizione) cambia solo la 2a risposta, ecc.

Ora puoi iniziare a confrontare altre strategie con quella. Se la seconda volta che si esegue il test 2 risposte vengono modificate, se il punteggio cambia, conosciamo le risposte corrette per 2 domande e abbiamo salvato un passaggio, ma se ne abbiamo modificato uno per essere corretto e l'altro per essere sbagliato, allora il punteggio sì non cambia e non sappiamo quale modifica era corretta fino a quando non sosteniamo l'esame una terza volta cambiando solo uno di essi (ma questo ci parlerà anche dell'altro), quindi 1 o 2 ripetizioni per ottenere 2 risposte (50% possibilità di ciascuno) che ridurrà il numero previsto di ripetizioni, ma probabilmente manterrà il massimo lo stesso.

Ora puoi esaminare altre strategie e vedere come si confrontano (cambia le prime 3 risposte, cambia la prima $ \ frac {n} {2} $ , ecc.).