L'algoritmo per trovare gli interruttori necessari per accendere un light blub

Question

Supporre che ci si trovi in ​​una stanza con gli interruttori N e che ci sia una lampadina nella stanza successiva. La lampadina si accende solo quando alcuni interruttori specificati sono tutti accesi.

Set

• switches = l'insieme di tutti gli interruttori. |switches| = N.
• required = gli interruttori che devono essere attivati ​​per far brillare la lampadina.

Gli interruttori non necessari non sono importanti.

È possibile controllare solo se la lampadina è accesa solo se si accede alla stanza successiva. È possibile attivare o disattivare alcuni interruttori, passare alla stanza successiva per controllare la lampadina e ripetere questa procedura. Chiamiamo questo TENTATIVO.

supponga c'è N interruttori, nel peggiore dei casi, qual è il numero minimo di tentativi necessari per scoprire l'insieme di required interruttori (utilizzando la strategia ottimizzata)?

---

Per esempio,

• switches = { 1, 2, 3 }
• required = { 1, 2 }

Proviamo con un approccio ingenuo:

• Accendere { 1, 2 }, la luce i s incandescente. (Assicurarsi che l'interruttore 3 non sia necessario)
• Accendere { 1, 3 }, la luce non è accesa. (Verificare che sia necessario l'interruttore 2)
• Accendere { 2, 3 }, la luce non è accesa. (Assicurarsi che l'interruttore 1 sia necessario)

Quindi con 3 tentativi, possiamo assicurare required = { 1, 2 }.

Qual è l'algoritmo ottimizzato per questo problema?

Lascia il worst(N) il tentativo minimo considerando gli switch N nel peggiore dei casi. Potresti scoprire worst(N)

AGGIORNAMENTO: Se pensi che worst(N) = N, potresti fornire una prova formale?

Answer 1

prova che nel caso peggiore richiede almeno N tenta

Se ci sono N interruttori, ci possono essere 2 insiemi^N possibili 'richiesto' come ogni interruttore può essere sia dentro o fuori dal 'richiesto ' impostato.

Per distinguere tra i 2^N set possibili, è possibile pensarlo dato che sarà necessario ottenere almeno N bit di informazioni ingerendo con gli interruttori. In caso contrario, esiste la possibilità che ci siano più di un set che sia in grado di adattarsi alle informazioni che conosciamo finora.

Supponiamo che ci siano 8 configurazioni possibili (N = 3) e possiamo selezionare un sottoinsieme di configurazioni e interrogare se la configurazione 'richiesta' è nel sottoinsieme selezionato. Il modo migliore per farlo sarebbe simile alla ricerca binaria, ottenendo una complessità di log (2^N) che è solo N tentativi. Se usiamo meno di 3 tentativi, resteremo con almeno 2 configurazioni che non possiamo decidere quale sia corretta poiché ogni tentativo eliminerà la metà delle possibili configurazioni.

Tornando al problema originale, assumiamo di utilizzare i tentativi K fino a questo punto dove K < N. Poiché ogni tentativo fornirà 1 bit di informazioni (Sì, si illumina/No, non si illumina), ogni tentativo può eliminare metà del numero possibile di configurazioni, resteremo con 2^(NK) possibili configurazioni dopo i tentativi di K.

Per ottenere solo 1 distinta configurazione possibile del set 'richiesto', avremo bisogno di K = N che ci darà 2^(N-N) = 2^0 = 1 possibile configurazione.

Questo ci dà il limite inferiore per questo problema poiché ogni tentativo fornirà 1 bit di informazioni (Sì, si illumina/No, non si illumina). Quindi avremo bisogno di almeno N tentativi.

Possibile soluzione che utilizza non più di N tenta

partire dagli interruttori non necessaria non importa ', se interpreto correttamente, significa che se interruttori all'esterno del set 'richiesto' sono girano on, oltre a quelli nel set 'richiesto', la luce sarà ancora accesa. Dato che abbiamo N tentativi di utilizzare (e comunque lo rendono ottimale), possiamo permetterci di usare la seguente soluzione: Per ogni interruttore (in ordine sequenziale), accendi tutti gli altri switch tranne questo interruttore. Controllare se la luce è spenta. Se è spento, l'unico interruttore che rimane spento sarà nel set 'richiesto'.

Questa soluzione utilizzerà esattamente N tentativi (anche nel caso peggiore) ed è una delle soluzioni ottimali (come dimostrato in precedenza).

Answer 2

Supponiamo di dover provare tutte le combinazioni possibili degli interruttori N. Possiamo quindi rappresentare come un numero binario dire 0101 e vogliamo controllare ogni numero binario. Un approccio ingenuo è quello di passare ogni numero a turno: 0000 (tutto spento), 0001 (interruttore 4 attivato), 0010 (interruttore 3 attivato), 0011 (interruttore 3 e 4 acceso). Nota come ottenere da 0001 a 0010 in realtà richiede due passaggi per spegnere 4 e 3 on.

Un algoritmo migliore chiamato Gray code attraversa ogni numero in modo che venga commutata solo una cifra ogni volta. La sequenza sarebbe 0000, 0001, 0011, 0010, 0110 , 0111, 0101, 0100, 1100, 1101, 1111, 1110, 1010, 1011, 1001, 1000.

EDIT: Credo questo risolve un problema leggermente diverso in cui per la luce che si trova su alcuni interruttori dovrebbe essere spento per far accendere la luce.

Answer 3

Supponiamo che ci siano N interruttori, in CASO PEGGIO, qual è il numero minimo di tentativi necessari per trovare l'insieme degli switch richiesti (utilizzando la strategia ottimizzata)?

Il modo forza bruta, controllando tutte le possibili combinazioni di interruttori fino a quando la luce si accende, il che sarebbe O(2^N) (anche se potrebbe avere fortuna e avere l'interruttore dopo il primo tentativo).

Con ricerche più ottimizzate, il set di interruttori richiesti può essere trovato nel caso peggiore dei tentativi O(N). Qui è un modo che è sempre O(N):

• capovolgere tutti N interruttori: sappiamo che la luce si accende.

• Disattivare l'interruttore 1. Se la luce si spegne, è necessario l'interruttore 1, quindi riaccenderlo. Se la luce rimane accesa, lasciare l'interruttore 1 spento perché non è necessario. (Un tentativo usato).

• Interruttore di accensione 2 spento: se la spia si spegne, è necessario l'interruttore 2, quindi riaccenderlo. Se la luce rimane accesa, lasciare l'interruttore 2 spento perché non è necessario. (Sono stati usati due tentativi).

• Ripetere questo controllo per ciascuno degli interruttori rimanenti. (Tentativi N utilizzati).

• Dopo i tentativi N, restiamo con il set degli switch richiesti nella posizione on.

Come osservato in altre risposte/commenti, è anche possibile che la serie di switch necessari può essere trovato nel migliore dei casi O(log(N)) e caso peggiore O(N):

• capovolgere tutti N interruttori: sappiamo che la luce sarà accesa.

• Capovolgi il primo N/2 spento. Nella luce rimane acceso, nessuno di questi interruttori era necessario, quindi possiamo lasciare gli interruttori spenti. Spostarsi alla serie di N/2 interruttori che sono ancora e ripetere questo passo ...

• Se invece la luce andò, era richiesto almeno uno di questi interruttori N/2: capovolgere le riaccende, raggruppati in set metà e ripetere il passaggio precedente ...

Questo algoritmo è caso peggiore O(N) perché potremmo dover controllare ogni interruttore singolarmente (ad esempio se ci sono 10 interruttori e la configurazione necessaria è 0101010101).