18/01/20

Le autostrade di Corruptonia. 1: Un grosso aiuto ***

Lungi da me entrare nelle problematiche dei grafi, sviscerate e trattate con grande profondità dal nostro Umberto. L'intenzione del quiz sulle autostrade è quello di introdurre vari tipi di percorso, assegnando un certo numero di punti da toccare.

Nel nostro caso i punti vengono identificati con delle città e le linee che li congiungono sono delle vere e proprie strade, ma il succo generale rimane inalterato, anche se trattato in maniera estremamente semplificata. Ricordo solo alcuni tipi di percorsi che potrebbero essere affrontati.

Sistema ad albero di copertura: un sistema di segmenti (rimaniamo sempre nel caso di segmenti rettilinei) che uniscono tra loro tutte le città. Forse è il caso più comune nella nostra realtà quotidiana.

Sistema ad albero di copertura minimo: il sistema che permette l'unione di tutte le città, che abbia la minima lunghezza totale. Sembrerebbe il nostro caso... ma non è proprio così.

Percorso hamiltoniano: un percorso che colleghi tutte le città, passando una e una sola volta da tutte loro. Nel caso si ritorni al punto di partenza lo chiamiamo ciclo.

Percorso hamiltoniano minimo: uguale a quello precedente, ma di lunghezza minima (anche questo può diventare un ciclo). Siamo di fronte al ben noto problema del commesso viaggiatore, che il Bombo (quel grosso e simpatico insetto simile all'ape) sa risolvere con estrema noncuranza.

Il Bombo, un fantastico "matematico".
Il Bombo, un fantastico "matematico".

Sono tutti problemi estremamente complicati nella loro generalizzazione e sconfinano in una matematica veramente superiore.

Tuttavia, esiste un ulteriore sistema applicabile a una rete autostradale: quello che può utilizzare non soltanto dei tratti rettilinei tra città e città, ma anche punti di snodo aggiuntivi. In questo caso le soluzioni per i nostri 4 casi diventano ancora più convenienti. Mentre la prima e l'ultima sono abbastanza ovvie, non lo sono quelle relative al quadrato e soprattutto al pentagono. Può essere utile pensare agli angoli al vertice e a come dovrebbero presentarsi gli eventuali punti di snodo. Ovviamente, ogni segmento autostradale deve essere sempre rettilineo...

Oltre alla soluzione concettuale, gradirei il calcolo esatto delle distanze totali caso per caso, prendendo come unità il lato del poligono considerato. Il tentativo di trovare formule ricorrenti è un problema in parte ancora insoluto, per quanto io ne sappia (Umberto potrebbe confermarlo)...

 

 

4 commenti

  1. Umberto

    no, non esistono. Avrei voluto tempo fa scrivere qualcosa. Ma sono problemi che non si possono

    tanto generalizzare. Comunque non si sa mai

  2. grazie Umberto... magari ci riuscirai tu!

  3. umberto

    purtroppo non sono ancora i forma

  4. fabpan

    Non mi sono ancora arreso. La soluzione trovata per il triangolo e quadrato non va bene per il pentagono che ha un numero dispari di vertici. Per il pentagono ci vuole qualcosa di diverso.

    Ho provato ha posizionare in modo generico gli snodi rispettando comunque la simmetria del pentagono. Poi ho cercato di ottimizzare la loro posizione per trovare il percorso minimo che collega i vertici.

    Il risultato è in questa figura.

    La lunghezza è circa 3,89 l. Quello che sembra più interressante è che, anche in questo caso, i rami che escono dagli snodi formano 3 angoli di 120º come per il quadrato e triangolo. Che questa regolarità fosse presente nelle altre figure veniva dal fatto che si ripeteva più volte la stessa struttura. In questo caso le strutture utilizzate sono diverse, ma la regolarità sembra rimanere. Dico sembra perchè, avendo risolto il problema numericamente, rimane una piccola incertezza sul risultato.

    Questa regolarità fa pensare che ci possa essere un legame tra snodi con rami a 120º e porcorsi ottimali. Legame che però non ho trovato.

    Aggiungo qualcosa sul percorso fatto per trovare il posizionamento degli snodi.

    Per la simmetrie del pentagono, uno degli snodi deve essere su un asse di simmetria, diciamo a distanza w dal centro. Gli altri 2 simmetrici rispetto all'asse che assumo come asse delle ascisse. Quindi, le coordinate generiche dei 3 snodi dovrebbero essere (w,0), (x,y) e (x,-y). Date queste coordinate è possibile trovare l'espressione della lunghezza del percorso come funzione di w,x,y, L(w,x,y). Ora occorre trovare la tripletta w,x,y che rende minima questa lunghezza. Fino a qui è possibile procedere manualmente, nei passaggi successivi sono dovuto ricorrere a strumenti informatici. Una possibilità è quella di risolvere numericamente il sistema di 3 equazioni che si ottengono derivando parzialmente L(w,x,y) rispetto a ciscune delle 3 variabili. Un'altra possibilità è quella di inserire la funzione in uno strumento informatico di ottimizzazione numerica che fornisce direttamente il risultato.

    Dovo dire che sono positivamente sorpreso della ricchezza di strumenti informatici disponibili legalmente in rete. In questo caso direi il lato "oscuro" di Internet, in contrasto con le nefaste scie luminose lasciate dai satelliti.

Lascia un commento

*

:wink: :twisted: :roll: :oops: :mrgreen: :lol: :idea: :evil: :cry: :arrow: :?: :-| :-x :-o :-P :-D :-? :) :( :!: 8-O 8)

 

Questo sito usa Akismet per ridurre lo spam. Scopri come i tuoi dati vengono elaborati.