La ricerca scientifica è probabilmente la parte più interessante del nostro percorso di studi. L'idea è di mettersi alla prova in un settore scelto già durante l'università. Ad esempio, gli studenti delle aree di 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 nell'ambito della Informatica. Durante il lavoro, ho studiato e messo in pratica approcci per risolvere uno dei problemi NP-difficili più noti: il problema del vertice coperto.
Attualmente, si sta sviluppando rapidamente un approccio interessante per i problemi NP-difficili: gli algoritmi parametrizzati. Cercherò di introdurvi nell'argomento, illustrando alcuni semplici algoritmi parametrizzati e descrivendo un potente metodo che mi è stato di grande aiuto. 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.
Su di me
Mi chiamo Vasily Alfyorov, sto per completare il terzo anno all'HSE di San Pietroburgo. Sono appassionato di algoritmi fin dai tempi della scuola, quando andavo alla 179ª scuola 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 da un libro
Immaginate di essere il guardiano di un bar in una piccola città. Ogni venerdì metà della città viene nel vostro bar per rilassarsi, il che comporta non pochi problemi: dovete cacciare fuori i clienti molesti per evitare risse. Alla fine, vi stancate di tutto ciò e decidete di adottare misure preventive.
Poiché la vostra città è piccola, sapete esattamente quali coppie di clienti hanno una grande probabilità di litigare se si trovano nel bar insieme. Avete un elenco di n persone che verranno stasera nel bar. Decidete di non far entrare alcune persone in modo che nessuno possa litigare. D'altra parte, il vostro capo non vuole perdere profitto e sarà scontento se non farete entrare più di k persone.
Purtroppo, il compito che vi si presenta è un classico problema NP-difficile. Potreste conoscerlo come , o come problema di copertura dei vertici. Per tali problemi in generale non si conoscono algoritmi che funzionano in un tempo ragionevole. A dire il vero, una congettura non dimostrata e piuttosto forte chiamata ETH (Ipotesi del Tempo Esponenziale) suggerisce che questo problema non può essere risolto in un tempo 
, cioè che non c'è nulla di significativamente migliore del completo controllo. Ad esempio, supponiamo che al bar vogliano venire n = 1000 persone. Allora il numero totale di combinazioni sarà 
opzioni, che è circa 
— un'enormità. Fortunatamente, la vostra direzione vi ha imposto un vincolo di k = 10, quindi il numero di combinazioni da considerare è molto minore: il numero di sottoinsiemi di dieci elementi è 
. Questo è già meglio, ma non si potrà comunque arrivare a un conteggio in un giorno, anche su un cluster potente.
Per escludere la possibilità di risse in tale configurazione di rapporti tesi tra i visitatori del bar, bisogna non far entrare Bob, Daniel e Fyodor. Non esistono soluzioni in cui solo due di loro rimangano esclusi.
Significa questo che è ora di arrendersi e far entrare tutti? Consideriamo altre opzioni. Ad esempio, si può non far entrare solo chi probabilmente combatterà con un numero molto elevato di persone. Se qualcuno può combattere almeno con k + 1 un'altra persona, allora sicuramente non deve essere fatto entrare, altrimenti sarà necessario non far entrare tutti k + 1 i cittadini con cui potrebbe combattere, il che già deluderà certamente la direzione.
Supponiamo che tu abbia escluso tutti quelli che potevi secondo questo principio. Allora tutti gli altri possono combattere con non più di k persone. Escludendo da essi k la gente, puoi prevenire al massimo 
conflitti. Quindi, se più di 
persone partecipano a almeno un conflitto, allora sicuramente non riuscirai a prevenirli tutti. Poiché, è ovvio, che le persone non conflittuali le farai entrare, è necessario esaminare tutti i sottoinsiemi di dimensione dieci da duecento persone. Ce ne sono circa 
, e tale numero di operazioni è già gestibile in un cluster.
Se è possibile accettare persone completamente non conflittuali, cosa dire di quelle che partecipano a un solo conflitto? In realtà, anche loro possono essere accolti, chiudendo le porte davanti ai loro avversari. È vero, se Alice è in conflitto solo con Bob, allora, se facciamo entrare Alice, non perderemo: Bob potrebbe avere altri conflitti, mentre Alice sicuramente non ne ha. Inoltre, è del tutto inutile non far entrare entrambi. Dopo tali operazioni, rimangono al massimo 
ospiti con un destino irrisolto: in totale abbiamo 
conflitti, in ciascuno ci sono due partecipanti e ognuno partecipa ad almeno due. Quindi, rimane da considerare solo 
opzioni, il che potrebbe richiedere solo mezza giornata su un portatile.
In effetti, attraverso ragionamenti semplici si possono ottenere condizioni ancora più vantaggiose. È importante notare che dobbiamo necessariamente risolvere tutte le controversie, ovvero scegliere almeno una persona da ogni coppia in conflitto da escludere. Consideriamo il seguente algoritmo: prendiamo qualsiasi conflitto, rimuoviamo un partecipante e eseguiamo ricorsivamente l'algoritmo sul resto, poi rimuoviamo l'altro e facciamo lo stesso in modo ricorsivo. Poiché in ogni passaggio escludiamo qualcuno, l'albero di ricorsione di questo algoritmo è un albero binario di profondità k, quindi l'algoritmo funziona in totale per 
, dove n — numero di vertici, e m — numero di archi. Nel nostro esempio, sono circa dieci milioni, che possono essere calcolati in frazioni di secondo non solo su un laptop, ma anche su un telefono cellulare.
L'esempio sopra riportato è un esempio di algoritmo parametrizzato. Gli algoritmi parametrizzati sono algoritmi che funzionano in un tempo f(k) poly(n), dove p — polinomiale, f — qualche funzione calcolabile e k — un parametro che, molto probabilmente, sarà molto più piccolo della dimensione del problema.
Tutti i ragionamenti fino a questo algoritmo portano all'esempio di kernalizzazione — 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 risultante viene spesso chiamato nucleo. Così, mediante semplici ragionamenti sulle potenze dei vertici, abbiamo ottenuto un nucleo quadratico per il problema del Vertex Cover, parametrizzato in base alla dimensione della risposta. Esistono altri parametri che possono essere scelti per questo problema (ad esempio, il Vertex Cover Above LP), ma discuteremo solo di questo parametro.
Pace Challenge
Competizione (The Parameterized Algorithms and Computational Experiments Challenge) è nato nel 2015 per stabilire un legame tra algoritmi parametrizzati e approcci utilizzati nella pratica per risolvere problemi computazionali. Le prime tre competizioni sono state dedicate alla ricerca della larghezza dell'albero del grafo (), alla ricerca dell'albero di Steiner () e alla ricerca di un insieme di vertici che taglia cicli (). Quest'anno una delle sfide in cui si poteva mettere alla prova è stata quella del vertex cover descritta sopra.
La competizione sta guadagnando popolarità di anno in anno. Se le informazioni preliminari sono corrette, quest'anno hanno partecipato ben 24 squadre alla competizione per la risoluzione del problema del copertura verticile. Vale la pena notare che la competizione non dura solo alcune ore, né una settimana, ma diversi mesi. Le squadre hanno la possibilità di studiare la letteratura, sviluppare idee originali e cercare di realizzarle. In sostanza, questa competizione rappresenta un lavoro di ricerca. Le idee delle soluzioni più efficaci e la premiazione dei vincitori avverrà insieme alla conferenza (International Symposium on Parameterized and Exact Computation) nell'ambito del più grande incontro annuale di algoritmi in Europa . Maggiori informazioni sulla competizione possono essere trovate su , mentre i risultati degli anni passati sono disponibili .
Schema della soluzione
Per affrontare il problema della copertura dei vertici, ho cercato di applicare algoritmi parametrizzati. Questi generalmente consistono in due parti: regole di semplificazione (che idealmente portano a una kernelizzazione) e regole di divisione. Le regole di semplificazione sono una preelaborazione dell'input in tempo polinomiale. L'obiettivo dell'applicazione di tali regole è di ridurre il problema a uno equivalente di dimensione minore. Le regole di semplificazione rappresentano la parte più onerosa dell'algoritmo, e l'applicazione proprio di questa parte porta a un tempo di esecuzione complessivo 
invece di un semplice tempo polinomiale. Nel nostro caso, le regole di divisione si basano sul fatto che per ogni vertice è necessario rispondere con esso o con uno dei suoi vicini.
Lo schema generale è il seguente: applichiamo le regole di semplificazione, poi scegliamo un vertice qualsiasi e facciamo due chiamate ricorsive: nella prima prendiamo il vertice in risposta, mentre nella seconda prendiamo tutti i suoi vicini. Questo lo chiamiamo diramarsi (branching) su quel vertice.
A questo schema sarà aggiunto esattamente un complemento nel paragrafo successivo.
Idee per le regole di divisione (branching)
Discutiamo su come scegliere il vertice su cui avverrà la suddivisione.
L'idea principale è molto golosa in senso algoritmico: prendiamo il vertice di massima grado e suddividiamoci proprio su di esso. Perché sembra che sia meglio? Perché, nella seconda branca della chiamata ricorsiva, in questo modo elimineremo un gran numero di vertici. Possiamo aspettarci che rimanga un grafo piccolo su cui lavoreremo rapidamente.
Questo approccio, insieme alle tecniche di kernelizzazione già discusse, si comporta abbastanza bene e risolve alcuni test con dimensioni di diverse migliaia di vertici. Tuttavia, ad esempio, funziona male per i grafi cubici (cioè quelli in cui il grado di ogni vertice è uguale a tre).
C'è un'altra idea basata su un concetto piuttosto semplice: se il grafo è disconnesso, il problema sulle sue 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 accelera notevolmente la soluzione: prima in questo caso lavoravamo con il prodotto dei tempi di conteggio delle risposte delle componenti, ora lavoriamo invece con la somma. E per velocizzare il branching è necessario trasformare un grafo connesso in uno disconnesso.
Come farlo? Se nel grafo c'è un punto di giunzione, bisogna effettuare il branching proprio su di esso. Un punto di giunzione è un vertice tale che, se rimosso, il grafo perde la connettività. Trovare tutti i punti di giunzione in un grafo può essere fatto utilizzando l'algoritmo classico in tempo lineare. Questo approccio accelera notevolmente il branching.
Alla rimozione di uno qualsiasi dei vertici evidenziati, il grafo si suddividerà in componenti di connettività.
Lo faremo, ma vogliamo di più. Ad esempio, cercare nel grafo piccoli tagli sui vertici e effettuare la scomposizione attraverso di essi. Il modo più efficace che conosco per trovare il taglio globale minimo sui vertici è utilizzare l'albero di Gomory-Hu, che si costruisce in tempo cubico. Nel PACE Challenge, la dimensione tipica del grafo è di diverse migliaia di vertici. In questa situazione, in ogni vertice dell'albero di ricorsione è necessario eseguire miliardi di operazioni. Quindi, risolvere il problema nel tempo assegnato è semplicemente impossibile.
Proviamo a ottimizzare la soluzione. Il taglio minimo tra una coppia di vertici può essere trovato utilizzando qualsiasi algoritmo che costruisca un flusso massimo. Possiamo applicare su una rete simile , che in pratica funziona molto rapidamente. Ho il sospetto che sia teoricamente possibile dimostrare una stima sul tempo di esecuzione 
, il che è già abbastanza accettabile.
Ho provato diverse volte a cercare separazioni tra coppie di vertici casuali, cercando di ottenere la più bilanciata. Sfortunatamente, questo ha avuto risultati scarsi nei test aperti del PACE Challenge. Ho confrontato con un algoritmo che si limitava ai vertici di massimo grado, eseguendo il tutto con una limitazione sulla profondità di discesa. Dopo un algoritmo che tentava di trovare una separazione in questo modo, restavano grafi di dimensioni maggiori. Ciò è dovuto al fatto che le separazioni risultavano molto sbilanciate: rimuovendo da 5 a 10 vertici, si riusciva a separare solo 15-20.
È importante notare che negli articoli sulle teorie dei più rapidi algoritmi vengono utilizzate tecniche di selezione dei vertici per la divisione molto più avanzate. Queste tecniche hanno implementazioni molto complesse e spesso scarse valutazioni in termini di tempo e memoria. Non sono riuscito a isolare da esse approcci ragionevoli per l'uso pratico.
Come applicare le regole di semplificazione
Abbiamo già delle idee per la 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 le prime due è tutto chiaro, ma con la terza c'è un trucco. Se nel problema scherzoso del bar ci era stata data una limitazione superiore su k, nel PACE Challenge bisogna solo trovare un insieme di vertici di dimensione minima. Questo è un tipico esempio di trasformazione dei problemi di ricerca (Search Problem) in problemi di decisione (Decision Problem), spesso non si fa distinzione tra i due tipi di problemi. Nella pratica, se scriviamo un risolutore per il problema dell'insieme di vertici, la differenza può esserci. Ad esempio, come nel terzo punto.
Dal punto di vista dell'implementazione, ci sono due approcci. Il primo approccio si chiama Iterative Deepening. Esso consiste nel seguente: possiamo iniziare con una qualsiasi limitazione ragionevole inferiore per la risposta e poi eseguire il nostro algoritmo, utilizzando questa limitazione come limite superiore, senza discendere nella ricorsione al di sotto di questa limitazione. Se troviamo una risposta, essa è garantitamente ottimale; altrimenti, possiamo aumentare questa limitazione di uno e ripartire.
Il secondo approccio consiste nel mantenere una risposta attualmente ottimale e cercare una risposta di dimensione minore, modifica questo parametro quando viene trovata. k per un maggiore taglio delle diramazioni superflue nella ricerca.
Dopo aver condotto diversi esperimenti notturni, ho deciso di combinare questi due approcci: inizialmente eseguo il mio algoritmo con una certa limitazione sulla profondità di ricerca (scegliendola in modo che richieda un tempo insignificante rispetto alla soluzione principale) e utilizzo la migliore soluzione trovata come limite superiore per la risposta. k.
Vertici di grado 2
Abbiamo già trattato i vertici di grado 0 e 1. Si scopre che lo stesso si può fare anche con i vertici di grado 2, ma questo richiederà operazioni più complesse sul grafo.
Per spiegare questo, dobbiamo in qualche modo designare i vertici. Chiamiamo un vertice di grado 2 un vertice v, e i suoi vicini — vertici x e y. A questo punto avremo due casi.
- Quando x e y — vicini. In tal caso, possiamo prendere come risposta x e y, e v rimuovere. Infatti, da questo triangolo è necessario prendere almeno due vertici nella risposta, e sicuramente non perderemo se prendiamo x e y: probabilmente hanno altri vicini, ma v loro non ce li hanno.
- Quando x e y — non vicini. In questo caso, 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, o entrambi i vertici x e y. Infatti, nel primo caso dovremo includere nella risposta tutti i vicini. x e y, e nel secondo non è necessario. Questo corrisponde esattamente ai casi in cui non prendiamo il vertice unito nella risposta e quando lo prendiamo. Resta solo da notare che in entrambi i casi la risposta di tale operazione diminuisce di uno.
Vale la pena notare che un approccio del genere è 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 subottimale (ad esempio, se dopo ogni unione si copiano molti bordi). Mi sono concentrato nella ricerca di percorsi interi tra vertici di grado 2 e nella disamina di molte situazioni particolari, come cicli di tali vertici o di tutti tali vertici tranne uno.
Inoltre, è necessario che questa operazione sia reversibile, in modo che durante il ritorno dalla ricorsione possiamo ripristinare il grafo nella sua forma originale. Per garantire questo, non ho cancellato le liste dei bordi dei vertici fusi, quindi sapevo semplicemente quali bordi dovevo dirigere. Questa implementazione dei grafi richiede anche precisione, ma garantisce un tempo lineare onesto. E per grafi con decine di migliaia di bordi, è ben gestito nella cache del processore, il che offre grandi vantaggi in termini di velocità.
Nucleo lineare
Infine, la parte più interessante del nucleo.
Per iniziare, ricordiamo che nei grafi bipartiti è possibile cercare la copertura minima dei vertici in 
. A tal fine, è necessario utilizzare l'algoritmo per trovare lì il massimo accoppiamento, e poi applicare il teorema .
L'idea del nucleo lineare è: prima raddoppiamo il grafo, cioè invece di ogni vertice v creiamo due vertici 
e 
, e invece di ogni bordo u — v creiamo due bordi 
e 
. Il grafo ottenuto sarà bipartito. Troveremo in esso un minimo insieme di vertici. Alcuni vertici del grafo iniziale appariranno due volte, altri solo una volta, e alcuni non appariranno affatto. Il teorema di Nemhauser-Trotter afferma che in questo caso si possono rimuovere i vertici che non sono stati selezionati e includere quelli che sono stati selezionati due volte. Inoltre, dice che tra i vertici rimanenti (quelli che sono stati selezionati una volta) è necessario includere almeno la metà.
Appena abbiamo imparato a lasciare nel grafo non più di 2k vertici. Infatti, se nel risultato ci sono almeno la metà di tutti i vertici, allora il numero totale di vertici non è maggiore di 2k.
Qui sono riuscito a fare un piccolo passo avanti. È chiaro che il nucleo così costruito dipende da quale minimo insieme di vertici nel grafo bipartito abbiamo scelto. Si desidera selezionare quello in modo che il numero di vertici rimanenti sia minimo. In passato, questo si sapeva fare solo in un tempo 
. Io ho ideato un'implementazione di questo algoritmo in un tempo 
, in questo modo, questo nucleo può essere cercato su grafi con centinaia di migliaia di vertici in ogni fase del branching.
Risultato
La pratica dimostra che la mia soluzione funziona bene nei test su diverse centinaia di vertici e diverse migliaia di archi. In questi test, ci si può aspettare che la soluzione venga trovata in circa mezz'ora. La probabilità di trovare una risposta in un tempo accettabile aumenta quando nel grafo ci sono abbastanza vertici di alto grado, ad esempio di grado 10 o superiore.
Per partecipare alla competizione, era necessario inviare le soluzioni su . A giudicare dalla tabella presentata lì, la mia soluzione si posiziona al terzo posto nei test pubblici su venti, con un ampio distacco rispetto al secondo. Se devo essere completamente onesto, non è del tutto chiaro come saranno valutate le soluzioni nella competizione vera e propria: ad esempio, la mia soluzione supera meno test rispetto a quella al quarto posto, ma su quelli che riesce a superare, è più veloce. I risultati sui test riservati saranno resi noti il primo luglio.
I risultati dei test chiusi saranno noti il primo luglio.
Fonte: habr.com
