Trovare un oggetto su una linea infinita

Question

Trovare un oggetto su una linea infinita

#1 da (6 voti)
#2 da (5 voti)
#3 da (0 voti)
#4 da (-1 voti)

5

Domanda:

C'è una linea infinita. Sei in piedi in un punto particolare che puoi spostare 1 passo in avanti o 1 passo indietro. Devi cercare un oggetto in quella linea infinita. Il tuo oggetto può essere in qualsiasi direzione. Fornisci una soluzione ottimale

Il mio approccio:

       Go 1 step forward, 2 step back ward 
       Go 2 step forward, 4 step back ward and so on

Complessità:

Diciamo che l'oggetto richiesto è al punto n.

Numero totale di passaggi:

 3 + 6 + 9 + .... n
 = 3(1 + 2 + 3 ... n)
 = O(n^2)

C'è un modo per migliorare l'efficienza?

algorithms programming-logic

posta Chander Shivdasani 05.09.2013 - 07:40

fonte

4 risposte

Leggi altre domande sui tag algorithms programming-logic

Mantenere documentazione / manuali aggiornati in un progetto in rapida evoluzione Unit test tattiche

score 6 · Answer 1

Che cosa intendi per "soluzione ottimale"?
Fai il minor numero possibile di passi?
Vorrei non aumentare la distanza dal punto di partenza di 1 ogni volta, perché dopo un po 'di tempo visita quasi sempre una posizione che hai già visitato e il rapporto tra i nuovi punti visitati converge a 0. Vorrei usare un modello che garantisce che visitiamo sempre un rapporto fisso di nuovi punti.
es
r: giusto passo avanti l: left step

                x
                 r              new: 1   old: 0
               ll               new: 2   old: 1
                rrrr            new: 4   old: 3 
           llllllll             new: 8   old: 7
            rrrrrrrrrrrrrrrr    new:16   old:15

In questo modo il rapporto tra le posizioni già visitate e le nuove posizioni visitate è sempre di circa 1: 1.

score 5 · Answer 2

Una strategia di crescita esponenziale esegue il tempo O (n), la media e il caso peggiore. Questo è ottimale se si trascurano i fattori costanti. Se vuoi ottimizzare anche il fattore costante, devi fare qualche ipotesi sulla distribuzione della probabilità.

Ad esempio se usi una strategia di raddoppiamento, il costo massimo è 7 * n

dist = 1
loop
    MoveTo(dist)
    MoveTo(-dist)
    dist = dist * 2

score 0 · Answer 3

Supponendo che:

Ogni passaggio costa tempo
Non è possibile prevedere dove si trova questo oggetto sulla "linea" infinita dei passaggi
Che non puoi biforcarti o clonare te stesso
Che ottieni solo più informazioni una volta che sei sull'oggetto (nessun suggerimento mentre vai)

Quindi scegli una direzione a caso e inizia a camminare. Nessun backtracking costoso. Certo potrebbe essere un passo indietro ma questa è solo la fine dell'infinito proprio lì.

O (n)

score -1 · Answer 4

Su una linea infinita non troverai mai l'oggetto. L'infinito è una cosa strana. cioè scegli un punto su una linea finita, poiché la lunghezza della linea si avvicina all'infinito la probabilità che il punto selezionato sia l'oggetto che si avvicina a zero.

Alcune cose che potrebbero rendere questo problema significativo

La linea è finita (un numero N)
L'oggetto può essere solo in punti discreti.

Immagino che in questi casi la soluzione ottimale (il minor numero di passi) sia quella di camminare in una direzione finché non trovi l'oggetto o raggiungi la fine. Se raggiungi la fine verrai riconsegnato.