{"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\/pt\/blog\/news\/kak-reshat-np-trudnye-zadachi-s-pomoshhyu-parametrizovannyh-algoritmov","title":{"rendered":"Como resolver problemas NP-dif\u00edceis com algoritmos parametrizados","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

A pesquisa cient\u00edfica \u00e9, sem d\u00favida, a parte mais interessante do nosso aprendizado. A ideia \u00e9 tentar se aventurar na dire\u00e7\u00e3o escolhida ainda na universidade. Por exemplo, estudantes das \u00e1reas de Engenharia de Software e Aprendizado de M\u00e1quina frequentemente buscam realizar trabalhos de pesquisa em empresas (principalmente, JetBrains ou Yandex, mas n\u00e3o apenas).<\/p>\n

Neste post, vou falar sobre meu projeto na \u00e1rea de Ci\u00eancia da Computa\u00e7\u00e3o. No \u00e2mbito do trabalho, eu estudei e implementei na pr\u00e1tica abordagens para resolver um dos problemas NP-dif\u00edceis mais conhecidos: o problema do cobertura de v\u00e9rtices<\/b>.<\/p>\n

Atualmente, um interessante enfoque para problemas NP-dif\u00edceis est\u00e1 se desenvolvendo rapidamente \u2014 algoritmos parametrizados. Vou tentar mant\u00ea-lo a par, explicando alguns algoritmos parametrizados simples e descrevendo um m\u00e9todo poderoso que me ajudou bastante. Apresentei meus resultados na competi\u00e7\u00e3o PACE Challenge: ap\u00f3s os testes abertos, minha solu\u00e7\u00e3o ocupa o terceiro lugar, e os resultados finais ser\u00e3o conhecidos em 1 de julho.<\/p>\n

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

Sobre mim<\/h3>\n

Meu nome \u00e9 Vasiliy Alferov, e estou concluindo o terceiro ano na \u041d\u0418\u0423 \u0412\u0428\u042d \u2014 S\u00e3o Petersburgo. Tenho me interessado por algoritmos desde os tempos de escola, quando estudava na escola 179 de Moscovo e participei com sucesso em olimp\u00edadas de inform\u00e1tica.<\/p>\n

Um n\u00famero finito de especialistas em algoritmos parametrizados entra no bar\u2026<\/h3>\n

O exemplo foi retirado do livro \u00abParameterized algorithms\u00bb<\/a><\/noindex><\/i><\/p>\n

Imagine que voc\u00ea \u00e9 o seguran\u00e7a de um bar em uma pequena cidade. Toda sexta-feira, metade da cidade vai ao seu bar para relaxar, o que traz muitos problemas: \u00e9 preciso expulsar os frequentadores agitados para evitar brigas. No final, voc\u00ea fica cansado disso e decide tomar medidas preventivas.<\/p>\n

Como a cidade \u00e9 pequena, voc\u00ea sabe exatamente quais pares de visitantes t\u00eam uma alta probabilidade de brigar se estiverem no bar juntos. Voc\u00ea tem uma lista de n<\/i> pessoas que v\u00e3o chegar esta noite ao bar. Voc\u00ea decide n\u00e3o deixar entrar certos cidad\u00e3os da cidade de forma que ningu\u00e9m brigue. Ao mesmo tempo, sua chefia n\u00e3o quer perder lucro e ficar\u00e1 insatisfeita se voc\u00ea n\u00e3o deixar mais do que k<\/i> pessoas no bar.<\/p>\n

Infelizmente, a tarefa que voc\u00ea enfrenta \u00e9 uma cl\u00e1ssica tarefa NP-dif\u00edcil. Voc\u00ea pode conhec\u00ea-la como Cobertura de V\u00e9rtices<\/a><\/noindex>, ou como uma tarefa de cobertura de v\u00e9rtices. Para tais tarefas, em geral, n\u00e3o existem algoritmos que funcionem em um tempo aceit\u00e1vel. Para ser preciso, uma hip\u00f3tese n\u00e3o comprovada e bastante forte, a ETH (Hip\u00f3tese do Tempo Exponencial), sugere que essa tarefa n\u00e3o pode ser resolvida dentro de um tempo razo\u00e1vel. \"Como, ou seja, que n\u00e3o \u00e9 poss\u00edvel pensar em algo significativamente melhor do que a for\u00e7a bruta. Por exemplo, suponha que um grupo de n = 1000<\/i> pessoas vai chegar ao seu bar. Assim, a for\u00e7a bruta envolveria verificar \"Como op\u00e7\u00f5es, o que \u00e9 aproximadamente \"Como \u2014 um n\u00famero surreal. Felizmente, sua ger\u00eancia imp\u00f4s uma limita\u00e7\u00e3o k = 10<\/i>, ent\u00e3o o n\u00famero de combina\u00e7\u00f5es que voc\u00ea precisa verificar \u00e9 muito menor: o n\u00famero de subconjuntos de dez elementos \u00e9 igual a \"Como. Isso j\u00e1 \u00e9 melhor, mas ainda assim n\u00e3o ser\u00e1 contado em um dia, mesmo em um cluster poderoso.
\n\"Como
\nPara evitar a possibilidade de brigas nessa configura\u00e7\u00e3o de rela\u00e7\u00f5es tensas entre os clientes do bar, voc\u00ea deve impedir a entrada de Bob, Daniel e Fi\u00f3dor. N\u00e3o existe uma solu\u00e7\u00e3o na qual apenas duas pessoas fiquem de fora.<\/p>\n

Isso significa que \u00e9 hora de desistir e deixar todos entrarem? Vamos considerar outras op\u00e7\u00f5es. Bem, por exemplo, pode-se n\u00e3o permitir a entrada apenas daqueles que provavelmente brigariam com um grande n\u00famero de pessoas. Se algu\u00e9m pode brigar com pelo menos k + 1<\/i> outra pessoa, ent\u00e3o essa pessoa n\u00e3o deve ser admitida \u2014 caso contr\u00e1rio, voc\u00ea teria que impedir a entrada de todos k + 1<\/i> os cidad\u00e3os com quem ele poderia brigar, o que certamente desagrada a ger\u00eancia.<\/p>\n

Suponha que voc\u00ea tenha barrado todas as pessoas que poderia com base neste princ\u00edpio. Ent\u00e3o, todos os outros podem brigar com no m\u00e1ximo k<\/i> pessoas. Se voc\u00ea expulsar delas k<\/i> pessoas, voc\u00ea pode evitar no m\u00e1ximo \"Como conflitos. Portanto, se houver mais de \"Como pessoas envolvidas em pelo menos um conflito, voc\u00ea definitivamente n\u00e3o conseguir\u00e1 evitar todos. Assim, como \u00e9 evidente, as pessoas que n\u00e3o geram conflitos devem ser admitidas, voc\u00ea precisar\u00e1 verificar todos os subconjuntos de tamanho dez de duzentas pessoas. S\u00e3o aproximadamente \"Como, e essa quantidade de opera\u00e7\u00f5es j\u00e1 pode ser verificada em um cluster.<\/p>\n

Se for poss\u00edvel aceitar pessoas que n\u00e3o est\u00e3o em conflito, o que dizer daqueles que participam de apenas um conflito? Na verdade, tamb\u00e9m podemos deix\u00e1-los entrar, fechando a porta para seu oponente. E \u00e9 verdade, se Alice est\u00e1 em conflito apenas com Bob, ao deixarmos Alice entrar, n\u00e3o perdemos: Bob pode ter outros conflitos, enquanto Alice definitivamente n\u00e3o tem. Al\u00e9m disso, faz pouco sentido n\u00e3o permitir a entrada de ambos. Ap\u00f3s essas opera\u00e7\u00f5es, n\u00e3o restar\u00e1 mais que \"Como convidados com destino incerto: no total temos \"Como conflitos, com duas pessoas em cada um e cada uma participando de pelo menos dois. Isso significa que resta apenas \"Como variantes a serem consideradas, o que pode ser feito em meio dia no laptop.<\/p>\n

Na verdade, com racioc\u00ednios simples \u00e9 poss\u00edvel chegar a condi\u00e7\u00f5es ainda mais atraentes. Vamos observar que precisamos resolver todas as disputas, ou seja, de cada par em conflito, precisamos escolher pelo menos uma pessoa que n\u00e3o deixaremos entrar. Vamos considerar o seguinte algoritmo: pegamos qualquer conflito, removemos um dos participantes e iniciamos recursivamente a partir do restante; depois removemos o outro e tamb\u00e9m iniciamos recursivamente. Como em cada passo descartamos algu\u00e9m, a \u00e1rvore de recurs\u00e3o desse algoritmo \u00e9 uma \u00e1rvore bin\u00e1ria de profundidade k<\/i>, portanto, o algoritmo funciona em \"Como, onde n<\/i> \u2014 n\u00famero de v\u00e9rtices, e m<\/i> \u2014 n\u00famero de arestas. No nosso exemplo, isso \u00e9 em torno de dez milh\u00f5es, o que pode ser calculado em fra\u00e7\u00f5es de segundo, n\u00e3o apenas em um laptop, mas at\u00e9 mesmo em um telefone m\u00f3vel.<\/p>\n

O exemplo acima \u00e9 um exemplo de algoritmo parametrizado<\/b>. Algoritmos parametrizados s\u00e3o aqueles que operam em tempo f(k) poly(n)<\/i>, onde p<\/i> \u2014 um polin\u00f4mio, f<\/i> \u2014 uma fun\u00e7\u00e3o comput\u00e1vel arbitr\u00e1ria, e k<\/i> \u2014 algum par\u00e2metro que, possivelmente, ser\u00e1 muito menor que o tamanho do problema.<\/p>\n

Todos os racioc\u00ednios at\u00e9 este algoritmo levam ao exemplo de kerneliza\u00e7\u00e3o<\/b> \u2014 uma das t\u00e9cnicas comuns para criar algoritmos parametrizados. Kernaliza\u00e7\u00e3o \u00e9 a redu\u00e7\u00e3o do tamanho do problema a um valor limitado por uma fun\u00e7\u00e3o em rela\u00e7\u00e3o ao par\u00e2metro. O problema resultante \u00e9 frequentemente chamado de n\u00facleo. Assim, com considera\u00e7\u00f5es simples sobre os graus dos v\u00e9rtices, obtemos um n\u00facleo quadr\u00e1tico para o problema de Vertex Cover, parametrizado pelo tamanho da resposta. Existem outros par\u00e2metros que podem ser escolhidos para este problema (por exemplo, Vertex Cover Above LP), mas discutiremos especificamente esse par\u00e2metro.<\/p>\n

Desafio Pace<\/h3>\n

Competi\u00e7\u00e3o Desafio PACE<\/a><\/noindex> (O Desafio de Algoritmos Parametrizados e Experi\u00eancias Computacionais) surgiu em 2015 para estabelecer uma conex\u00e3o entre algoritmos parametrizados e abordagens utilizadas na pr\u00e1tica para resolver problemas computacionais. As tr\u00eas primeiras competi\u00e7\u00f5es foram dedicadas \u00e0 busca da largura de \u00e1rvore do grafo (Largura de \u00c1rvore<\/a><\/noindex>), \u00e0 busca pela \u00c1rvore de Steiner (\u00c1rvore de Steiner<\/a><\/noindex>) e \u00e0 busca por um conjunto de v\u00e9rtices que corta ciclos (Conjunto de V\u00e9rtices de Feedback<\/a><\/noindex>). Este ano, uma das tarefas em que os participantes puderam testar suas habilidades foi a mencionada tarefa de Vertex Cover.<\/p>\n

A competi\u00e7\u00e3o ganha popularidade a cada ano. Segundo dados preliminares, somente na competi\u00e7\u00e3o para resolver a tarefa de Vertex Cover participaram 24 equipes. Vale ressaltar que a competi\u00e7\u00e3o n\u00e3o dura algumas horas ou at\u00e9 mesmo uma semana, mas v\u00e1rios meses. As equipes t\u00eam a oportunidade de estudar a literatura, inventar uma ideia original e tentar implement\u00e1-la. Essencialmente, esta competi\u00e7\u00e3o representa um trabalho de pesquisa. As ideias para as solu\u00e7\u00f5es mais eficazes e a premia\u00e7\u00e3o dos vencedores acontecer\u00e3o juntamente com a confer\u00eancia IPEC<\/a><\/noindex> (Simposio Internacional sobre C\u00e1lculo Parametrizado e Exato) no maior encontro anual de algoritmos na Europa ALGO<\/a><\/noindex>. Informa\u00e7\u00f5es mais detalhadas sobre a competi\u00e7\u00e3o podem ser encontradas em site<\/a><\/noindex>, e os resultados dos anos anteriores est\u00e3o dispon\u00edveis em aqui<\/a><\/noindex>.<\/p>\n

Esquema de solu\u00e7\u00e3o<\/h3>\n

Para lidar com o problema da cobertura de v\u00e9rtices, tentei aplicar algoritmos parametrizados. Eles geralmente consistem em duas partes: regras de simplifica\u00e7\u00e3o (que idealmente levam \u00e0 kerneliza\u00e7\u00e3o) e regras de divis\u00e3o. As regras de simplifica\u00e7\u00e3o s\u00e3o uma pr\u00e9-processamento da entrada em tempo polinomial. O objetivo da aplica\u00e7\u00e3o dessas regras \u00e9 reduzir o problema a um equivalente de menor tamanho. As regras de simplifica\u00e7\u00e3o s\u00e3o a parte mais custosa do algoritmo, e a aplica\u00e7\u00e3o apenas dessa parte leva a um tempo total maior. \"Como Em vez de um tempo polinomial simples. No nosso caso, as regras de divis\u00e3o s\u00e3o baseadas no fato de que para cada v\u00e9rtice precisamos escolher como resposta ou ele ou seu vizinho.<\/p>\n

O esquema geral \u00e9 o seguinte: aplicamos as regras de simplifica\u00e7\u00e3o, depois escolhemos um v\u00e9rtice e fazemos duas chamadas recursivas: na primeira, pegamos ele como resposta, e na outra, pegamos todos os seus vizinhos. Chamamos isso de dividir (branching) por esse v\u00e9rtice.<\/p>\n

Para esse esquema, ser\u00e1 feita exatamente uma adi\u00e7\u00e3o no pr\u00f3ximo par\u00e1grafo.<\/p>\n

Ideias para regras de divis\u00e3o (branching)<\/h3>\n

Vamos discutir como escolher o v\u00e9rtice por onde a divis\u00e3o ocorrer\u00e1.
\nA ideia principal \u00e9 muito gananciosa em termos algor\u00edtmicos: vamos escolher o v\u00e9rtice de maior grau e dividir exatamente por ele. Por que parece que isso \u00e9 melhor? Porque na segunda ramifica\u00e7\u00e3o da chamada recursiva, assim eliminamos muitos v\u00e9rtices. Podemos esperar que reste um grafo pequeno e que nele possamos trabalhar rapidamente.<\/p>\n

Essa abordagem, juntamente com as t\u00e9cnicas simples de kerneliza\u00e7\u00e3o j\u00e1 discutidas, se mostra satisfat\u00f3ria, resolvendo alguns testes com milhares de v\u00e9rtices. Mas, por exemplo, funciona mal para grafos c\u00fabicos (ou seja, grafos em que o grau de cada v\u00e9rtice \u00e9 tr\u00eas).
\nH\u00e1 tamb\u00e9m outra ideia, baseada em uma no\u00e7\u00e3o bastante simples: se o grafo \u00e9 desconexo, o problema em suas componentes conexas pode ser resolvido independentemente, reunindo as respostas no final. Esse, ali\u00e1s, \u00e9 a pequena modifica\u00e7\u00e3o prometida no esquema, que acelerar\u00e1 significativamente a solu\u00e7\u00e3o: anteriormente, nesse caso, trabalh\u00e1vamos com o produto dos tempos de contagem das respostas das componentes, e agora trabalhamos com a soma. E para acelerar a divis\u00e3o, precisamos transformar um grafo conexo em um desconexo.<\/p>\n

Como fazer isso? Se o grafo tiver um ponto de articula\u00e7\u00e3o, \u00e9 necess\u00e1rio ramificar exatamente por ele. Um ponto de articula\u00e7\u00e3o \u00e9 um v\u00e9rtice cuja remo\u00e7\u00e3o faz o grafo perder a conectividade. Encontrar todos os pontos de articula\u00e7\u00e3o em um grafo pode ser feito com um algoritmo cl\u00e1ssico em tempo linear. Essa abordagem acelera significativamente a ramifica\u00e7\u00e3o.
\n\"Como
\nAo remover qualquer um dos v\u00e9rtices destacados, o grafo se dividir\u00e1 em componentes de conectividade.<\/p>\n

Isso faremos, mas queremos mais. Por exemplo, buscar pequenos cortes de v\u00e9rtices no grafo e realizar a separa\u00e7\u00e3o com base neles. O m\u00e9todo mais eficiente que conhe\u00e7o para encontrar o corte global m\u00ednimo de v\u00e9rtices \u00e9 usar a \u00e1rvore de Gomory-Hu, que \u00e9 constru\u00edda em tempo c\u00fabico. No PACE Challenge, o tamanho t\u00edpico do grafo \u00e9 de alguns milhares de v\u00e9rtices. Com essa escala, em cada v\u00e9rtice da \u00e1rvore de recurs\u00e3o s\u00e3o necess\u00e1rias bilh\u00f5es de opera\u00e7\u00f5es. Portanto, resolver essa tarefa no tempo estipulado \u00e9 simplesmente imposs\u00edvel.<\/p>\n

Vamos tentar otimizar a solu\u00e7\u00e3o. O corte m\u00ednimo de v\u00e9rtices entre um par de v\u00e9rtices pode ser encontrado por qualquer algoritmo que construa o fluxo m\u00e1ximo. Podemos aplicar o algoritmo de Dinic<\/a><\/noindex>, que na pr\u00e1tica funciona muito r\u00e1pido. Suspeito que teoricamente \u00e9 poss\u00edvel provar uma estimativa para o tempo de execu\u00e7\u00e3o \"Como, que j\u00e1 \u00e9 bastante aceit\u00e1vel.<\/p>\n

Tentei v\u00e1rias vezes encontrar cortes entre pares de v\u00e9rtices aleat\u00f3rios e escolher o mais equilibrado entre eles. Infelizmente, isso produziu resultados ruins em testes abertos do PACE Challenge. Comparei com um algoritmo que se ramificava a partir de v\u00e9rtices de grau m\u00e1ximo, executando-os com uma limita\u00e7\u00e3o na profundidade de busca. Ap\u00f3s o algoritmo que tenta encontrar o corte dessa forma, restaram grafos de maior tamanho. Isso ocorre porque os cortes obtidos eram muito desequilibrados: ao remover de 5 a 10 v\u00e9rtices, o m\u00e1ximo que consegui separar foi apenas de 15 a 20.<\/p>\n

Vale mencionar que nos artigos sobre os algoritmos teoricamente mais r\u00e1pidos, t\u00e9cnicas muito mais avan\u00e7adas de sele\u00e7\u00e3o de v\u00e9rtices para separa\u00e7\u00e3o s\u00e3o utilizadas. Essas t\u00e9cnicas t\u00eam implementa\u00e7\u00f5es muito complexas e, muitas vezes, avalia\u00e7\u00f5es ruins em rela\u00e7\u00e3o ao tempo e \u00e0 mem\u00f3ria. N\u00e3o consegui identificar delas op\u00e7\u00f5es que fossem razo\u00e1veis para a pr\u00e1tica.<\/p>\n

Como aplicar as regras de simplifica\u00e7\u00e3o<\/h3>\n

J\u00e1 temos ideias de kerneliza\u00e7\u00e3o. Lembro:<\/p>\n

    \n
  1. Se houver um v\u00e9rtice isolado, remov\u00ea-lo.<\/li>\n
  2. Se houver um v\u00e9rtice de grau 1, remova-o e tome seu vizinho como resposta.<\/li>\n
  3. Se houver um v\u00e9rtice de grau pelo menos k + 1<\/i>, tome-o como resposta.<\/li>\n<\/ol>\n

    Com os dois primeiros tudo est\u00e1 claro, mas com o terceiro h\u00e1 um truque. Se na tarefa humor\u00edstica sobre o bar nos foi dada uma restri\u00e7\u00e3o superior sobre k<\/i>, no PACE Challenge \u00e9 preciso apenas encontrar uma cobertura de v\u00e9rtices de tamanho m\u00ednimo. Esta \u00e9 uma transforma\u00e7\u00e3o t\u00edpica de problemas de busca (Search Problem) em problemas de decis\u00e3o (Decision Problem), frequentemente entre dois tipos de problemas n\u00e3o se faz distin\u00e7\u00e3o. Na pr\u00e1tica, se estamos escrevendo um resolvedor para o problema de cobertura de v\u00e9rtices, a diferen\u00e7a pode existir. Por exemplo, como no terceiro ponto.<\/p>\n

    Do ponto de vista da implementa\u00e7\u00e3o, existem duas abordagens. A primeira abordagem \u00e9 chamada de Aprofundamento Iterativo. Ela consiste no seguinte: podemos come\u00e7ar com alguma restri\u00e7\u00e3o razo\u00e1vel inferior sobre a resposta e, em seguida, executar nosso algoritmo, usando essa restri\u00e7\u00e3o como limite superior na resposta, n\u00e3o descendo em recurs\u00f5es mais profundas do que essa restri\u00e7\u00e3o. Se encontramos alguma resposta, ela \u00e9 garantidamente \u00f3tima, caso contr\u00e1rio, podemos aumentar essa restri\u00e7\u00e3o em uma unidade e reiniciar.<\/p>\n

    A segunda abordagem \u00e9 armazenar alguma resposta \u00f3tima atual e procurar uma resposta de menor tamanho, ao encontr\u00e1-la, alterando esse par\u00e2metro k<\/i> para um maior corte de ramos desnecess\u00e1rios na busca.<\/p>\n

    Ap\u00f3s realizar algumas experimenta\u00e7\u00f5es noturnas, decidi por uma combina\u00e7\u00e3o dessas duas abordagens: primeiro, executo meu algoritmo com alguma restri\u00e7\u00e3o na profundidade da busca (ajustando-a para que leve um tempo insignificante em compara\u00e7\u00e3o com a solu\u00e7\u00e3o principal) e uso a melhor solu\u00e7\u00e3o encontrada como limite superior para a resposta \u2014 ou seja, para aquele k<\/i>.<\/p>\n

    V\u00e9rtices de grau 2<\/h3>\n

    Com os v\u00e9rtices de grau 0 e 1 nos esclarecemos. Aparentemente, isso pode ser feito tamb\u00e9m com v\u00e9rtices de grau 2, mas para isso o gr\u00e1fico exigir\u00e1 opera\u00e7\u00f5es mais complexas.<\/p>\n

    Para explicar isso, precisaremos de alguma forma de denotar os v\u00e9rtices. Chamaremos o v\u00e9rtice de grau 2 de v\u00e9rtice v<\/i>, e seus vizinhos de v\u00e9rtices x<\/i> e y<\/i>. A seguir, teremos dois casos.<\/p>\n

      \n
    1. Quando x<\/i> e y<\/i> \u2014 vizinhos. Ent\u00e3o podemos tomar como resposta x<\/i> e y<\/i>, e v<\/i> remover. E de fato, a partir deste tri\u00e2ngulo, pelo menos dois v\u00e9rtices precisam ser tomados como resposta e com certeza n\u00e3o iremos perder se tomarmos x<\/i> e y<\/i>: eles provavelmente t\u00eam mais vizinhos, enquanto v<\/i> eles n\u00e3o t\u00eam.<\/li>\n
    2. Quando x<\/i> e y<\/i> \u2014 n\u00e3o vizinhos. Ent\u00e3o, afirma-se que os tr\u00eas v\u00e9rtices podem ser fundidos em um s\u00f3. A ideia \u00e9 que, nesse caso, existe uma resposta \u00f3tima, na qual escolheremos ou v<\/i>, ou ambos os v\u00e9rtices x<\/i> e y<\/i>. De fato, no primeiro caso, teremos que considerar todos os vizinhos na resposta x<\/i> e y<\/i>, enquanto no segundo n\u00e3o \u00e9 obrigatoriamente necess\u00e1rio. Isso corresponde exatamente aos casos em que n\u00e3o inclu\u00edmos o v\u00e9rtice fundido na resposta e quando o inclu\u00edmos. Resta apenas notar que, em ambos os casos, a resposta dessa opera\u00e7\u00e3o diminui em uma unidade.<\/li>\n<\/ol>\n

      \"Como<\/p>\n

      Vale a pena notar que tal abordagem \u00e9 bastante dif\u00edcil de implementar de maneira cuidadosa em tempo linear real. A fus\u00e3o dos v\u00e9rtices \u00e9 uma opera\u00e7\u00e3o complexa, sendo necess\u00e1rio copiar as listas de vizinhos. Se n\u00e3o for feita com cuidado, pode-se obter um tempo de execu\u00e7\u00e3o assintoticamente n\u00e3o otimizado (por exemplo, se ap\u00f3s cada fus\u00e3o copiar muitas arestas). Parei de procurar por caminhos inteiros a partir de v\u00e9rtices de grau 2 e de analisar uma s\u00e9rie de casos particulares, como ciclos envolvendo esses v\u00e9rtices ou todos esses v\u00e9rtices, exceto um.<\/p>\n

      Al\u00e9m disso, \u00e9 necess\u00e1rio que essa opera\u00e7\u00e3o seja revers\u00edvel, para que, ao retornar da recurs\u00e3o, possamos restaurar o gr\u00e1fico ao seu estado original. Para garantir isso, n\u00e3o limpei as listas de arestas dos v\u00e9rtices fundidos, ap\u00f3s o que apenas sabia quais arestas deveriam ser direcionadas. Essa implementa\u00e7\u00e3o de grafos tamb\u00e9m requer cuidado, mas garante um tempo linear real. Para gr\u00e1ficos com algumas dezenas de milhares de arestas, isso cabe perfeitamente no cache do processador, o que traz grandes vantagens em velocidade.<\/p>\n

      N\u00facleo Linear<\/h3>\n

      Finalmente, a parte mais interessante do n\u00facleo.<\/p>\n

      Para come\u00e7ar, lembremos que em grafos bipartidos, o m\u00ednimo conjunto de cobertura de v\u00e9rtices pode ser buscado em \"Como. Para isso, \u00e9 necess\u00e1rio utilizar o algoritmo Hopcroft-Karp<\/a><\/noindex> para encontrar l\u00e1 um emparelhamento m\u00e1ximo e depois utilizar o teorema K\u00f6nig-Egerv\u00e1ry<\/a><\/noindex>.<\/p>\n

      A ideia do n\u00facleo linear \u00e9 a seguinte: primeiro dividimos o gr\u00e1fico, ou seja, em vez de cada v\u00e9rtice v<\/i> , criamos dois v\u00e9rtices \"Como e \"Como, e em vez de cada aresta u \u2014 v<\/i> , criamos duas arestas \"Como e \"ComoO gr\u00e1fico resultante ser\u00e1 bipartido. Vamos encontrar a cobertura m\u00ednima de v\u00e9rtices nele. Algumas v\u00e9rtices do gr\u00e1fico original aparecer\u00e3o l\u00e1 duas vezes, algumas apenas uma vez, e algumas nenhuma. O teorema de Nemhauser-Trotter afirma que, nesse caso, podemos remover os v\u00e9rtices que n\u00e3o apareceram e considerar como resposta aqueles que apareceram duas vezes. Mais importante, ele diz que, dos v\u00e9rtices restantes (aqueles que apareceram uma vez), devemos considerar como resposta pelo menos metade.<\/p>\n

      Acabamos de aprender a deixar no gr\u00e1fico n\u00e3o mais do que 2k<\/i> v\u00e9rtices. De fato, se na resposta restante houver pelo menos metade de todos os v\u00e9rtices, ent\u00e3o o total de v\u00e9rtices n\u00e3o \u00e9 maior que 2k<\/i>.<\/p>\n

      Aqui consegui dar um pequeno passo \u00e0 frente. Est\u00e1 claro que o n\u00facleo constru\u00eddo dessa maneira depende de qual cobertura m\u00ednima de v\u00e9rtices em um gr\u00e1fico bipartido escolhemos. Queremos escolher uma que minimize o n\u00famero de v\u00e9rtices restantes. Anteriormente, isso s\u00f3 podia ser feito em um tempo \"Como. Eu consegui desenvolver a implementa\u00e7\u00e3o deste algoritmo em um tempo \"Como, assim, este n\u00facleo pode ser buscado em gr\u00e1ficos com centenas de milhares de v\u00e9rtices em cada etapa de ramifica\u00e7\u00e3o.<\/p>\n

      Resultado<\/h3>\n

      A pr\u00e1tica mostra que minha solu\u00e7\u00e3o funciona bem em testes com algumas centenas de v\u00e9rtices e milhares de arestas. Em tais testes, \u00e9 razo\u00e1vel esperar que a solu\u00e7\u00e3o seja encontrada em meia hora. A probabilidade de encontrar uma resposta em um tempo aceit\u00e1vel aumenta se o gr\u00e1fico tiver muitos v\u00e9rtices de alto grau, por exemplo, grau 10 ou mais.<\/p>\n

      Para participar da competi\u00e7\u00e3o, as solu\u00e7\u00f5es precisavam ser enviadas para optil.io<\/a><\/noindex>. De acordo com a tabela apresentada l\u00e1 , minha solu\u00e7\u00e3o ocupa o terceiro lugar em testes abertos, com uma boa margem sobre o segundo. Para ser completamente honesto, n\u00e3o est\u00e1 claro como as solu\u00e7\u00f5es ser\u00e3o avaliadas na pr\u00f3pria competi\u00e7\u00e3o: por exemplo, minha solu\u00e7\u00e3o passa em menos testes do que a que est\u00e1 em quarto lugar, mas ela funciona mais r\u00e1pido nos testes que passa.<\/a><\/noindex>Os resultados dos testes fechados ser\u00e3o conhecidos no primeiro de julho.<\/p>\n

      A pesquisa acad\u00eamica \u00e9, sem d\u00favida, a parte mais interessante do nosso aprendizado. A ideia \u00e9 experimentar a \u00e1rea escolhida j\u00e1 na universidade.<\/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\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\udd47Como resolver problemas NP-dif\u00edceis com algoritmos param\u00e9tricos | ProHoster","description":"\ud83e\udd47Como resolver problemas NP-dif\u00edceis com algoritmos param\u00e9tricos | ProHoster","canonical_url":"https:\/\/prohoster.info\/pt\/blog\/news\/kak-reshat-np-trudnye-zadachi-s-pomoshhyu-parametrizovannyh-algoritmov","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"pt_PT","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\/pt\/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\/pt\/wp-json\/wp\/v2\/posts\/35406","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/comments?post=35406"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/posts\/35406\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/media\/26562"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/media?parent=35406"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/categories?post=35406"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/pt\/wp-json\/wp\/v2\/tags?post=35406"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}