Il lavoro di ricerca scientifica è, senza dubbio, la parte più interessante del nostro percorso formativo. L'idea è di provare già all'università a cimentarsi nella propria area di specializzazione. Ad esempio, gli studenti delle specializzazioni in Ingegneria del Software e Machine Learning spesso svolgono progetti di ricerca in aziende (principalmente JetBrains o Yandex, ma non solo).
In questo post parlerò del mio progetto nel campo della Computer Science. Nell'ambito del lavoro ho studiato e implementato nella pratica approcci alla soluzione di uno dei problemi NP-difficili più noti: il problema della copertura dei vertici.
Attualmente si sta sviluppando molto rapidamente un interessante approccio ai problemi NP-difficili: gli algoritmi parametrizzati. Cercherò di introdurvi a questa tematica, illustrando alcuni semplici algoritmi parametrizzati e descrivendo un potente metodo che mi è stato molto utile. Ho presentato i miei risultati alla competizione PACE Challenge: in base ai test aperti, la mia soluzione occupa il terzo posto, mentre i risultati finali saranno noti il 1° luglio.
Chi sono
Mi chiamo Vasili Alferov, e attualmente sto concludendo il terzo anno all'HSE — San Pietroburgo. Sono appassionato di algoritmi sin dai tempi della scuola, quando studiavo alla scuola 179 di Mosca e partecipavo con successo alle olimpiadi di informatica.
Un numero finito di specialisti in algoritmi parametrizzati entra in un bar...
L'esempio è tratto dal libro
Immaginate di essere un guardiano di un bar in una piccola città. Ogni venerdì, metà della città viene nel vostro bar per rilassarsi, il che vi causa non pochi problemi: dovete espellere i clienti indisciplinati per evitare risse. Alla fine, vi stancate di questo e decidete di prendere misure preventive.
Poiché la città è piccola, sapete esattamente quali coppie di clienti hanno una grande probabilità di litigare se si trovano nello stesso bar. Avete un elenco di n persone che verranno questa sera nel bar. Decidete di non far entrare alcuni cittadini in modo tale che nessuno si tiri in rissa. Allo stesso tempo, i vostri superiori non vogliono perdere guadagni e saranno insoddisfatti se non farai entrare più di k persone.
Sfortunatamente, il compito che vi trovate ad affrontare è un classico problema NP-difficile. Potreste conoscere questo problema come , o come un problema di copertura dei vertici. Per questi problemi, in generale, non si conoscono algoritmi che funzionino in tempi accettabili. A essere precisi, l'ipotesi ETH (Exponential Time Hypothesis), non dimostrata e piuttosto forte, afferma che questo problema non può essere risolto in un tempo 
, cioè che non si può pensare a nulla di significativamente migliore della ricerca esaustiva. Ad esempio, supponiamo che nel tuo bar stia per arrivare n = 1000 persone. Quindi, la ricerca esaustiva comporterebbe 
opzioni, che sono circa 
— esageratamente molte. Per fortuna, la tua direzione ti ha imposto un limite k = 10, così il numero di combinazioni che devi esaminare è molto inferiore: il numero di sottoinsiemi di dieci elementi è 
. È già meglio, ma comunque non sarà possibile contarli in un giorno, nemmeno su un potente cluster.
Per escludere la possibilità di risse con una tale configurazione di relazioni tese tra i clienti del bar, è necessario non far entrare Bob, Daniel e Fyodor. Non esiste una soluzione in cui solo due rimangano fuori.
Significa che è ora di arrendersi e far entrare tutti? Consideriamo altre opzioni. Ad esempio, si può non far entrare solo coloro che potrebbero probabilmente litigare con un numero molto elevato di persone. Se qualcuno può litigare con almeno k + 1 altre persone, allora non può essere sicuramente fatto entrare — altrimenti dovrà essere escluso da tutti k + 1 i cittadini con cui potrebbe litigare, il che sicuramente deluderà la direzione.
Supponiamo che tu abbia escluso tutti coloro che potevi seguendo questo principio. Allora tutti gli altri possono litigare con non più di k persone. Escludendo da loro k persone, puoi prevenire al massimo 
conflitti. Quindi, se più di 
persone partecipano ad almeno un conflitto, sicuramente non potrai prevenirli tutti. Dato che, ovviamente, le persone completamente non conflittuali le farai entrare, dovrai esaminare tutti i sottoinsiemi di dieci delle duecento persone. Sono circa 
, e un numero di operazioni del genere è già possibile da esaminare su un cluster.
Se è possibile accogliere persone del tutto non conflittuali, che dire di quelli che partecipano solo a un conflitto? In realtà, anche loro possono essere accolti, chiudendo la porta di fronte al loro avversario. Infatti, se Alice è in conflitto solo con Bob, accogliendo Alice tra i due, non perdiamo: Bob potrebbe avere altri conflitti, mentre Alice certamente non ne ha. Inoltre, è del tutto senza senso non far entrare entrambe le parti. Dopo tali operazioni, non rimane più di 
ospiti con una sorte irrisolta: in totale abbiamo 
conflitti, ciascuno con due partecipanti e ognuno partecipa ad almeno due. Dunque, rimane da soppesare solamente 
opzioni, che potrebbe essere considerato come mezza giornata su un portatile.
In realtà, con ragionamenti semplici si possono ottenere condizioni ancora più favorevoli. Notiamo che dobbiamo necessariamente risolvere tutte le controversie, cioè per ogni coppia in conflitto scegliere almeno una persona che non accoglieremo. Consideriamo il seguente algoritmo: prendiamo uno qualsiasi dei conflitti, rimuoviamo un partecipante e lanciamo ricorsivamente il processo dal resto, poi rimuoviamo l'altro e anche in questo caso lanciamo ricorsivamente. Poiché ad ogni passo scartiamo qualcuno, l'albero della ricorsione di tale algoritmo è un albero binario di profondità k, quindi complessivamente l'algoritmo funziona in 
, dove n — numero di nodi, mentre m — numero di lati. Nel nostro esempio si tratta di circa dieci milioni, che possono essere calcolati in frazioni di secondo non solo su un portatile, ma anche su un telefono cellulare.
L'esempio sopra riportato è un esempio di algoritmo parametrizzato.Gli algoritmi parametrizzati sono algoritmi che funzionano in tempo f(k) poly(n), dove p — polinomiale, f — una funzione calcolabile arbitraria, e k — un qualche parametro che, molto probabilmente, sarà molto più piccolo della dimensione del problema.
Tutte le considerazioni precedenti a questo algoritmo portano all'esempio di kernelizzazione. — una delle tecniche comuni per la creazione di algoritmi parametrizzati. La kernelizzazione è la riduzione della dimensione del problema a un valore limitato da una funzione del parametro. Il problema ottenuto è spesso chiamato nucleo. Così, attraverso semplici ragionamenti sulle potenze delle vertici, abbiamo ottenuto un nucleo quadratico per il problema del Vertex Cover, parametricamente dimensionato sulla dimensione della risposta. Esistono altri parametri che si possono scegliere per questo problema (ad esempio, Vertex Cover Above LP), ma discuteremo proprio di questo parametro.
Pace Challenge
Competizione (The Parameterized Algorithms and Computational Experiments Challenge) è nato nel 2015 per stabilire un legame tra gli algoritmi parametrizzati e gli approcci pratici utilizzati per risolvere problemi computazionali. Le prime tre competizioni erano dedicate alla ricerca della larghezza degli alberi di un grafo (), alla ricerca dell'albero di Steiner () e alla ricerca di un insieme di vertici che separa i cicli (). Quest'anno, una delle sfide in cui è stato possibile mettersi alla prova era il problema di copertura dei vertici sopra descritto.
La competizione cresce in popolarità di anno in anno. Se le informazioni preliminari sono corrette, quest'anno solo nella competizione per la risoluzione del problema di copertura dei vertici hanno partecipato 24 squadre. Vale la pena sottolineare che la competizione non dura solo alcune ore e neppure una settimana, ma diversi mesi. Le squadre hanno la possibilità di studiare la letteratura, ideare una propria idea originale e tentare di realizzarla. In sostanza, questa competizione rappresenta un lavoro di ricerca. Le idee delle soluzioni più efficaci e la premiazione dei vincitori si svolgeranno in concomitanza con la conferenza (International Symposium on Parameterized and Exact Computation) nell'ambito del più grande incontro annuale di algoritmi in Europa . Maggiori informazioni sulla competizione stessa sono disponibili su , mentre i risultati degli anni passati si trovano .
Schema di soluzione
Per affrontare il problema della copertura dei vertici, ho provato ad applicare algoritmi parametrizzati. Questi di solito consistono in due parti: regole di semplificazione (che idealmente portano a una kernelizzazione) e regole di biforcazione. Le regole di semplificazione sono una pre-elaborazione dell'input in tempo polinomiale. L'obiettivo di queste regole è ridurre il problema a un problema equivalente di dimensioni minori. Le regole di semplificazione sono la parte più costosa dell'algoritmo e l'applicazione di questa parte porta a un tempo di esecuzione complessivo 
invece di un semplice tempo polinomiale. Nel nostro caso, le regole di biforcazione si basano sul fatto che per ogni vertice bisogna scegliere di prendere in considerazione sia esso che il suo vicino.
Lo schema generale è il seguente: applichiamo le regole di semplificazione, poi scegliamo un vertice e facciamo due chiamate ricorsive: nella prima prendiamo il vertice in questione, mentre nell'altra consideriamo tutti i suoi vicini. Questo lo chiamiamo biforcarsi su questo vertice.
A questo schema verrà aggiunta esattamente un'aggiunta nel paragrafo successivo.
Idee per le regole di biforcazione
Discutiamo su come scegliere il vertice su cui avverrà la biforcazione.
L'idea principale è molto affamata dal punto di vista algoritmico: prendiamo il vertice di massimo grado e biforchiamo esattamente su di esso. Perché sembra migliore? Perché nel secondo ramo della chiamata ricorsiva elimineremo in questo modo molti vertici. Ci si può aspettare che rimanga un grafo ridotto e su di esso lavoreremo rapidamente.
Questo approccio, insieme alle semplici tecniche di kernelizzazione già discusse, si presenta piuttosto bene, risolvendo alcuni test di dimensioni nell'ordine di alcune migliaia di vertici. Tuttavia, ad esempio, funziona male per i grafi cubici (cioè grafi in cui il grado di ogni vertice è tre).
C'è un'altra idea, basata su una considerazione abbastanza semplice: se il grafo non è connesso, il problema sui suoi componenti di connettività può essere risolto in modo indipendente, unendo le risposte alla fine. Questa, tra l'altro, è la piccola modifica promessa nello schema, che accelererà notevolmente la soluzione: prima in questo caso lavoravamo per il prodotto dei tempi di conteggio delle risposte dei componenti, ora lavoriamo per la somma. E per accelerare la biforcazione è necessario trasformare un grafo connesso in un grafo non connesso.
Come fare? Se nel grafo c'è un punto di giunzione, bisogna ramificare proprio in quel punto. Un punto di giunzione è un vertice tale che, se rimosso, il grafo perde connettività. Trovare tutti i punti di giunzione in un grafo può essere fatto con un algoritmo classico in tempo lineare. Questo approccio accelera notevolmente la ramificazione.
Rimuovendo uno qualsiasi dei vertici evidenziati, il grafo si frantumerà in componenti connesse.
Lo faremo, ma ci piacerebbe di più. Ad esempio, cercare nel grafo piccoli tagli di vertici e effettuare la ramificazione sui vertici estratti. Il modo più efficiente che conosco per trovare il taglio globale minimo dei vertici è utilizzare l'albero di Gomory-Hu, che si costruisce in tempo cubico. Nella PACE Challenge, la dimensione tipica del grafo è di alcune migliaia di vertici. In tale situazione, in ogni vertice dell'albero di ricorsione bisogna eseguire miliardi di operazioni. Risultato: risolvere il problema nel tempo previsto è praticamente impossibile.
Proviamo a ottimizzare la soluzione. Un taglio minimo tra una coppia di vertici può essere trovato utilizzando qualsiasi algoritmo che costruisce un flusso massimo. Possiamo applicare a tale rete , in pratica funziona molto velocemente. Ho il sospetto che teoricamente si possa dimostrare una stima sul tempo di esecuzione 
, che è già abbastanza accettabile.
Ho provato diverse volte a cercare tagli tra coppie di vertici casuali e prendere il più bilanciato. Sfortunatamente, nei test aperti della PACE Challenge ciò ha portato a risultati deludenti. Ho confrontato con un algoritmo che si ramificava sui vertici di massimo grado, eseguendoli con un limite sulla profondità di discesa. Dopo l'algoritmo che cercava di trovare un taglio in questo modo, rimanevano grafi di dimensioni maggiori. Questo è dovuto al fatto che i tagli risultavano molto sbilanciati: rimuovendo 5-10 vertici, si riusciva a staccarne solo 15-20.
Va notato che negli articoli sui algoritmi teoricamente più veloci si utilizzano tecniche di selezione dei vertici per la ramificazione molto più avanzate. Queste tecniche hanno una realizzazione molto complessa e spesso scarse stime su tempo e memoria. Non sono riuscito a estrarne delle ragionevoli per la pratica.
Come applicare le regole di semplificazione
Abbiamo già idee di kernelizzazione. Ricordo:
- Se c'è un vertice isolato, rimuoverlo.
- Se c'è un vertice di grado 1, rimuoverlo e prendere il suo vicino come risposta.
- Se c'è un vertice di grado almeno k + 1, prenderlo come risposta.
Con i primi due è tutto chiaro, ma con il terzo c'è un trucco. Se nel problema scherzoso del bar ci era stato dato un vincolo superiore su k, nel PACE Challenge bisogna semplicemente trovare una copertura del vertice di dimensione minima. Questa è una tipica trasformazione degli problemi di ricerca (Search Problem) in problemi decisionali (Decision Problem), spesso tra questi due tipi di problemi non si fa differenza. In pratica, se scriviamo un risolutore per il problema della copertura del vertice, la differenza potrebbe esserci. Ad esempio, come nel terzo punto.
Dal punto di vista dell'implementazione, ci sono due modi per procedere. Il primo approccio è chiamato Iterative Deepening. Consiste nel seguente: possiamo iniziare con un ragionevole vincolo inferiore sulla risposta e poi avviare il nostro algoritmo utilizzando questo vincolo come vincolo superiore sulla risposta, senza scendere in ricorsione al di sotto di tale limitazione. Se troviamo una risposta, è garantita come ottimale, altrimenti possiamo aumentare questo vincolo di uno e ripartire.
Il secondo approccio consiste nel mantenere una qualche risposta ottimale attuale e cercare una risposta di dimensioni minori, modificando questo parametro al momento della scoperta k per una maggiore potatura di rami inutili nella ricerca.
Dopo aver condotto diversi esperimenti notturni, mi sono orientato su una combinazione di questi due metodi: inizialmente avvio il mio algoritmo con un certo vincolo sulla profondità di ricerca (scegliendolo in modo che richieda un tempo trascurabile rispetto alla soluzione principale) e utilizzo la migliore soluzione trovata come vincolo superiore sulla risposta — cioè su quel k.
Vertici di grado 2
Con i vertici di grado 0 e 1 ci siamo chiariti. Si scopre che si può fare così anche con i vertici di grado 2, ma per questo, dal grafo, saranno necessarie operazioni più complesse.
Per spiegare questo, è necessario in qualche modo denotare i vertici. Chiamiamo un vertice di grado 2 un vertice v, e i suoi vicini — vertici x e y. Successivamente avremo due casi.
- Quando x e y — vicini. Allora si può prendere come risposta x e y, ma v rimuovere. Infatti, da questo triangolo, è necessario prendere almeno due vertici come risposta e non perderemo sicuramente prendendo x e y: probabilmente hanno ancora vicini, mentre v loro non hanno.
- Quando x e y — non sono i vicini. Allora si afferma che tutti e tre i vertici possono essere uniti in uno. L'idea è che in tal caso ci sia una risposta ottimale, in cui prenderemo o v, oppure entrambi i vertici x e y. Infatti, nel primo caso dovremo includere nella risposta tutti i vicini x e y, mentre nel secondo non è necessario. Questo corrisponde esattamente ai casi in cui non includiamo il vertice unito nella risposta e quando lo facciamo. Resta solo da notare che in entrambi i casi la risposta a tale operazione diminuisce di uno.
È importante notare che tale approccio è piuttosto difficile da implementare correttamente in tempo lineare. L'unione dei vertici è un'operazione complessa, è necessario copiare le liste dei vicini. Se non si fa con attenzione, si può ottenere un tempo di esecuzione asintoticamente non ottimale (ad esempio, se dopo ogni unione si copiano molti archi). Mi sono concentrato sulla ricerca di percorsi interi dai vertici di grado 2 e sull'analisi di molteplici casi speciali, come cicli formati da tali vertici o da tutti tranne uno di questi.
Inoltre, è necessario che questa operazione sia invertibile, in modo da poter ripristinare il grafo al suo stato originale durante il ritorno dalla ricorsione. Per garantire ciò, non ho svuotato le liste degli archi dei vertici uniti, dopo di che sapevo semplicemente quali archi dovevano essere diretti dove. Tale implementazione dei grafi richiede anche attenzione, ma garantisce un tempo lineare corretto. E per grafi con alcune decine di migliaia di archi, ciò pone un'ottima compatibilità con la cache della CPU, il che conferisce grandi vantaggi in termini di velocità.
Nucleo lineare
Infine, la parte più interessante del nucleo.
Iniziamo ricordando che nei grafi bipartiti è possibile cercare il minimo copertura dei vertici in 
. A tal fine è necessario utilizzare l'algoritmo per trovare il massimo accoppiamento, e successivamente utilizzare il teorema .
L'idea del nucleo lineare è la seguente: prima dobbiamo bipartire il grafo, quindi al posto di ogni vertice v creiamo due vertici 
e 
, e invece di ogni arco u — v creiamo due archi 
e 
Il grafo risultante sarà bipartito. Troveremo in esso una copertura minima dei vertici. Alcuni vertici del grafo originale appariranno lì due volte, alcuni solo una volta, e alcuni non appariranno affatto. Il teorema di Nemhauser-Trotter afferma che in tal caso si possono rimuovere i vertici che non appaiono affatto e si possono includere nella risposta quelli che appaiono due volte. Inoltre, afferma che tra i vertici rimanenti (quelli che appaiono una sola volta) bisogna includere almeno la metà.
Appena abbiamo imparato a lasciare nel grafo non più di 2k vertici. È vero, se nella risposta rimanente c'è almeno la metà di tutti i vertici, allora il numero totale di vertici non sarà maggiore di 2k.
Qui sono riuscito a fare un piccolo passo avanti. È chiaro che il nucleo costruito in questo modo dipende da quale copertura minima dei vertici abbiamo utilizzato nel grafo bipartito. Vorrei scegliere quella che riduce al minimo il numero di vertici rimanenti. In passato, questo era possibile solo in un tempo di 
. Ho però ideato un'implementazione di questo algoritmo in un tempo di 
, in questo modo, questo nucleo può essere cercato in grafi di centinaia di migliaia di vertici ad ogni fase del branching.
Risultato
La pratica dimostra che la mia soluzione funziona bene su test con qualche centinaio di vertici e diverse migliaia di archi. Su tali test è possibile aspettarsi che venga trovata una soluzione in mezz'ora. La probabilità di trovare una risposta in un tempo accettabile aumenta in linea di principio se nel grafo ci sono abbastanza vertici di alta grado, ad esempio grado 10 o superiore.
Per partecipare alla competizione, le soluzioni dovevano essere inviate a . A giudicare dalla tabella presentata lì I risultati dei test chiusi saranno resi noti il primo di luglio.
Il lavoro di ricerca scientifica è, probabilmente, la parte più interessante della nostra formazione. L'idea è di provare, ancora all'università, a cimentarsi nella direzione scelta.
Fonte: habr.com
