Problema topologico

[Robert]

Su una tratta di acquedotto lunga 1 km si è verificata una perdita, probabilmente è scoppiata una valvola, in quella tratta ci sono 50 tombini da scoperchiare per vedere se la perdita è lì...uno ogni 20 metri...
voi siete l'addetto alla riparazione, per fare il prima possibile come vi regolate?
partite dal primo e via andare?o dal mezzo?o dal fondo?

[Aladar]

Su una tratta di acquedotto lunga 1 km si è verificata una perdita, probabilmente è scoppiata una valvola, in quella tratta ci sono 50 tombini da scoperchiare per vedere se la perdita è lì...uno ogni 20 metri...
voi siete l'addetto alla riparazione, per fare il prima possibile come vi regolate?
partite dal primo e via andare?o dal mezzo?o dal fondo?

Pardo dal 50 e misuro, se la perdita c'è allora sta a monte, altrimenti a valle. Ipotizziamo sia a Valle, vado al 75° e così via. Alla peggio faccio 8 controlli.

[L'anticristo]

Dal mezzo

Poi da 1/4 o 3/4 a seconda del risultato del punto precedente

Ridotto il problema a 1/4 di quello iniziale, si procede esclusivamente

Nel caso peggiore dovrebbero scoperchiarsi log2(50)= 6 tombini

[Darwin]

Su una tratta di acquedotto lunga 1 km si è verificata una perdita, probabilmente è scoppiata una valvola, in quella tratta ci sono 50 tombini da scoperchiare per vedere se la perdita è lì...uno ogni 20 metri...
voi siete l'addetto alla riparazione, per fare il prima possibile come vi regolate?
partite dal primo e via andare?o dal mezzo?o dal fondo?

Dipende dove ti trovi ed il tempo che impieghi a scoperchiare e controllare.

Se il tempo di scoperchiamento e controllo >> superiore allo spostamento devi ottimizzare il primo quindi ricerca dicotomica -> in 6 controlli al massimo la trovi.
Se il tempo di scoperchiamento e controllo inferiore allo spostamento e quindi devi ottimizzare lo spostamento dipende da dove ti trovi in tutti i casi partendo dal 25 o 26 tombino e proseguendo in su o in giu a seconda del controllo al massimo fai 500 metri.

[Darwin]

Su una tratta di acquedotto lunga 1 km si è verificata una perdita, probabilmente è scoppiata una valvola, in quella tratta ci sono 50 tombini da scoperchiare per vedere se la perdita è lì...uno ogni 20 metri...
voi siete l'addetto alla riparazione, per fare il prima possibile come vi regolate?
partite dal primo e via andare?o dal mezzo?o dal fondo?

Se vogliamo essere più precisi dato

m tempo per percorrere un metro
n tempo per scoperchiare e controllare

e con la possibilità di partire in qualsiasi posizione.

Ricerca dicotomica -->
max 500 * m + 6 * n
mediamente 480 * m e 5*n

Ricerca esaustiva partendo da uno dei due tombini centrali -->
max 500 * m + 25 * n
mediamente 250 *m e 12,5 * n.

Se il rapporto n/m è inferiore a 30,6 conviene la ricerca esaustiva altrimenti quella dicotomica