{"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\/novosti-interneta\/kak-reshat-np-trudnye-zadachi-s-pomoshhyu-parametrizovannyh-algoritmov","title":{"rendered":"Come risolvere problemi NP-difficili con algoritmi parametrici","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

La ricerca scientifica \u00e8 probabilmente la parte pi\u00f9 interessante del nostro percorso di studi. L'idea \u00e8 di mettersi alla prova in un settore scelto gi\u00e0 durante l'universit\u00e0. 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).<\/p>\n

In questo post parler\u00f2 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\u00f9 noti: il problema del vertice coperto<\/b>.<\/p>\n

Attualmente, si sta sviluppando rapidamente un approccio interessante per i problemi NP-difficili: gli algoritmi parametrizzati. Cercher\u00f2 di introdurvi nell'argomento, illustrando alcuni semplici algoritmi parametrizzati e descrivendo un potente metodo che mi \u00e8 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.<\/p>\n

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

Su di me<\/h3>\n

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\u00aa scuola di Mosca e partecipavo con successo alle olimpiadi di informatica.<\/p>\n

\u041a\u043e\u043d\u0435\u0447\u043d\u043e\u0435 \u043a\u043e\u043b\u0438\u0447\u0435\u0441\u0442\u0432\u043e \u0441\u043f\u0435\u0446\u0438\u0430\u043b\u0438\u0441\u0442\u043e\u0432 \u043f\u043e \u043f\u0430\u0440\u0430\u043c\u0435\u0442\u0440\u0438\u0437\u043e\u0432\u0430\u043d\u043d\u044b\u043c \u0430\u043b\u0433\u043e\u0440\u0438\u0442\u043c\u0430\u043c \u0437\u0430\u0445\u043e\u0434\u044f\u0442 \u0432 \u0431\u0430\u0440…<\/h3>\n

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

Immaginate di essere il 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 comporta non pochi problemi: dovete cacciare fuori i clienti molesti per evitare risse. Alla fine, vi stancate di tutto ci\u00f2 e decidete di adottare misure preventive.<\/p>\n

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

Purtroppo, il compito che vi si presenta \u00e8 un classico problema NP-difficile. Potreste conoscerlo come Vertex Cover<\/a><\/noindex>, 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\u00f2 essere risolto in un tempo \"Come, cio\u00e8 che non c'\u00e8 nulla di significativamente migliore del completo controllo. Ad esempio, supponiamo che al bar vogliano venire n = 1000<\/i> persone. Allora il numero totale di combinazioni sar\u00e0 \"Come opzioni, che \u00e8 circa \"Come \u2014 un'enormit\u00e0. Fortunatamente, la vostra direzione vi ha imposto un vincolo di k = 10<\/i>, quindi il numero di combinazioni da considerare \u00e8 molto minore: il numero di sottoinsiemi di dieci elementi \u00e8 \"Come. Questo \u00e8 gi\u00e0 meglio, ma non si potr\u00e0 comunque arrivare a un conteggio in un giorno, anche su un cluster potente.
\n\"Come
\nPer escludere la possibilit\u00e0 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.<\/p>\n

Significa questo che \u00e8 ora di arrendersi e far entrare tutti? Consideriamo altre opzioni. Ad esempio, si pu\u00f2 non far entrare solo chi probabilmente combatter\u00e0 con un numero molto elevato di persone. Se qualcuno pu\u00f2 combattere almeno con k + 1<\/i> un'altra persona, allora sicuramente non deve essere fatto entrare, altrimenti sar\u00e0 necessario non far entrare tutti k + 1<\/i> i cittadini con cui potrebbe combattere, il che gi\u00e0 deluder\u00e0 certamente la direzione.<\/p>\n

Supponiamo che tu abbia escluso tutti quelli che potevi secondo questo principio. Allora tutti gli altri possono combattere con non pi\u00f9 di k<\/i> persone. Escludendo da essi k<\/i> la gente, puoi prevenire al massimo \"Come conflitti. Quindi, se pi\u00f9 di \"Come persone partecipano a almeno un conflitto, allora sicuramente non riuscirai a prevenirli tutti. Poich\u00e9, \u00e8 ovvio, che le persone non conflittuali le farai entrare, \u00e8 necessario esaminare tutti i sottoinsiemi di dimensione dieci da duecento persone. Ce ne sono circa \"Come, e tale numero di operazioni \u00e8 gi\u00e0 gestibile in un cluster.<\/p>\n

Se \u00e8 possibile accettare persone completamente non conflittuali, cosa dire di quelle che partecipano a un solo conflitto? In realt\u00e0, anche loro possono essere accolti, chiudendo le porte davanti ai loro avversari. \u00c8 vero, se Alice \u00e8 in conflitto solo con Bob, allora, se facciamo entrare Alice, non perderemo: Bob potrebbe avere altri conflitti, mentre Alice sicuramente non ne ha. Inoltre, \u00e8 del tutto inutile non far entrare entrambi. Dopo tali operazioni, rimangono al massimo \"Come ospiti con un destino irrisolto: in totale abbiamo \"Come conflitti, in ciascuno ci sono due partecipanti e ognuno partecipa ad almeno due. Quindi, rimane da considerare solo \"Come opzioni, il che potrebbe richiedere solo mezza giornata su un portatile.<\/p>\n

In effetti, attraverso ragionamenti semplici si possono ottenere condizioni ancora pi\u00f9 vantaggiose. \u00c8 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\u00e9 in ogni passaggio escludiamo qualcuno, l'albero di ricorsione di questo algoritmo \u00e8 un albero binario di profondit\u00e0 k<\/i>, quindi l'algoritmo funziona in totale per \"Come, dove n<\/i> \u2014 numero di vertici, e m<\/i> \u2014 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.<\/p>\n

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

Tutti i ragionamenti fino a questo algoritmo portano all'esempio di kernalizzazione<\/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 risultante viene spesso chiamato nucleo. Cos\u00ec, 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.<\/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 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 (Treewidth<\/a><\/noindex>), alla ricerca dell'albero di Steiner (Steiner Tree<\/a><\/noindex>) e alla ricerca di un insieme di vertici che taglia cicli (Feedback Vertex Set<\/a><\/noindex>). Quest'anno una delle sfide in cui si poteva mettere alla prova \u00e8 stata quella del vertex cover descritta sopra.<\/p>\n

La competizione sta guadagnando popolarit\u00e0 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\u00e9 una settimana, ma diversi mesi. Le squadre hanno la possibilit\u00e0 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\u00f9 efficaci e la premiazione dei vincitori avverr\u00e0 insieme alla 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 possono essere trovate su sito<\/a><\/noindex>, mentre i risultati degli anni passati sono disponibili qui<\/a><\/noindex>.<\/p>\n

Schema della soluzione<\/h3>\n

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 \u00e8 di ridurre il problema a uno equivalente di dimensione minore. Le regole di semplificazione rappresentano la parte pi\u00f9 onerosa dell'algoritmo, e l'applicazione proprio di questa parte porta a un tempo di esecuzione complessivo \"Come invece di un semplice tempo polinomiale. Nel nostro caso, le regole di divisione si basano sul fatto che per ogni vertice \u00e8 necessario rispondere con esso o con uno dei suoi vicini.<\/p>\n

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

A questo schema sar\u00e0 aggiunto esattamente un complemento nel paragrafo successivo.<\/p>\n

Idee per le regole di divisione (branching)<\/h3>\n

Discutiamo su come scegliere il vertice su cui avverr\u00e0 la suddivisione.
\nL'idea principale \u00e8 molto golosa in senso algoritmico: prendiamo il vertice di massima grado e suddividiamoci proprio su di esso. Perch\u00e9 sembra che sia meglio? Perch\u00e9, 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.<\/p>\n

Questo approccio, insieme alle tecniche di kernelizzazione gi\u00e0 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\u00e8 quelli in cui il grado di ogni vertice \u00e8 uguale a tre).
\nC'\u00e8 un'altra idea basata su un concetto piuttosto semplice: se il grafo \u00e8 disconnesso, il problema sulle sue 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 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 \u00e8 necessario trasformare un grafo connesso in uno disconnesso.<\/p>\n

