Il lavoro di ricerca è forse la parte più interessante della nostra formazione. L'idea è quella di metterti alla prova nella direzione prescelta mentre sei ancora all'università. Ad esempio, gli studenti dei settori Ingegneria del Software e Machine Learning vanno spesso a fare ricerca nelle aziende (soprattutto JetBrains o Yandex, ma non solo).
In questo post parlerò del mio progetto in Informatica. Nell'ambito del mio lavoro ho studiato e messo in pratica approcci per risolvere uno dei più famosi problemi NP-hard: problema della copertura del vertice.
Al giorno d'oggi, un approccio interessante ai problemi NP-hard si sta sviluppando molto rapidamente: algoritmi parametrizzati. Cercherò di aggiornarti, di raccontarti alcuni semplici algoritmi parametrizzati e di descrivere un metodo potente che mi ha aiutato molto. Ho presentato i miei risultati al concorso PACE Challenge: secondo i risultati dei test aperti, la mia soluzione occupa il terzo posto e i risultati finali saranno noti il 1 luglio.
Informazioni su di me
Mi chiamo Vasily Alferov, ora sto finendo il mio terzo anno presso la Scuola Superiore di Economia della National Research University - San Pietroburgo. Mi sono interessato agli algoritmi fin dai tempi della scuola, quando ho studiato alla scuola n. 179 di Mosca e ho partecipato con successo alle Olimpiadi dell'informatica.
Un numero finito di specialisti in algoritmi parametrizzati entrano nel bar...
Esempio tratto dal libro
Immagina di essere la guardia di sicurezza di un bar in una piccola città. Ogni venerdì mezza città viene nel tuo bar per rilassarti, il che ti dà un sacco di problemi: devi buttare fuori dal bar i clienti turbolenti per evitare risse. Alla fine ti stufi e decidi di adottare misure preventive.
Dato che la tua città è piccola, sai esattamente quali coppie di avventori potrebbero litigare se finiscono insieme in un bar. Hai un elenco di n persone che verranno al bar stasera. Decidi di tenere alcuni cittadini fuori dal bar senza che nessuno litighi. Allo stesso tempo, i tuoi capi non vogliono perdere profitti e saranno scontenti se non gli permetti più di k persone.
Sfortunatamente, il problema che hai davanti è un classico problema NP-difficile. Potresti conoscerla come , o come problema di copertura dei vertici. Per tali problemi, nel caso generale, non esistono algoritmi che funzionino in tempi accettabili. Per essere precisi, l’ipotesi non dimostrata e piuttosto forte ETH (Exponential Time Hypothesis) afferma che questo problema non può essere risolto in tempo , cioè, non puoi pensare a niente di notevolmente migliore di una ricerca completa. Ad esempio, supponiamo che qualcuno venga al tuo bar n = 1000 Umano. Quindi la ricerca completa sarà opzioni che ci sono approssimativamente - importo pazzesco. Fortunatamente, la tua direzione ti ha dato un limite k = 10, quindi il numero di combinazioni su cui è necessario iterare è molto più piccolo: il numero di sottoinsiemi di dieci elementi è . Questo è meglio, ma non verrà comunque conteggiato in un giorno nemmeno su un ammasso potente.
Per eliminare la possibilità di una rissa in questa configurazione di rapporti tesi tra i visitatori del bar, è necessario tenere fuori Bob, Daniel e Fedor. Non esiste una soluzione in cui solo due saranno lasciati indietro.
Questo significa che è ora di arrendersi e lasciare entrare tutti? Consideriamo altre opzioni. Bene, ad esempio, non puoi far entrare solo coloro che probabilmente combatteranno con un numero molto elevato di persone. Se qualcuno può combattere almeno con K + 1 un'altra persona, allora non puoi assolutamente lasciarla entrare, altrimenti dovrai tenere fuori tutti K + 1 cittadini, con i quali può combattere, il che sconvolgerà sicuramente la leadership.
Possa tu buttare fuori tutti quelli che potresti secondo questo principio. Quindi tutti gli altri potranno combattere con nient'altro che k persone. Buttarli fuori k amico, non puoi impedire altro che conflitti. Ciò significa che se c'è più di Se una persona è coinvolta in almeno un conflitto, non è certo possibile prevenirli tutti. Poiché, ovviamente, lascerai sicuramente entrare persone completamente non in conflitto, devi esaminare tutti i sottoinsiemi di dimensioni dieci su duecento persone. Ci sono circa e questo numero di operazioni può già essere risolto sul cluster.
Se si possono tranquillamente prendere individui che non hanno alcun conflitto, allora che dire di coloro che partecipano ad un solo conflitto? Infatti, possono anche essere fatti entrare chiudendo la porta al loro avversario. Infatti, se Alice è in conflitto solo con Bob, allora se lasciamo uscire Alice da loro due, non perderemo: Bob può avere altri conflitti, ma Alice certamente non li ha. Inoltre, non ha senso non lasciarci entrare entrambi. Dopo tali operazioni non rimane più nulla ospiti dal destino irrisolto: ne abbiamo solo conflitti, ciascuno con due partecipanti e ciascuno coinvolto in almeno due. Quindi non resta che sistemarsi opzioni, che possono facilmente essere considerate mezza giornata su un laptop.
Infatti con un semplice ragionamento si possono ottenere condizioni ancora più vantaggiose. Tieni presente che dobbiamo assolutamente risolvere tutte le controversie, ovvero scegliere almeno una persona da ciascuna coppia in conflitto a cui non lasceremo entrare. Consideriamo il seguente algoritmo: prendiamo qualsiasi conflitto, dal quale rimuoviamo un partecipante e iniziamo ricorsivamente dal resto, quindi rimuoviamo l'altro e iniziamo anch'esso ricorsivamente. Dato che ad ogni passo eliminiamo qualcuno, l'albero di ricorsione di un simile algoritmo è un albero binario della profondità k, quindi in totale l'algoritmo funziona Dove n è il numero di vertici e m - numero di costole. Nel nostro esempio si tratta di circa dieci milioni, che possono essere calcolati in una frazione di secondo non solo su un laptop, ma anche su un telefono cellulare.
L'esempio sopra è un esempio algoritmo parametrizzato. Gli algoritmi parametrizzati sono algoritmi che vengono eseguiti nel tempo f(k) poli(n)Dove p - polinomio, f è una funzione calcolabile arbitraria e k - qualche parametro che, molto probabilmente, sarà molto inferiore alla dimensione del problema.
Tutti i ragionamenti prima di questo algoritmo forniscono un esempio kernelizzazione è una delle tecniche generali per la creazione di algoritmi parametrizzati. La kernelizzazione è la riduzione della dimensione del problema a un valore limitato da una funzione di un parametro. Il problema risultante è spesso chiamato kernel. Pertanto, ragionando semplicemente sui gradi dei vertici, abbiamo ottenuto un nucleo quadratico per il problema Vertex Cover, parametrizzato dalla dimensione della risposta. Ci sono altre impostazioni che puoi scegliere per questa attività (come Vertex Cover Above LP), ma questa è l'impostazione di cui parleremo.
Sfida al ritmo
concorrenza (The Parametrized Algorithms and Computational Experiments Challenge) è nato nel 2015 per stabilire una connessione tra algoritmi parametrizzati e approcci utilizzati nella pratica per risolvere problemi computazionali. Le prime tre gare erano dedicate alla ricerca della larghezza dell'albero di un grafico (), alla ricerca di un albero di Steiner () e cercando un insieme di vertici che taglia i cicli (). Quest'anno uno dei problemi in cui potevi cimentarti era il problema della copertura dei vertici sopra descritto.
La competizione sta guadagnando popolarità ogni anno. Secondo i dati preliminari, quest'anno 24 squadre hanno preso parte alla competizione per risolvere da soli il problema della copertura del vertice. Vale la pena notare che la competizione non dura diverse ore e nemmeno una settimana, ma diversi mesi. I team hanno l'opportunità di studiare la letteratura, elaborare la propria idea originale e provare a implementarla. In sostanza, questo concorso è un progetto di ricerca. In concomitanza con il convegno si terranno le idee per le soluzioni più efficaci e la premiazione dei vincitori (International Symposium on Parametrized and Exact Computation) nell’ambito del più grande incontro algoritmico annuale in Europa . Informazioni più dettagliate sul concorso stesso sono disponibili all'indirizzo , e i risultati degli anni precedenti mentono .
Schema risolutivo
Per risolvere il problema della copertura dei vertici, ho provato a utilizzare algoritmi parametrizzati. Solitamente sono costituiti da due parti: regole di semplificazione (che idealmente portano alla kernelizzazione) e regole di suddivisione. Le regole di semplificazione preelaborano l'input in tempo polinomiale. Lo scopo dell’applicazione di tali regole è ridurre il problema a un problema equivalente più piccolo. Le regole di semplificazione sono la parte più costosa dell'algoritmo e l'applicazione di questa parte porta al tempo di esecuzione totale invece del semplice tempo polinomiale. Nel nostro caso, le regole di suddivisione si basano sul fatto che per ogni vertice è necessario prendere come risposta esso o il suo vicino.
Lo schema generale è questo: applichiamo le regole di semplificazione, poi selezioniamo qualche vertice, e facciamo due chiamate ricorsive: nella prima lo prendiamo in risposta, e nell'altra prendiamo tutti i suoi vicini. Questo è ciò che chiamiamo scissione (ramificazione) lungo questo vertice.
Nel paragrafo successivo verrà apportata esattamente un'aggiunta a questo schema.
Idee per dividere (brunching) le regole
Parliamo di come scegliere un vertice lungo il quale avverrà la scissione.
L'idea principale è molto avida in senso algoritmico: prendiamo un vertice di massimo grado e dividiamo lungo di esso. Perché sembra migliore? Perché nel secondo ramo della chiamata ricorsiva rimuoveremo molti vertici in questo modo. Puoi contare su un piccolo grafico rimanente e possiamo lavorarci rapidamente.
Questo approccio, con le semplici tecniche di kernelizzazione già discusse, si mostra bene e risolve alcuni test di diverse migliaia di vertici. Ma, ad esempio, non funziona bene per i grafi cubici (cioè i grafici il cui grado di ciascun vertice è tre).
C'è un'altra idea basata su un'idea abbastanza semplice: se il grafico è sconnesso, il problema sui suoi componenti collegati può essere risolto indipendentemente, combinando le risposte alla fine. Questa, tra l'altro, è una piccola modifica promessa allo schema, che accelererà notevolmente la soluzione: prima, in questo caso, lavoravamo per il prodotto dei tempi per calcolare le risposte dei componenti, ma ora lavoriamo per la somma. E per accelerare la ramificazione, è necessario trasformare un grafico connesso in uno disconnesso.
Come farlo? Se c'è un punto di articolazione nel grafico, devi lottare per raggiungerlo. Un punto di articolazione è un vertice tale che, una volta rimosso, il grafico perde la sua connettività. Tutti i punti di giunzione in un grafico possono essere trovati utilizzando un algoritmo classico in tempo lineare. Questo approccio accelera notevolmente la ramificazione.
Quando uno qualsiasi dei vertici selezionati viene rimosso, il grafico verrà suddiviso in componenti collegati.
Lo faremo, ma vogliamo di più. Ad esempio, cerca piccoli tagli nei vertici nel grafico e dividili lungo i vertici. Il modo più efficiente che conosco per trovare il taglio minimo del vertice globale è utilizzare un albero di Gomori-Hu, costruito in tempo cubico. Nella sfida PACE, la dimensione tipica del grafico è di diverse migliaia di vertici. In questa situazione, è necessario eseguire miliardi di operazioni su ciascun vertice dell'albero di ricorsione. Si scopre che è semplicemente impossibile risolvere il problema nel tempo assegnato.
Proviamo a ottimizzare la soluzione. Il vertice minimo tagliato tra una coppia di vertici può essere trovato da qualsiasi algoritmo che costruisce un flusso massimo. Puoi lasciarlo entrare in una rete del genere , in pratica funziona molto velocemente. Ho il sospetto che teoricamente sia possibile dimostrare una stima del tempo di funzionamento , il che è già abbastanza accettabile.
Ho provato più volte a cercare i tagli tra coppie di vertici casuali e a prendere quello più equilibrato. Sfortunatamente, ciò ha prodotto scarsi risultati nei test aperti del PACE Challenge. L'ho confrontato con un algoritmo che divideva i vertici di massimo grado, eseguendoli con una limitazione sulla profondità di discesa. Un algoritmo che cercava di trovare un taglio in questo modo lasciava grafici più grandi. Ciò è dovuto al fatto che i tagli si sono rivelati molto sbilanciati: eliminati 5-10 vertici è stato possibile separarne solo 15-20.
Vale la pena notare che gli articoli sugli algoritmi teoricamente più veloci utilizzano tecniche molto più avanzate per selezionare i vertici da dividere. Tali tecniche hanno un'implementazione molto complessa e spesso scarse prestazioni in termini di tempo e memoria. Non sono riuscito a identificare quelli che sono abbastanza accettabili per la pratica.
Come applicare le regole di semplificazione
Abbiamo già idee per la kernelizzazione. Lascia che ti ricordi:
- Se c'è un vertice isolato, cancellalo.
- Se c'è un vertice di grado 1, rimuovilo e prendi in risposta il suo vicino.
- Se c'è un vertice di grado almeno K + 1, riprenditelo.
Con i primi due tutto è chiaro, con il terzo c'è un trucco. Se in un problema comico su un bar ci fosse dato un limite massimo di k, quindi nella PACE Challenge devi solo trovare una copertura del vertice della dimensione minima. Questa è una tipica trasformazione dei problemi di ricerca in problemi di decisione; spesso non c'è differenza tra i due tipi di problemi. In pratica, se stiamo scrivendo un risolutore per il problema della copertura dei vertici, potrebbe esserci una differenza. Ad esempio, come nel terzo punto.
Dal punto di vista realizzativo si possono procedere in due modi. Il primo approccio è chiamato Iterative Deepening. È il seguente: possiamo iniziare con qualche ragionevole vincolo dal basso sulla risposta, e poi eseguire il nostro algoritmo utilizzando questo vincolo come vincolo sulla risposta dall'alto, senza scendere al di sotto di questo vincolo nella ricorsione. Se abbiamo trovato qualche risposta è garantito che sia ottimale, altrimenti possiamo aumentare questo limite di uno e ricominciare da capo.
Un altro approccio consiste nel memorizzare una risposta ottimale corrente e cercare una risposta più piccola, modificando questo parametro una volta trovato k per un maggiore taglio dei rami non necessari nella ricerca.
Dopo aver condotto diversi esperimenti notturni, ho optato per una combinazione di questi due metodi: in primo luogo, eseguo il mio algoritmo con una sorta di limite alla profondità di ricerca (selezionandolo in modo che richieda un tempo trascurabile rispetto alla soluzione principale) e utilizzo il migliore soluzione trovata come limite superiore alla risposta, cioè alla stessa cosa k.
Vertici di grado 2
Abbiamo trattato i vertici di grado 0 e 1. Si scopre che ciò può essere fatto con vertici di grado 2, ma ciò richiederà operazioni più complesse dal grafico.
Per spiegare questo, dobbiamo designare in qualche modo i vertici. Chiamiamo vertice un vertice di grado 2 ve i suoi vicini: vertici x и y. Successivamente avremo due casi.
- Quando x и y - vicinato. Allora puoi rispondere x и yE v eliminare. In effetti, da questo triangolo è necessario prendere in cambio almeno due vertici e, se li prendiamo, sicuramente non perderemo x и y: probabilmente hanno altri vicini, e v non lo sono.
- Quando x и y - non vicini. Quindi si afferma che tutti e tre i vertici possono essere incollati in uno solo. L'idea è che in questo caso esista una risposta ottimale, in cui prendiamo l'una o l'altra v, o entrambi i vertici x и y. Inoltre, nel primo caso dovremo rispondere a tutti i vicini x и y, ma nel secondo non è necessario. Ciò corrisponde esattamente ai casi in cui non prendiamo il vertice incollato in risposta e quando lo facciamo. Resta solo da notare che in entrambi i casi la risposta di tale operazione diminuisce di uno.
Vale la pena notare che questo approccio è piuttosto difficile da implementare con precisione in tempi lineari corretti. Incollare i vertici è un'operazione complessa; è necessario copiare elenchi di vicini. Se questo viene fatto con noncuranza, puoi ritrovarti con un tempo di esecuzione asintoticamente non ottimale (ad esempio, se copi molti bordi dopo ogni incollaggio). Ho deciso di trovare interi percorsi da vertici di grado 2 e di analizzare una serie di casi speciali, come i cicli da tali vertici o da tutti questi vertici tranne uno.
Inoltre, è necessario che questa operazione sia reversibile, in modo che al ritorno dalla ricorsione riportiamo il grafico alla sua forma originale. Per garantire ciò, non ho cancellato gli elenchi dei vertici uniti e quindi sapevo solo quali bordi dovevano andare e dove. Anche questa implementazione dei grafici richiede precisione, ma fornisce un tempo lineare discreto. E per i grafici con diverse decine di migliaia di spigoli, si inserisce nella cache del processore, il che offre grandi vantaggi in termini di velocità.
Nucleo lineare
Infine, la parte più interessante del kernel.
Per cominciare, ricordiamo che nei grafi bipartiti la copertura minima dei vertici può essere trovata utilizzando . Per fare questo è necessario utilizzare l'algoritmo per trovare lì la corrispondenza massima e quindi utilizzare il teorema .
L'idea di un nucleo lineare è questa: prima biforchiamo il grafico, cioè al posto di ciascun vertice v aggiungiamo due picchi и , e invece di ciascun bordo u-v aggiungiamo due costolette и . Il grafico risultante sarà bipartito. Troviamo in esso la copertura minima del vertice. Alcuni vertici del grafico originale arriveranno lì due volte, alcuni solo una volta e altri mai. Il teorema di Nemhauser-Trotter afferma che in questo caso si possono rimuovere i vertici che non hanno colpito nemmeno una volta e riprendere quelli che hanno colpito due volte. Inoltre, dice che dei restanti vertici (quelli che colpiscono una volta) devi prenderne almeno la metà come risposta.
Abbiamo appena imparato a non lasciare più di 2k picchi Infatti, se la risposta rimanente è almeno la metà di tutti i vertici, allora non ci sono più vertici in totale di 2k.
Qui ho potuto fare un piccolo passo avanti. È chiaro che il kernel costruito in questo modo dipende dal tipo di copertura minima dei vertici che abbiamo preso nel grafo bipartito. Vorrei prenderne uno in modo che il numero di vertici rimanenti sia minimo. In precedenza, erano in grado di farlo solo in tempo . Nel tempo ho ideato un'implementazione di questo algoritmo , quindi, questo nucleo può essere cercato nei grafici di centinaia di migliaia di vertici in ogni fase di ramificazione.
risultato
La pratica dimostra che la mia soluzione funziona bene su test di diverse centinaia di vertici e diverse migliaia di spigoli. In tali test è del tutto possibile aspettarsi che la soluzione venga trovata in mezz'ora. La probabilità di trovare una risposta in un tempo accettabile, in linea di principio, aumenta se il grafico ha un numero sufficientemente elevato di vertici di grado elevato, ad esempio grado 10 e superiore.
Per partecipare al concorso era necessario inviare le soluzioni a . A giudicare dalle informazioni presentate lì , la mia soluzione nei test aperti si colloca al terzo posto su venti, con un ampio distacco dal secondo. Ad essere sincero, non è del tutto chiaro come verranno valutate le soluzioni al concorso stesso: ad esempio, la mia soluzione supera meno test rispetto alla soluzione al quarto posto, ma su quelle che superano funziona più velocemente.
I risultati dei test a porte chiuse saranno resi noti il XNUMX° luglio.
Fonte: habr.com