Newsgroup: it.hobby.enigmi
Titolo: siti completamente linkati

Questo problema m'e' venuto in mente guardando il disegno di un tetraedro, e
nei cinque minuti successivi non ho trovato soluzioni evidenti, quindi lo
propongo. Magari esiste una soluzione che lo rende banale, ma di immediate
non ne ho trovate.
Ci sono 4 pagine web identiche, ognuna contenente tre link (etichettati come
link 1, link 2 e link 3) che puntano alle tre rimanenti pagine, ma non si sa
in che ordine. Sul browser e' disabilitata l'opzione che evidenzia i link a
pagine gia' visitate, ed anche barra di stato e degli indirizzi, quindi le
quattro pagine non presentano alcun ricordo dei precedenti passaggi.
Qual e' la piu' breve sequenza di link da cliccare per essere sicuri di aver
visitato tutti e quattro i siti?
E se ogni pagina ha quattro link, di cui uno a se stessa?
Ciao, Silv:o)

 wrote:
" 
" Ci sono 4 pagine web identiche, ognuna contenente tre link (etichettati come
" link 1, link 2 e link 3) che puntano alle tre rimanenti pagine, ma non si sa
" in che ordine. 
Cosa vuol dire "identiche"? anche l'ordine dei link e` identico, oppure no?
.mau.

 Cosa vuol dire "identiche"? anche l'ordine dei link e` identico, oppure
no?
Le pagine appaiono tutte cosi':
link 1
link 2
link 3
ma link n e' solo l'etichetta, il testo visualizzato. In realta' i link
puntano ad una delle pagine diversa da quella attualmente in uso. faccio un
esmpio:
nella pagina 1
link 1 -> pag2
link 2 -> pag3
link 3 -> pag4
nella pagina 2
link 1 -> pag4
link 2 -> pag3
link 3 -> pag1
nella pagina 3
link 1 -> pag2
link 2 -> pag1
link 3 -> pag4
nella pagina 4
link 1 -> pag1
link 2 -> pag3
link 3 -> pag2

 wrote:
" > " Ci sono 4 pagine web identiche, ognuna contenente tre link 
" > Cosa vuol dire "identiche"? anche l'ordine dei link e` identico, oppure
" no?
" 
" Le pagine appaiono tutte cosi':
" 
" link 1
" link 2
" link 3
" 
" ma link n e' solo l'etichetta, il testo visualizzato. In realta' i link
" puntano ad una delle pagine diversa da quella attualmente in uso.
Ok. Quanta memoria hai *tu* (non il PC, che abbiamo detto che non ne ha)?
Mi spiego. Comincio dalla pagina 1, clicco link1 e vedo pagina 2.
La prossima volta che vedo pagina 1, so che cliccando link1 vedo pagina 2 o
me lo sono dimenticato?
Ovviamente la risposta sara` diversa nei due casi (e si`, si puo` essere
certi di raggiungere tutte le pagine anche nel secondo caso, che
probabilmente e` il piu` interessante: il problema mi ricorda quello degli
interruttori da accendere alla cieca)
ciao, .mau.

 me lo sono dimenticato?
Hai carta e penna a tua disposizione, se la memoria non ti dovesse
sorreggere. Il punto, come ho detto prima, e' che conosco la sequenza dei
link cliccati, ma non la sequenza delle pagine visitate.
Comunque la variante con 4 link mi pare piu' interessante, nella prima il
fatto di sapere con sicurezza che ad ogni clic corrisponde un salto di
pagina facilita molto le cose.
Spero di essere stato chiaro
Ciao, Silv:o)

 Ciao, Silv:o)
Utilizzo per i link la notazione (axb) con il significato:
partendo dalla pagina a, cliccando su x, arrivo alla pagina b.
Considerando il secondo caso (possibilita' di autolink), una sequenza
iniziale di click potrebbe essere 1,2,2,3,3,4 che mi da la certezza di
visitare almeno tre pagine.
Sia (a) la pagina di partenza; ho due possibilita': (a1a) ed (a1b).
Se (a1a)
il secondo click (2) mi porta ad una pagina diversa, che chiamo b (a2b);
con il terzo click (2) puo' essere:
(b2c) ed ecco la terza pagina;
(b2b), in questo caso il primo 3 mi porta a (c), oppure ad (a) e con il
secondo 3 arrivo a (c);
(b2a), ed il quarto click (3) e' necessariamente del tipo (a3c).
Se (a1b)
con il secondo click (2) posso avere:
(b2c), OK;
(b2a), seguito da: (a2c), oppure (a2a) e (a3c);
(b2b) seguito da un altro (b2b), quindi (b3c), oppure (b3a) e (a3c), oppure
(b3a) (a3a) (a4c)
salvo errori od omissioni
Con mooooolti tentativi, credo che si potrebbe arrivare alla sequenza che
garantisce le quattro pagine, ma probabilmente esiste un metodo piu'
elegante.
_____________
Propongo una variante (di cui non conosco la risposta):
Partendo dalla pagina (a), esiste una sequenza (non nulla) di click che
garantisce di terminare nella stessa pagina (a) di partenza (nei due casi,
con e senza autolink)?
ciao
paolo

 wrote:
" >La prossima volta che vedo pagina 1
" 
" non posso avere alcuna conferma che sono tornato alla pagina 1
Occhei. In massimo nove click (benfatti :-) ) posso essere certo di avere
visitato tutte le pagine, nella versione con tre link per pagina.
L'algoritmo tra qualche giorno :-)
Non ho ancora studiato la versione con quattro link, ma dovrebbe anch'essa
essere possibile.
Non saprei dove iniziare a trovare un algoritmo per il caso generale di N
pagine e N (oppure N-1) link).
ciao, .mau.

 wrote:
" Propongo una variante (di cui non conosco la risposta):
" Partendo dalla pagina (a), esiste una sequenza (non nulla) di click che
" garantisce di terminare nella stessa pagina (a) di partenza (nei due casi,
" con e senza autolink)?
Secondo me no.
.mau.

 L'algoritmo tra qualche giorno :-)
Si puo' fare agevolmente con 8.
E' un grafo orientato con 4 nodi A,B,C,D
Consideriamo solo 3 nodi A,B,C e cerchiamo una strategia che ci permetta
di uscire dal piu' lungo loop possibile in A,B,C assicurando l'aggancio
del quarto nodo D. Con 1,2,3 indico i percorsi uscenti da ciascun nodo.
Evidentemente non conviene ripetere una coppia di links piu' di una
volta. Sequenze come. 1,1,1,1... 1,2,1,2... sono dispersive, potremmo
palleggiare fra 2 sole pagine.
Battezzando A il nodo di partenza procedo con:
1,1,2,2,3,3  Non posso qui disegnare il grafo, ma e' facile verificare
che se non sono ancora uscito da A,B,C
sono sicuramente tornato in A. Ci sono solo 2 casi:
1) A,B,A,C,B,C,A  in questo caso passerei in D con 3.
2) A,B,C,B,A,C,A  in questo caso passerei in D con 2.
A questo punto clicco su 3. Nel caso 1) passo in D.
Con il massimo della sfiga torno in C, da dove sono sicuro di
guadagnarmi D eseguendo 1.
La sequenza diventa : 1,1,2,2,3,3,3,1 o tutte quelle simmetriche a
questa.
:) dario
PS. Bravo Silvio!

PS. Bravo Silvio!
OK. L'idea e' buona, quindi tutti al lavoro. C'e' ancora da sistemare la
variante 4X4, prima di tentare qualche generalizzazione. Se non dovessimo
riuscire a trovare una regola generale, credo che gia' il 5X4 o 5X5 siano
casi abbastanza impegnativi da affrontare a mano.
Ciao, Silv:o)

con e senza autolink)?
Sicuramente no.
Qualunque sia la sequenza fornita, e' sempre facile esibire un controesempio
che, con quella sequenza, non termina nel sito di partenza. Infatti se la
sequenza prevede che per ultimo vada cliccato il "link x", allora basta
settare i collegamenti in modo che nessuno dei "link x" delle quattro pagine
punti alla pagina iniziale.
Ciao, Silv:o)

Ho creato un mostro!!!
Nella versione 4X4 (4 pagine con 4 link) non so assolutamente dove
cominciare per cercare la sequenza minima.
Ma questo non sarebbe assolutamente grave. Non sapendo risolvere la variante
di ottimizzazione, ho provato la variante piu' semplice, quella di ricerca:
"Trovare almeno una sequenza di link che garantisca la visita di tutti i
siti". Nessuna idea neanche per questa variante. Allora ho aggredito la
versione decisionale del problema: "Data una sequenza di link, verificare
che garantisca la visita di tutti e quattro i siti". E qui, dove la fantasia
e' mancata, la forza bruta mi ha sorretto.
Ho scritto una funzione che, presa in input una stringa, la verifica su
ognuno dei possibili (4!)^4 grafi (sono solo 331.776 :), e termina mostrando
il primo grafo, se lo trova, che abbia almeno un nodo mai visitato al
termine della sequenza.
Ho cominciato a provare con sequenze piu' o meno casuali di 10-12 click, poi
ho aumentato fino ad una ventina: niente!!!!! allora o pensato ad un bug del
programma, ma mi pareva tutto a posto. Provo ad aumentare i click.
Finalmente con la stringa "12233343322224312231442131" mi esaurisce tutti i
trecentomila grafi senza fermarsi mai. Non ho certo pensato di aver trovato
un minimo, ma credevo di trovare facilmente qualcosa di piu' corto pestando
le dita a caso sui primi 4 numeri.
Avete qualche approccio piu' originale? Possibile che un problema
all'apparenza cosi' semplice presenti tante difficolta' gia' a dimensioni
cosi' contenute? Soprattutto dopo che la versione senza autolink si e'
dimostrata decisamente abbordabile. Di aggredirlo esminando tutte le
possibili sequenze non se ne parla neanche, la complessita sarebbe
iper-esponenziale.
Per chi ha nozioni di complessita' computazionale: che sia un problema
NP-completo?
Ciao, Silv:o)

Sono arrivato a 17 click ("33321324434421122" dopo 15 mila tentativi a caso)
Ormai e' un ora che sta provando sequenze casuali di 16 cifre, ne ha
macinate piu' di centomila senza trovarne una buona.
Ciao, Silv:o)

 wrote:
" Finalmente con la stringa "12233343322224312231442131" mi esaurisce tutti i
" trecentomila grafi senza fermarsi mai. Non ho certo pensato di aver trovato
" un minimo, ma credevo di trovare facilmente qualcosa di piu' corto pestando
" le dita a caso sui primi 4 numeri.
Guarda, io ho provato ad affrontare l'algoritmo generale n*n, cercando di
trovare almeno una soluzione (sono un matematico, in fin dei conti) e sono
relativamente certo che questa sia una soluzione: (quando scrivo
(k){stringa} intendo ripetere k volte la stringa)
     ...(n-1){(n-1){(n-1){(n-1){1}2}3}4}...
che e` una funzione che cresce mica male. 
ciao, .mau.

