Un nuovo algoritmo per gli incroci dei grafici, nascosto in bella vista
Lo scorso ottobre, mentre Jacob Holm ed Eva Rotenberg stavano sfogliando un documento che avevano pubblicato alcuni mesi prima, si sono resi conto di essere stati seduti su qualcosa di grande.
Per decenni gli informatici hanno cercato di sviluppare un algoritmo veloce per determinare quando è possibile aggiungere archi a un grafico in modo che rimanga "planare", il che significa che nessuno dei suoi bordi si interseca. Ma il campo non era stato in grado di migliorare un algoritmo pubblicato oltre 20 anni fa.
Holm e Rotenberg furono sorpresi di scoprire che il loro articolo conteneva le informazioni necessarie per fare molto meglio. "Ha risolto uno dei maggiori ostacoli che abbiamo avuto con l'ottenimento di un vero algoritmo", ha detto Holm, uno scienziato informatico presso l'Università di Copenaghen. "Potremmo aver dato via tutto."
I due si sono precipitati a redigere un nuovo documento . Lo hanno presentato a giugno all'ACM Symposium on Theory of Computing , dove hanno descritto un metodo esponenzialmente migliore per verificare se un grafo è planare.
"Il nuovo algoritmo è un notevole tour de force", ha detto Giuseppe Italiano , scienziato informatico presso l'Università Luiss e coautore dell'articolo del 1996 che descrive quello che ora è il secondo algoritmo più veloce. "Quando sono stato coautore di quel documento, non pensavo che questo potesse accadere."
I grafici sono raccolte di nodi collegati da bordi. Possono essere utilizzati per rappresentare qualsiasi cosa, da un social network ai sistemi stradali alle connessioni elettriche su un circuito stampato. Nelle schede a circuito stampato, se il grafico non è planare, significa che due fili si incrociano e vanno in cortocircuito.
Già nel 1913, i grafici planari venivano fuori in un rompicapo chiamato il problema delle tre utilità, pubblicato su The Strand Magazine. Ha chiesto ai lettori di collegare tre case a tre utenze – acqua, gas ed elettricità – senza attraversare nessuno dei collegamenti. Non ci vuole molto per vedere che non può essere fatto.
Ma non è sempre immediatamente ovvio se i grafici più complicati siano planari. Ed è ancora più difficile dire se un grafico planare complicato rimane planare quando inizi ad aggiungere bordi come potresti quando pianifichi un nuovo tratto di autostrada.
Gli informatici hanno cercato un algoritmo in grado di determinare rapidamente se è possibile apportare la modifica desiderata mantenendo il grafico planare e senza controllare ogni singola parte del grafico quando è interessata solo una piccola parte. L'algoritmo del 1996 richiedeva un numero di passaggi computazionali approssimativamente proporzionale alla radice quadrata del numero di nodi nel grafico.
"Molto meglio che farlo da zero ogni volta, ma non è davvero buono", ha detto Holm.
Il nuovo algoritmo controlla la planarità in un numero di passaggi proporzionale al cubo del logaritmo del numero di nodi nel grafico: un miglioramento esponenziale. Holm e Rotenberg, uno scienziato informatico presso l'Università Tecnica della Danimarca, hanno raggiunto la velocità sfruttando una proprietà speciale dei grafici planari che hanno scoperto l'anno scorso.
Per capire il loro metodo, la prima cosa da notare è che lo stesso grafico planare può essere disegnato in più modi . In questi diversi disegni, i collegamenti rimangono gli stessi, ma i bordi potrebbero trovarsi in posizioni diverse l'uno rispetto all'altro.
Ad esempio, puoi trasformare il disegno A nel disegno B capovolgendo il triangolo formato dai nodi 1, 2 e 3 sul bordo che collega i nodi 2 e 3. La sezione superiore del disegno B può anche essere riflessa sui nodi 4 e 5 per produrre il disegno C. I disegni hanno un aspetto diverso, ma sono lo stesso grafico.
Ora immagina di voler inserire un nuovo bordo che collega due nodi in un grafo planare, ad esempio i nodi 1 e 6 nell'esempio sotto. Per farlo, eseguirai una serie di salti mortali. Dalla posizione di partenza a sinistra sono necessari due lanci per spostare il nodo 1 in uno spazio dove può essere collegato al nodo 6 senza incrociare altri bordi.
Nel loro articolo del 2019 Holm e Rotenberg hanno scoperto che alcuni disegni forniscono una posizione di partenza più vantaggiosa per l'inserimento di un bordo rispetto ad altri. Questi "buoni" disegni sono a pochi passi dall'accettare il bordo senza rompere la planarità.
Quello che hanno tardivamente riconosciuto in ottobre è stato che un capovolgimento che ti avvicina alla possibilità di aggiungere un nuovo bordo porta anche il grafico più vicino a somigliare a uno dei buoni disegni che avevano già identificato. Mostrando che una serie di ribaltamenti sposta inevitabilmente un grafico verso un disegno favorevole, il nuovo algoritmo mette un backstop sul numero di ribaltamenti che potresti dover eseguire prima di trovare un modo per inserire un bordo (ammesso che l'inserimento sia possibile) .
"Ci siamo resi conto molto rapidamente che con questa nuova analisi, un algoritmo concettualmente molto, molto semplice risolverà il problema", ha detto Holm.
Il nuovo algoritmo esegue i lanci uno alla volta, alla ricerca di una soluzione. Alla fine, accade una delle due cose: o l'algoritmo trova un modo per inserire il bordo desiderato, o il capovolgimento successivo annulla il capovolgimento precedente – a quel punto l'algoritmo conclude che non c'è modo di aggiungere il bordo.
"Lo chiamiamo il pigro avido", ha spiegato Rotenberg. "Esegue solo le modifiche necessarie per adattarsi al bordo."
Il loro nuovo metodo si avvicina, ma non raggiunge del tutto, le prestazioni del miglior algoritmo possibile (o limite inferiore) per questo tipo di problema. Il nuovo algoritmo deve anche lavorare attraverso troppi passaggi per la maggior parte delle applicazioni del mondo reale, dove i grafici rilevanti sono solitamente abbastanza semplici da controllare con metodi di forza bruta.
Ma per Holm e Rotenberg, la velocità dell'algoritmo è meno importante delle intuizioni che lo hanno accelerato. "Da questa comprensione nasce qualcosa di veloce", ha detto Rotenberg.
E Italiano pensa che alla fine potrebbe aiutare con le applicazioni del mondo reale. "Probabilmente avrà, prima o poi, un impatto anche al di fuori dell'informatica e della matematica", ha detto.
Per quanto riguarda quando arriverà un algoritmo ancora più veloce, nessuno lo sa. Potrebbe richiedere una svolta completamente nuova, o l'ingrediente segreto potrebbe essere già là fuori, in attesa in una pila di vecchi documenti di ricerca.
Questa è la traduzione automatica di un articolo pubblicato su Quanta Magazine all’URL https://www.quantamagazine.org/a-new-algorithm-for-graph-crossings-hiding-in-plain-sight-20200915/ in data Tue, 15 Sep 2020 13:55:10 +0000.