{"id":35406,"date":"2019-10-31T22:04:08","date_gmt":"2019-10-31T19:04:08","guid":{"rendered":"https:\/\/prohoster.info\/blog\/kak-reshat-np-trudnye-zadachi-s-pomoshhyu-parametrizovannyh-algoritmov\/"},"modified":"2021-01-02T13:01:41","modified_gmt":"2021-01-02T11:01:41","slug":"kak-reshat-np-trudnye-zadachi-s-pomoshhyu-parametrizovannyh-algoritmov","status":"publish","type":"post","link":"https:\/\/prohoster.info\/it\/blog\/news\/kak-reshat-np-trudnye-zadachi-s-pomoshhyu-parametrizovannyh-algoritmov","title":{"rendered":"Come risolvere problemi NP-difficili con algoritmi parametrizzati","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Il lavoro di ricerca scientifica \u00e8, senza dubbio, la parte pi\u00f9 interessante del nostro percorso formativo. L'idea \u00e8 di provare gi\u00e0 all'universit\u00e0 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).<\/p>\n

In questo post parler\u00f2 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\u00f9 noti: il problema della copertura dei vertici<\/b>.<\/p>\n

Attualmente si sta sviluppando molto rapidamente un interessante approccio ai problemi NP-difficili: gli algoritmi parametrizzati. Cercher\u00f2 di introdurvi a questa tematica, illustrando alcuni semplici algoritmi parametrizzati e descrivendo un potente metodo che mi \u00e8 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\u00b0 luglio.<\/p>\n

\"Come
\n<\/a><\/noindex><\/p>\n

Chi sono<\/h3>\n

Mi chiamo Vasili Alferov, e attualmente sto concludendo il terzo anno all'HSE \u2014 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.<\/p>\n

Un numero finito di specialisti di algoritmi parametrizzati entra in un bar…<\/h3>\n

L'esempio \u00e8 tratto dal libro \u00abParameterized algorithms\u00bb<\/a><\/noindex><\/i><\/p>\n

Immaginate di essere un guardiano di un bar in una piccola citt\u00e0. Ogni venerd\u00ec, met\u00e0 della citt\u00e0 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.<\/p>\n

Poich\u00e9 la citt\u00e0 \u00e8 piccola, sapete esattamente quali coppie di clienti hanno una grande probabilit\u00e0 di litigare se si trovano nello stesso bar. Avete un elenco di n<\/i> 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\u00f9 di k<\/i> persone.<\/p>\n

Sfortunatamente, il compito che vi trovate ad affrontare \u00e8 un classico problema NP-difficile. Potreste conoscere questo problema come Vertex Cover<\/a><\/noindex>, 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\u00f2 essere risolto in un tempo \"Come, cio\u00e8 che non si pu\u00f2 pensare a nulla di significativamente migliore della ricerca esaustiva. Ad esempio, supponiamo che nel tuo bar stia per arrivare n = 1000<\/i> persone. Quindi, la ricerca esaustiva comporterebbe \"Come opzioni, che sono circa \"Come \u2014 esageratamente molte. Per fortuna, la tua direzione ti ha imposto un limite k = 10<\/i>, cos\u00ec il numero di combinazioni che devi esaminare \u00e8 molto inferiore: il numero di sottoinsiemi di dieci elementi \u00e8 \"Come. \u00c8 gi\u00e0 meglio, ma comunque non sar\u00e0 possibile contarli in un giorno, nemmeno su un potente cluster.
\n\"Come
\nPer escludere la possibilit\u00e0 di risse con una tale configurazione di relazioni tese tra i clienti del bar, \u00e8 necessario non far entrare Bob, Daniel e Fyodor. Non esiste una soluzione in cui solo due rimangano fuori.<\/p>\n

Significa che \u00e8 ora di arrendersi e far entrare tutti? Consideriamo altre opzioni. Ad esempio, si pu\u00f2 non far entrare solo coloro che potrebbero probabilmente litigare con un numero molto elevato di persone. Se qualcuno pu\u00f2 litigare con almeno k + 1<\/i> altre persone, allora non pu\u00f2 essere sicuramente fatto entrare \u2014 altrimenti dovr\u00e0 essere escluso da tutti k + 1<\/i> i cittadini con cui potrebbe litigare, il che sicuramente deluder\u00e0 la direzione.<\/p>\n

Supponiamo che tu abbia escluso tutti coloro che potevi seguendo questo principio. Allora tutti gli altri possono litigare con non pi\u00f9 di k<\/i> persone. Escludendo da loro k<\/i> persone, puoi prevenire al massimo \"Come conflitti. Quindi, se pi\u00f9 di \"Come 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 \"Come, e un numero di operazioni del genere \u00e8 gi\u00e0 possibile da esaminare su un cluster.<\/p>\n

Se \u00e8 possibile accogliere persone del tutto non conflittuali, che dire di quelli che partecipano solo a un conflitto? In realt\u00e0, anche loro possono essere accolti, chiudendo la porta di fronte al loro avversario. Infatti, se Alice \u00e8 in conflitto solo con Bob, accogliendo Alice tra i due, non perdiamo: Bob potrebbe avere altri conflitti, mentre Alice certamente non ne ha. Inoltre, \u00e8 del tutto senza senso non far entrare entrambe le parti. Dopo tali operazioni, non rimane pi\u00f9 di \"Come ospiti con una sorte irrisolta: in totale abbiamo \"Come conflitti, ciascuno con due partecipanti e ognuno partecipa ad almeno due. Dunque, rimane da soppesare solamente \"Come opzioni, che potrebbe essere considerato come mezza giornata su un portatile.<\/p>\n

In realt\u00e0, con ragionamenti semplici si possono ottenere condizioni ancora pi\u00f9 favorevoli. Notiamo che dobbiamo necessariamente risolvere tutte le controversie, cio\u00e8 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\u00e9 ad ogni passo scartiamo qualcuno, l'albero della ricorsione di tale algoritmo \u00e8 un albero binario di profondit\u00e0 k<\/i>, quindi complessivamente l'algoritmo funziona in \"Come, dove n<\/i> \u2014 numero di nodi, mentre m<\/i> \u2014 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.<\/p>\n

L'esempio sopra riportato \u00e8 un esempio di algoritmo parametrizzato.<\/b>Gli algoritmi parametrizzati sono algoritmi che funzionano in tempo f(k) poly(n)<\/i>, dove p<\/i> \u2014 polinomiale, f<\/i> \u2014 una funzione calcolabile arbitraria, e k<\/i> \u2014 un qualche parametro che, molto probabilmente, sar\u00e0 molto pi\u00f9 piccolo della dimensione del problema.<\/p>\n

Tutte le considerazioni precedenti a questo algoritmo portano all'esempio di kernelizzazione.<\/b> \u2014 una delle tecniche comuni per la creazione di algoritmi parametrizzati. La kernelizzazione \u00e8 la riduzione della dimensione del problema a un valore limitato da una funzione del parametro. Il problema ottenuto \u00e8 spesso chiamato nucleo. Cos\u00ec, 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.<\/p>\n

Pace Challenge<\/h3>\n

Competizione PACE Challenge<\/a><\/noindex> (The Parameterized Algorithms and Computational Experiments Challenge) \u00e8 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 (Treewidth<\/a><\/noindex>), alla ricerca dell'albero di Steiner (Steiner Tree<\/a><\/noindex>) e alla ricerca di un insieme di vertici che separa i cicli (Feedback Vertex Set<\/a><\/noindex>). Quest'anno, una delle sfide in cui \u00e8 stato possibile mettersi alla prova era il problema di copertura dei vertici sopra descritto.<\/p>\n

La competizione cresce in popolarit\u00e0 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\u00e0 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\u00f9 efficaci e la premiazione dei vincitori si svolgeranno in concomitanza con la conferenza IPEC<\/a><\/noindex> (International Symposium on Parameterized and Exact Computation) nell'ambito del pi\u00f9 grande incontro annuale di algoritmi in Europa ALGO<\/a><\/noindex>. Maggiori informazioni sulla competizione stessa sono disponibili su sito<\/a><\/noindex>, mentre i risultati degli anni passati si trovano qui<\/a><\/noindex>.<\/p>\n

Schema di soluzione<\/h3>\n

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 \u00e8 ridurre il problema a un problema equivalente di dimensioni minori. Le regole di semplificazione sono la parte pi\u00f9 costosa dell'algoritmo e l'applicazione di questa parte porta a un tempo di esecuzione complessivo \"Come 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.<\/p>\n

Lo schema generale \u00e8 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.<\/p>\n

A questo schema verr\u00e0 aggiunta esattamente un'aggiunta nel paragrafo successivo.<\/p>\n

Idee per le regole di biforcazione<\/h3>\n

Discutiamo su come scegliere il vertice su cui avverr\u00e0 la biforcazione.
\nL'idea principale \u00e8 molto affamata dal punto di vista algoritmico: prendiamo il vertice di massimo grado e biforchiamo esattamente su di esso. Perch\u00e9 sembra migliore? Perch\u00e9 nel secondo ramo della chiamata ricorsiva elimineremo in questo modo molti vertici. Ci si pu\u00f2 aspettare che rimanga un grafo ridotto e su di esso lavoreremo rapidamente.<\/p>\n

Questo approccio, insieme alle semplici tecniche di kernelizzazione gi\u00e0 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\u00e8 grafi in cui il grado di ogni vertice \u00e8 tre).
\nC'\u00e8 un'altra idea, basata su una considerazione abbastanza semplice: se il grafo non \u00e8 connesso, il problema sui suoi componenti di connettivit\u00e0 pu\u00f2 essere risolto in modo indipendente, unendo le risposte alla fine. Questa, tra l'altro, \u00e8 la piccola modifica promessa nello schema, che accelerer\u00e0 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 \u00e8 necessario trasformare un grafo connesso in un grafo non connesso.<\/p>\n

Come fare? Se nel grafo c'\u00e8 un punto di giunzione, bisogna ramificare proprio in quel punto. Un punto di giunzione \u00e8 un vertice tale che, se rimosso, il grafo perde connettivit\u00e0. Trovare tutti i punti di giunzione in un grafo pu\u00f2 essere fatto con un algoritmo classico in tempo lineare. Questo approccio accelera notevolmente la ramificazione.
\n\"Come
\nRimuovendo uno qualsiasi dei vertici evidenziati, il grafo si frantumer\u00e0 in componenti connesse.<\/p>\n

Lo faremo, ma ci piacerebbe di pi\u00f9. Ad esempio, cercare nel grafo piccoli tagli di vertici e effettuare la ramificazione sui vertici estratti. Il modo pi\u00f9 efficiente che conosco per trovare il taglio globale minimo dei vertici \u00e8 utilizzare l'albero di Gomory-Hu, che si costruisce in tempo cubico. Nella PACE Challenge, la dimensione tipica del grafo \u00e8 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 \u00e8 praticamente impossibile.<\/p>\n

Proviamo a ottimizzare la soluzione. Un taglio minimo tra una coppia di vertici pu\u00f2 essere trovato utilizzando qualsiasi algoritmo che costruisce un flusso massimo. Possiamo applicare a tale rete l'algoritmo di Dinic<\/a><\/noindex>, in pratica funziona molto velocemente. Ho il sospetto che teoricamente si possa dimostrare una stima sul tempo di esecuzione \"Come, che \u00e8 gi\u00e0 abbastanza accettabile.<\/p>\n

Ho provato diverse volte a cercare tagli tra coppie di vertici casuali e prendere il pi\u00f9 bilanciato. Sfortunatamente, nei test aperti della PACE Challenge ci\u00f2 ha portato a risultati deludenti. Ho confrontato con un algoritmo che si ramificava sui vertici di massimo grado, eseguendoli con un limite sulla profondit\u00e0 di discesa. Dopo l'algoritmo che cercava di trovare un taglio in questo modo, rimanevano grafi di dimensioni maggiori. Questo \u00e8 dovuto al fatto che i tagli risultavano molto sbilanciati: rimuovendo 5-10 vertici, si riusciva a staccarne solo 15-20.<\/p>\n

Va notato che negli articoli sui algoritmi teoricamente pi\u00f9 veloci si utilizzano tecniche di selezione dei vertici per la ramificazione molto pi\u00f9 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.<\/p>\n

Come applicare le regole di semplificazione<\/h3>\n

Abbiamo gi\u00e0 idee di kernelizzazione. Ricordo:<\/p>\n

    \n
  1. Se c'\u00e8 un vertice isolato, rimuoverlo.<\/li>\n
  2. Se c'\u00e8 un vertice di grado 1, rimuoverlo e prendere il suo vicino come risposta.<\/li>\n
  3. Se c'\u00e8 un vertice di grado almeno k + 1<\/i>, prenderlo come risposta.<\/li>\n<\/ol>\n

    Con i primi due \u00e8 tutto chiaro, ma con il terzo c'\u00e8 un trucco. Se nel problema scherzoso del bar ci era stato dato un vincolo superiore su k<\/i>, nel PACE Challenge bisogna semplicemente trovare una copertura del vertice di dimensione minima. Questa \u00e8 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.<\/p>\n

    Dal punto di vista dell'implementazione, ci sono due modi per procedere. Il primo approccio \u00e8 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, \u00e8 garantita come ottimale, altrimenti possiamo aumentare questo vincolo di uno e ripartire.<\/p>\n

    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<\/i> per una maggiore potatura di rami inutili nella ricerca.<\/p>\n

    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\u00e0 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 \u2014 cio\u00e8 su quel k<\/i>.<\/p>\n

    Vertici di grado 2<\/h3>\n

    Con i vertici di grado 0 e 1 ci siamo chiariti. Si scopre che si pu\u00f2 fare cos\u00ec anche con i vertici di grado 2, ma per questo, dal grafo, saranno necessarie operazioni pi\u00f9 complesse.<\/p>\n

    Per spiegare questo, \u00e8 necessario in qualche modo denotare i vertici. Chiamiamo un vertice di grado 2 un vertice v<\/i>, e i suoi vicini \u2014 vertici x<\/i> e y<\/i>. Successivamente avremo due casi.<\/p>\n

      \n
    1. Quando x<\/i> e y<\/i> \u2014 vicini. Allora si pu\u00f2 prendere come risposta x<\/i> e y<\/i>, ma v<\/i> rimuovere. Infatti, da questo triangolo, \u00e8 necessario prendere almeno due vertici come risposta e non perderemo sicuramente prendendo x<\/i> e y<\/i>: probabilmente hanno ancora vicini, mentre v<\/i> loro non hanno.<\/li>\n
    2. Quando x<\/i> e y<\/i> \u2014 non sono i vicini. Allora si afferma che tutti e tre i vertici possono essere uniti in uno. L'idea \u00e8 che in tal caso ci sia una risposta ottimale, in cui prenderemo o v<\/i>, oppure entrambi i vertici x<\/i> e y<\/i>. Infatti, nel primo caso dovremo includere nella risposta tutti i vicini x<\/i> e y<\/i>, mentre nel secondo non \u00e8 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.<\/li>\n<\/ol>\n

      \"Come<\/p>\n

      \u00c8 importante notare che tale approccio \u00e8 piuttosto difficile da implementare correttamente in tempo lineare. L'unione dei vertici \u00e8 un'operazione complessa, \u00e8 necessario copiare le liste dei vicini. Se non si fa con attenzione, si pu\u00f2 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.<\/p>\n

      Inoltre, \u00e8 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\u00f2, 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\u00f2 pone un'ottima compatibilit\u00e0 con la cache della CPU, il che conferisce grandi vantaggi in termini di velocit\u00e0.<\/p>\n

      Nucleo lineare<\/h3>\n

      Infine, la parte pi\u00f9 interessante del nucleo.<\/p>\n

      Iniziamo ricordando che nei grafi bipartiti \u00e8 possibile cercare il minimo copertura dei vertici in \"Come. A tal fine \u00e8 necessario utilizzare l'algoritmo Hopcroft-Karp<\/a><\/noindex> per trovare il massimo accoppiamento, e successivamente utilizzare il teorema di K\u00f6nig-Egervari.<\/a><\/noindex>.<\/p>\n

      L'idea del nucleo lineare \u00e8 la seguente: prima dobbiamo bipartire il grafo, quindi al posto di ogni vertice v<\/i> creiamo due vertici \"Come e \"Come, e invece di ogni arco u \u2014 v<\/i> creiamo due archi \"Come e \"ComeIl grafo risultante sar\u00e0 bipartito. Troveremo in esso una copertura minima dei vertici. Alcuni vertici del grafo originale appariranno l\u00ec 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\u00e0.<\/p>\n

      Appena abbiamo imparato a lasciare nel grafo non pi\u00f9 di 2k<\/i> vertici. \u00c8 vero, se nella risposta rimanente c'\u00e8 almeno la met\u00e0 di tutti i vertici, allora il numero totale di vertici non sar\u00e0 maggiore di 2k<\/i>.<\/p>\n

      Qui sono riuscito a fare un piccolo passo avanti. \u00c8 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 \"Come. Ho per\u00f2 ideato un'implementazione di questo algoritmo in un tempo di \"Come, in questo modo, questo nucleo pu\u00f2 essere cercato in grafi di centinaia di migliaia di vertici ad ogni fase del branching.<\/p>\n

      Risultato<\/h3>\n

      La pratica dimostra che la mia soluzione funziona bene su test con qualche centinaio di vertici e diverse migliaia di archi. Su tali test \u00e8 possibile aspettarsi che venga trovata una soluzione in mezz'ora. La probabilit\u00e0 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.<\/p>\n

      Per partecipare alla competizione, le soluzioni dovevano essere inviate a optil.io<\/a><\/noindex>. A giudicare dalla tabella presentata l\u00ec , la mia soluzione occupa il terzo posto nei test aperti su venti, con un ampio distacco dal secondo. Se vogliamo essere completamente onesti, non \u00e8 del tutto chiaro come verranno valutate le soluzioni nella competizione vera e propria: ad esempio, la mia soluzione passa meno test rispetto a quella al quarto posto, ma su quelli che passa, funziona pi\u00f9 rapidamente.<\/a><\/noindex>I risultati dei test chiusi saranno resi noti il primo di luglio.<\/p>\n

      Il lavoro di ricerca scientifica \u00e8, probabilmente, la parte pi\u00f9 interessante della nostra formazione. L'idea \u00e8 di provare, ancora all'universit\u00e0, a cimentarsi nella direzione scelta.<\/p>\n

      Fonte: habr.com<\/a><\/p>","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"excerpt":{"rendered":"

      \u041d\u0430\u0443\u0447\u043d\u043e-\u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u0441\u043a\u0430\u044f \u0440\u0430\u0431\u043e\u0442\u0430, \u043f\u043e\u0436\u0430\u043b\u0443\u0439, \u0441\u0430\u043c\u0430\u044f \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u0430\u044f \u0447\u0430\u0441\u0442\u044c \u043d\u0430\u0448\u0435\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f. \u0418\u0434\u0435\u044f \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e\u0431\u044b \u0435\u0449\u0451 \u0432 \u0443\u043d\u0438\u0432\u0435\u0440\u0441\u0438\u0442\u0435\u0442\u0435 \u043f\u043e\u043f\u0440\u043e\u0431\u043e\u0432\u0430\u0442\u044c \u0441\u0435\u0431\u044f \u0432 \u0432\u044b\u0431\u0440\u0430\u043d\u043d\u043e\u043c \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0438. \u041d\u0430\u043f\u0440\u0438\u043c\u0435\u0440, \u0441\u0442\u0443\u0434\u0435\u043d\u0442\u044b \u0441 \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0439 Software Engineering \u0438 Machine Learning \u0447\u0430\u0441\u0442\u043e \u0438\u0434\u0443\u0442 \u0434\u0435\u043b\u0430\u0442\u044c \u041d\u0418\u0420\u044b \u0432 \u043a\u043e\u043c\u043f\u0430\u043d\u0438\u0438 (\u0432 \u043e\u0441\u043d\u043e\u0432\u043d\u043e\u043c, JetBrains \u0438\u043b\u0438 \u042f\u043d\u0434\u0435\u043a\u0441, \u043d\u043e \u043d\u0435 \u0442\u043e\u043b\u044c\u043a\u043e). \u0412 \u044d\u0442\u043e\u043c \u043f\u043e\u0441\u0442\u0435 \u044f \u0440\u0430\u0441\u0441\u043a\u0430\u0436\u0443 \u043e \u0441\u0432\u043e\u0451\u043c \u043f\u0440\u043e\u0435\u043a\u0442\u0435 \u043f\u043e \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u044e Computer Science. […]<\/p>\n","protected":false,"gt_translate_keys":[{"key":"rendered","format":"html"}]},"author":1,"featured_media":26562,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[702],"tags":[],"class_list":["post-35406","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-news"],"aioseo_notices":[],"aioseo_head":"\n\t\t\n\t\n\t\n\t\n\t\n\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\t\t\n\n","aioseo_head_json":{"title":"\ud83e\udd47Come risolvere problemi NP-difficili con algoritmi parametrizzati | ProHoster","description":"\ud83e\udd47Come risolvere problemi NP-difficili con algoritmi parametrizzati | ProHoster","canonical_url":"https:\/\/prohoster.info\/it\/blog\/news\/kak-reshat-np-trudnye-zadachi-s-pomoshhyu-parametrizovannyh-algoritmov","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"it_IT","og:site_name":"ProHoster | \u041a\u0443\u043f\u0438\u0442\u044c \u043d\u0430\u0434\u0435\u0436\u043d\u044b\u0439 \u0445\u043e\u0441\u0442\u0438\u043d\u0433 \u0434\u043b\u044f \u0441\u0430\u0439\u0442\u043e\u0432 \u0441 \u0437\u0430\u0449\u0438\u0442\u043e\u0439 \u043e\u0442 DDoS, VPS VDS \u0441\u0435\u0440\u0432\u0435\u0440\u044b","og:type":"article","og:title":"\ud83e\udd47\u041a\u0430\u043a \u0440\u0435\u0448\u0430\u0442\u044c NP-\u0442\u0440\u0443\u0434\u043d\u044b\u0435 \u0437\u0430\u0434\u0430\u0447\u0438 \u0441 \u043f\u043e\u043c\u043e\u0449\u044c\u044e \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u0438\u0437\u043e\u0432\u0430\u043d\u043d\u044b\u0445 \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u043e\u0432 | ProHoster","og:description":"\u041d\u0430\u0443\u0447\u043d\u043e-\u0438\u0441\u0441\u043b\u0435\u0434\u043e\u0432\u0430\u0442\u0435\u043b\u044c\u0441\u043a\u0430\u044f \u0440\u0430\u0431\u043e\u0442\u0430, \u043f\u043e\u0436\u0430\u043b\u0443\u0439, \u0441\u0430\u043c\u0430\u044f \u0438\u043d\u0442\u0435\u0440\u0435\u0441\u043d\u0430\u044f \u0447\u0430\u0441\u0442\u044c \u043d\u0430\u0448\u0435\u0433\u043e \u043e\u0431\u0443\u0447\u0435\u043d\u0438\u044f. \u0418\u0434\u0435\u044f \u0432 \u0442\u043e\u043c, \u0447\u0442\u043e\u0431\u044b \u0435\u0449\u0451 \u0432 \u0443\u043d\u0438\u0432\u0435\u0440\u0441\u0438\u0442\u0435\u0442\u0435 \u043f\u043e\u043f\u0440\u043e\u0431\u043e\u0432\u0430\u0442\u044c \u0441\u0435\u0431\u044f \u0432 \u0432\u044b\u0431\u0440\u0430\u043d\u043d\u043e\u043c \u043d\u0430\u043f\u0440\u0430\u0432\u043b\u0435\u043d\u0438\u0438.","og:url":"https:\/\/prohoster.info\/it\/blog\/news\/kak-reshat-np-trudnye-zadachi-s-pomoshhyu-parametrizovannyh-algoritmov","og:image":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:secure_url":"https:\/\/prohoster.info\/wp-content\/uploads\/2021\/11\/logo-350.jpg","og:image:width":350,"og:image:height":350,"article:published_time":"2019-10-31T19:04:08+00:00","article:modified_time":"2021-01-02T11:01:41+00:00","article:publisher":"https:\/\/www.facebook.com\/prohoster","article:author":"https:\/\/www.facebook.com\/prohoster"},"aioseo_meta_data":{"post_id":"35406","title":null,"description":"","keywords":"","keyphrases":null,"primary_term":null,"canonical_url":"","og_title":null,"og_description":null,"og_object_type":"default","og_image_type":"default","og_image_url":null,"og_image_width":null,"og_image_height":null,"og_image_custom_url":null,"og_image_custom_fields":null,"og_video":null,"og_custom_url":null,"og_article_section":null,"og_article_tags":null,"twitter_use_og":false,"twitter_card":"default","twitter_image_type":"default","twitter_image_url":null,"twitter_image_custom_url":null,"twitter_image_custom_fields":null,"twitter_title":null,"twitter_description":null,"schema":{"blockGraphs":[],"customGraphs":[],"default":{"data":{"Article":[],"Course":[],"Dataset":[],"FAQPage":[],"Movie":[],"Person":[],"Product":[],"ProductReview":[],"Car":[],"Recipe":[],"Service":[],"SoftwareApplication":[],"WebPage":[]},"graphName":"","isEnabled":true},"graphs":[]},"schema_type":null,"schema_type_options":null,"pillar_content":false,"robots_default":true,"robots_noindex":false,"robots_noarchive":false,"robots_nosnippet":false,"robots_nofollow":false,"robots_noimageindex":false,"robots_noodp":false,"robots_notranslate":false,"robots_max_snippet":null,"robots_max_videopreview":null,"robots_max_imagepreview":"large","priority":null,"frequency":null,"local_seo":null,"seo_analyzer_scan_date":"2026-01-21 23:06:35","breadcrumb_settings":null,"limit_modified_date":false,"reviewed_by":null,"ai":null,"created":"2021-03-01 02:03:22","updated":"2026-01-21 23:06:35","focus_keyword":null,"additional_keywords":null,"truseo_locale":null},"gt_translate_keys":[{"key":"link","format":"url"}],"_links":{"self":[{"href":"https:\/\/prohoster.info\/it\/wp-json\/wp\/v2\/posts\/35406","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/it\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/it\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/it\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/it\/wp-json\/wp\/v2\/comments?post=35406"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/it\/wp-json\/wp\/v2\/posts\/35406\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/it\/wp-json\/wp\/v2\/media\/26562"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/it\/wp-json\/wp\/v2\/media?parent=35406"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/it\/wp-json\/wp\/v2\/categories?post=35406"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/it\/wp-json\/wp\/v2\/tags?post=35406"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}