Come farlo? Se nel grafo c'\u00e8 un punto di giunzione, bisogna effettuare il branching proprio su di esso. Un punto di giunzione \u00e8 un vertice tale che, se rimosso, il grafo perde la connettivit\u00e0. Trovare tutti i punti di giunzione in un grafo pu\u00f2 essere fatto utilizzando l'algoritmo classico in tempo lineare. Questo approccio accelera notevolmente il branching.
\n\"Come
\nAlla rimozione di uno qualsiasi dei vertici evidenziati, il grafo si suddivider\u00e0 in componenti di connettivit\u00e0.<\/p>\n

Lo faremo, ma vogliamo di pi\u00f9. Ad esempio, cercare nel grafo piccoli tagli sui vertici e effettuare la scomposizione attraverso di essi. Il modo pi\u00f9 efficace che conosco per trovare il taglio globale minimo sui vertici \u00e8 utilizzare l'albero di Gomory-Hu, che si costruisce in tempo cubico. Nel PACE Challenge, la dimensione tipica del grafo \u00e8 di diverse migliaia di vertici. In questa situazione, in ogni vertice dell'albero di ricorsione \u00e8 necessario eseguire miliardi di operazioni. Quindi, risolvere il problema nel tempo assegnato \u00e8 semplicemente impossibile.<\/p>\n

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

Ho provato diverse volte a cercare separazioni tra coppie di vertici casuali, cercando di ottenere la pi\u00f9 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\u00e0 di discesa. Dopo un algoritmo che tentava di trovare una separazione in questo modo, restavano grafi di dimensioni maggiori. Ci\u00f2 \u00e8 dovuto al fatto che le separazioni risultavano molto sbilanciate: rimuovendo da 5 a 10 vertici, si riusciva a separare solo 15-20.<\/p>\n

\u00c8 importante notare che negli articoli sulle teorie dei pi\u00f9 rapidi algoritmi vengono utilizzate tecniche di selezione dei vertici per la divisione molto pi\u00f9 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.<\/p>\n

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