che e` una funzione che cresce mica male.
Gia', cresce come la somma delle prime n potenze di (n-1), che e'
dell'ordine di n^n.
Se non ho capito male pero', gia' per n=3 non funziona.
La sequenza dovrebbe essere (2){(2){1}2}3 = {112}{112}3
oppure (2){(2){(2){1}2}3} = {1121123}{1121123}
Considera il seguente caso:
A:           B:           C:
link1 => A   link1 => A   qualsiasi
link2 => B   link2 => C
link3 => C   link3 => B
Se gli applichiamo la prima sequenza otteniamo, a partire da A:
AABAABB, con C che non viene visitato.
Anche con la versione raddoppiata le cose vanno allo stesso modo.
A ben guardare non va neanche per n=4, con un grafo praticamente identico,
per cui credo proprio di aver male interpretato la tua notazione.
Ciao, Silv:o)

 wrote:
" >     ...(n-1){(n-1){(n-1){(n-1){1}2}3}4}...
" >
" >che e` una funzione che cresce mica male.
" 
" Gia', cresce come la somma delle prime n potenze di (n-1), che e'
" dell'ordine di n^n.
" 
" Se non ho capito male pero', gia' per n=3 non funziona.
" 
" La sequenza dovrebbe essere (2){(2){1}2}3 = {112}{112}3
Allora l'ho scritta male. Per n=3 la successione e` 
112112113
per n=4 e` 
1112111211121113 1112111211121113 1112111211121113 1112111211121114
e cosi` via.
L'idea e` che con gli (n-1)1 o sono stato cosi` fortunato da fare gia`
tutto il giro, o mi sono trovato in un loop. A questo punto passo metto un
2 e vado avanti di nuovo a fare tutto il giro.
Non sono ancora sicuro di non avere commesso uno sbaglio, ma l'idea e` che
in un modo o nell'altro quando tocco l'ultimo link sono sicuro che tutte le
altre possibilita` sono state scartate.
.mau.

 1112111211121113 1112111211121113 1112111211121113 1112111211121114
Se la cosa ti puo' confortare, ho provato a dare in pasto questa stringa
alla funzione di convalida, e non ha trovato nulla da eccepire.
Questo non vuol dire che funziona per ogni n, ma la versione di ricerca del
problema potrebbe essere risolta. Hai qualche idea per l'ottimizzazione? La
differenza tra i 64 simboli della tua stringa ed i 17 che ho trovato
empiriticamente e' tale da lasciare ampio spazio...
Ciao, Silv:o)

 wrote:
" > 1112111211121113 1112111211121113 1112111211121113 1112111211121114
" 
" Se la cosa ti puo' confortare, ho provato a dare in pasto questa stringa
" alla funzione di convalida, e non ha trovato nulla da eccepire.
E` gia` qualcosa :-)
" Questo non vuol dire che funziona per ogni n, ma la versione di ricerca del
" problema potrebbe essere risolta. Hai qualche idea per l'ottimizzazione? La
" differenza tra i 64 simboli della tua stringa ed i 17 che ho trovato
" empiriticamente e' tale da lasciare ampio spazio...
Su quello non ci sono dubbi :-)
D'altra parte, penso che sia chiaro che io - da buon matematico - sono gia`
felice di dimostrare l'esistenza di una soluzione, addirittura con un
metodo costruttivo!
scherzi a parte, non ho idea di dove iniziare per ridurre la dimensione
della stringa, anche se sono convinto che esista una soluzione di
complessita O(n^2) o alla peggio O(n^3). 
ciao, .mau.

questa.
Il problema e' approdato su it.fan.dewdeney, dove ci sono stati interessanti
interventi. Ecco quanto trovato da Matteo Cortese, che usa le lettere al
posto dei numeri:
" Poi mi sono stufato e le ho fatte cercare al computer, il quale ha trovato
" queste quattro sequenze di 7 scelte:
"    AABCCCB
"    ABBBABC
"    ABBBCBA
"    ABCBBBA
Ciao, Silv:o)