Newsgroup: it.hobby.enigmi
Titolo: catena telefonica

Propongo un problema, di cui non ho ancora elaborato una soluzione 
convincente (e che potrebbe essere già stato trattato su questo NG):
Sia dato un gruppo di n amici e si voglia organizzare una catena 
telefonica con la massima efficienza, ossia con la maggior probabilità 
che ciascuno sia raggiunto da un certo messaggio (pic-nic in campagna, 
partita di calcetto, shopping di gruppo, etc.). Il vincolo che si pone è 
che ciascuno debba fare sempre e solo 2 telefonate, a 2 persone diverse 
e con una certa probabilità p per ogni telefonata di trovare il 
destinatario.
Qual è lo schema migliore di telefonate programmate?
(Ovviamente si può generalizzare a k telefonate per ciascuno)
Dade :)

 Qual è lo schema migliore di telefonate programmate?
Ho qualche domanda di chiarimento:
    -  la notizia parte da una persona sola?
    -  lo schema può cambiare in funzione di una chiamata specifica? Cerchi,
cioè, uno schema fisso o magari può accadere che A chiami B e gli dica:
"chiama C e digli che chiamasse D, se lo trova chiamasse anche E mentre se
non lo trova chiami F con la seconda telefonata".
    -  chiamo A e non lo trovo, se lo richiamo una seconda volta sono sicuro
di non trovarlo oppure ho probabilità p di trovarlo?
    -  con schema *migliore* intendi quello con la piu alta probabilità di
raggiungere tutti?
Visto che la domanda posta mi sembra abbastanza tosta è meglio che lavoriamo
con gli stessi presupposti.
Un saluto,
Gabriele

 raggiungere tutti?
No, quello con il numero medio più alto di persone raggiunte dalla catena.
Dade :)

Ripeto che il problema mi sembra veramente tosto da
analizzare ma provo a spararne una;  mi sembra che
un buono schema, per un numero dispari di persone,
sia il seguente: siano A, B, C, .....  il gruppo di amici,
immaginiamoli messi in cerchio  (per esempio 11 persone)
                         A
         M                               B
L                                                  C
I                                                    D
       H                                 E
                  G           F
Ognuno chiama la persona che lo segue in senso orario  e quella
posta a due posti di distanza in senso antiorario, nell'esempio A
chiama B e L,   B chiama C e M,  C chiama D ed A ecc.....
Se invece le persone sono in numero pari possiamo fare in modo
che ognuno chiami la persona che lo segue in senso orario e quella
posta a tre posti di distanza in senso antiorario.
Con questi schemi si crea una catena lineare oraria ed un altra
antioraria fatta a balzi.
Non ho però la piu pallida idea di come calcolare la *bontà* di
questo schema.
Notiamo che, ricercando una catena fissa, questa deve essere
indipendente da chi la inizia e quindi anche questi riceverà due
chiamate superflue che, però, non si possono evitare.
GaS


Assomiglia molto alla soluzione che avevo trovato io: ciascuno chiama le 
2 persone che lo seguono nella catena. In questo modo non importa se il 
numero n sia pari o dispari.
Un'altra mia soluzione prevede che si chiami il successivo e quello 
"circa" diametralmente opposto: in questo modo se da qualche parte si 
spezza la prima catena, questa potrà sempre ripartire dopo "circa" mezzo 
giro dell'altra. Qui i "circa" sono dovuti alla casistica n pari/dispari.
Non riesco, però, ad escogitare un metodo per controllare quale sia la 
soluzione più efficiente, se non quella di scrivere un programma per 
effettuare simulazioni a tappeto.
Dade :)

 ha scritto nel messaggio
news:bodejs$1d9ag4$1...@ID-92928.news.uni-berlin.de...