Abbiamo gi\u00e0 delle idee per la 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 le prime due \u00e8 tutto chiaro, ma con la terza c'\u00e8 un trucco. Se nel problema scherzoso del bar ci era stata data una limitazione superiore su k<\/i>, nel PACE Challenge bisogna solo trovare un insieme di vertici di dimensione minima. Questo \u00e8 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\u00f2 esserci. Ad esempio, come nel terzo punto.<\/p>\n

    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 \u00e8 garantitamente ottimale; altrimenti, possiamo aumentare questa limitazione di uno e ripartire.<\/p>\n

    Il secondo approccio consiste nel mantenere una risposta attualmente ottimale e cercare una risposta di dimensione minore, modifica questo parametro quando viene trovata. k<\/i> per un maggiore taglio delle diramazioni superflue nella ricerca.<\/p>\n

    Dopo aver condotto diversi esperimenti notturni, ho deciso di combinare questi due approcci: inizialmente eseguo il mio algoritmo con una certa limitazione sulla profondit\u00e0 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<\/i>.<\/p>\n

    Vertici di grado 2<\/h3>\n

    Abbiamo gi\u00e0 trattato i vertici di grado 0 e 1. Si scopre che lo stesso si pu\u00f2 fare anche con i vertici di grado 2, ma questo richieder\u00e0 operazioni pi\u00f9 complesse sul grafo.<\/p>\n

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

      \n
    1. Quando x<\/i> e y<\/i> \u2014 vicini. In tal caso, possiamo prendere come risposta x<\/i> e y<\/i>, e v<\/i> rimuovere. Infatti, da questo triangolo \u00e8 necessario prendere almeno due vertici nella risposta, e sicuramente non perderemo se prendiamo x<\/i> e y<\/i>: probabilmente hanno altri vicini, ma v<\/i> loro non ce li hanno.<\/li>\n
    2. Quando x<\/i> e y<\/i> \u2014 non vicini. In questo caso, 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>, o entrambi i vertici x<\/i> e y<\/i>. Infatti, nel primo caso dovremo includere nella risposta tutti i vicini. x<\/i> e y<\/i>, e nel secondo non \u00e8 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.<\/li>\n<\/ol>\n

      \"Come<\/p>\n

      Vale la pena notare che un approccio del genere \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 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.<\/p>\n

      Inoltre, \u00e8 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, \u00e8 ben gestito nella cache del processore, il che offre grandi vantaggi in termini di velocit\u00e0.<\/p>\n

      Nucleo lineare<\/h3>\n

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

      Per iniziare, ricordiamo che nei grafi bipartiti \u00e8 possibile cercare la copertura minima dei vertici in \"Come. A tal fine, \u00e8 necessario utilizzare l'algoritmo Hopcroft-Karp<\/a><\/noindex> per trovare l\u00ec il massimo accoppiamento, e poi applicare il teorema K\u00f6nig-Egervari<\/a><\/noindex>.<\/p>\n

      L'idea del nucleo lineare \u00e8: prima raddoppiamo il grafo, cio\u00e8 invece di ogni vertice v<\/i> creiamo due vertici \"Come e \"Come, e invece di ogni bordo u \u2014 v<\/i> creiamo due bordi \"Come e \"Come. Il grafo ottenuto sar\u00e0 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) \u00e8 necessario includere almeno la met\u00e0.<\/p>\n

      Appena abbiamo imparato a lasciare nel grafo non pi\u00f9 di 2k<\/i> vertici. Infatti, se nel risultato ci sono almeno la met\u00e0 di tutti i vertici, allora il numero totale di vertici non \u00e8 maggiore di 2k<\/i>.<\/p>\n

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

      Risultato<\/h3>\n

      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\u00f2 aspettare che la soluzione venga trovata in circa mezz'ora. La probabilit\u00e0 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.<\/p>\n

      Per partecipare alla competizione, era necessario inviare le soluzioni su optil.io<\/a><\/noindex>. A giudicare dalla tabella presentata l\u00ec, 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 \u00e8 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, \u00e8 pi\u00f9 veloce. tabella<\/a><\/noindex>I risultati sui test riservati saranno resi noti il primo luglio.<\/p>\n

      I risultati dei test chiusi saranno noti il primo luglio.<\/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-novosti-interneta"],"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\udd47 Come risolvere problemi NP-difficili con algoritmi parametrici | ProHoster","description":"La ricerca scientifica \u00e8 senza dubbio una delle parti pi\u00f9 interessanti del nostro percorso di studi. L'idea \u00e8 di provare a lavorare nel proprio campo di scelta gi\u00e0 durante l'universit\u00e0. Ad esempio, gli studenti delle materie di Software Engineering e Machine Learning spesso svolgono ricerche in aziende (principalmente JetBrains o Yandex, ma non solo). In questo post, condivider\u00f2 il mio progetto nel campo della Computer Science.","canonical_url":"https:\/\/prohoster.info\/it\/blog\/novosti-interneta\/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. \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.","og:url":"https:\/\/prohoster.info\/it\/blog\/novosti-interneta\/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"},"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}]}}