Obbligo di svolta

[giobimbo]

Nella città di Olde Yorke, di cui sotto vediamo una piantina schematica, con le sue 10 piazze ma però priva delle strade che conducono alle altre città, vige un singolare regolamento stradale.

11…00…00…00…00…00
00…00…00…12…00…13
14…00…15…00…16…00
00…00…00…00…00…17
00…18…00…19…00…00
00…00…00…00…00…20
carta stradale di Olde Yorke. Le strade sono indicate dai numeri 00, le piazze con i numeri da 11 a 20.

I lunghi viali rettilinei invitano alla velocità per cui è vietato attraversare una piazza con un percorso diritto, quindi arrivati lì c’e un segnale di direzione consentita a destra e a sinistra. Inoltre per andare da una piazza all’altra bisogna percorrere due tratti di strada tra loro perpendicolari, rallentando ulteriormente la velocità di percorrenza.
Per esempio, se dotiamo la mappa di un sistema di riferimento cartesiano, non possiamo andare direttamente da 11 a 14, ma bisogna fare (1,6) (2,6) (2,5) (2,4) (2,3) (2,2) (1,2) (1,3) (1,4). Indichiamo tale viaggio con (11-18-14).
Non contento di ciò il sindaco ora vuole far mettere sensi unici e obblighi di svolta in modo che la città sia tutta percorribile senza incroci, eliminando così anche i semafori (+sicurezza -spese =rielezione sicura!).

Problema 1. Trovare un percorso che passi per tutte le vie rispettando le regole

Problema 2. Dimostrare che tale percorso circolare è unico

[Gianfranco]

Ciao giobimbo,
non sono sicuro di aver capito le regole, perciò posto un esempio di prova.

giobimbo_incroci.png (25.62 KiB) Visto 9293 volte

Per esempio, se vogliamo fare un percorso che passi per tutte le piazze (non tutte le vie), quello rosso segue le regole?

[giobimbo]

Ricapitolo:
Regola 1. Non si può attraversare una piazza con un percorso diritto.
Regola 2. Per andare da una piazza all’altra bisogna percorrere 2 (due) tratti di strada tra loro perpendicolari.

Quindi, usando il tuo esempio, per il percorso 11-14 hai usato 4 tratti invece di 2: la Regola 2 lo proibisce, bisogna usare solo due tratti.
Lo stesso per 14-18 (3 tratti); 12-13 (4 tratti); 17-20 (4 tratti); 18-19 (4 tratti); 19-20 (3 tratti).
Giusto invece 12-15, 13-16, 16-17.
Per andare da 18 a 19 bisogna passare per 15, o per 17, o per 20.

[Gianfranco]

Grazie giobimbo, ho capito un po' di più ma ho ancora dei dubbi.

Problema 1. Trovare un percorso che passi per tutte le vie rispettando le regole

Significa che il percorso deve passare per tutte le vie della città o soltanto per quelle necessarie a fare il giro delle piazze?

il sindaco ora vuole far mettere sensi unici e obblighi di svolta in modo che la città sia tutta percorribile senza incroci, eliminando così anche i semafori

Non ho capito bene.
Significa che ad ogni incrocio bisogna svoltare o si possono percorrere due o più tratti in linea retta?

[Gianfranco]

Questa soluzione segue le regole?

giobimbo_incroci2.png (16.21 KiB) Visto 9252 volte

[giobimbo]

Questa è la soluzione del Problema 1, giusto. Adesso manca solo la risposta al Problema 2, che è quella che più mi interessa, altrimenti avrei messo un numero maggiore di piazze

Sono anni che faccio dei cruciverba per un settimanale di annunci gratuiti, all’inizio usando carta e matita, poi, facendosi l’impegno sempre più gravoso ho comperato un programma che mi aiutasse. Tempo dopo ricevo una email dai programmatori del cruciverba in cui, oltre ai ringraziamenti per l’acquisto, mi davano un link per scaricare un programma con tanti rompicapo alfanumerici, tra cui questo. Pensavo di farlo pubblicare sul giornale con il titolo “La curva di Peano”, ma volevo saperne di più prima, non affidarmi ciecamente ad un software. Ho trovato una dimostrazione, ovvio, ma penso e spero ce ne sia un’altra più semplice.

[Gianfranco]

Non sono in grado di dimostrare con sicurezza che la soluzione è unica, ma posso spiegare come l'ho trovata, dopo aver capito le regole.

1. Osserviamo che il punto 3 si può colegare soltanto con 1 e 6. La scelta è obbligata.

giobimbo_incroci_d1.png (13.06 KiB) Visto 8948 volte

2. Fatto questo, osserviamo che 1 si può collegare solo con 2. La scelta è obbligata.

giobimbo_incroci_d2.png (13.41 KiB) Visto 8948 volte

3. Fatto questo, osserviamo che 2 si può collegare solo con 5. E 6 solo con 7.
Infatti escludiamo comunque di collegare 6 con 10 e con 9 perché si taglierebbe fuori il 7 (e comunque non sarebbe ammesso in base alle regole)
Dobbiamo escludere anche 2-7 perché si taglierebbe fuori il 6.

giobimbo_incroci_d3.png (13.96 KiB) Visto 8948 volte

4. Fatto questo, osserviamo che il 4 si può collegare solo con l'8 però ci sono due possibilità.
A questo punto, basta un po' di backtracking dominabile con carta e matita, per arrivare alla soluzione.
Il backtracking permette di trovare una soluzione, se c'è, ma non dimostra che è l'unica.

[giobimbo]

Il backtracking permette di trovare una soluzione, se c'è, ma non dimostra che è l'unica.

Esattamente. Quindi la soluzione del Problema 2 è ancora incompleta. Una dimostrazione matematica non si affida solo al provare tutte le possibili strade tornando indietro e ricominciando se si vede che qualcosa non va, è logico. Come le combinazioni al gioco degli scacchi la dimostrazione parte da A per arrivare a B, con eventuali bivi, ma inesorabilmente arriva al traguardo. Spero che tu o qualche altro frequentatore ci arriviate.
Pensavo che applicando l’algoritmo ungherese, usato in Ricerca Operativa, si potessero trovare tutti i percorsi corretti, ma non ha funzionato, (o perlomeno, io) non sono riuscito a farlo funzionare…