A pesquisa científica é, sem dúvida, a parte mais interessante do nosso aprendizado. A ideia é tentar se aventurar na direção escolhida ainda na universidade. Por exemplo, estudantes das áreas de Engenharia de Software e Aprendizado de Máquina frequentemente buscam realizar trabalhos de pesquisa em empresas (principalmente, JetBrains ou Yandex, mas não apenas).
Neste post, vou falar sobre meu projeto na área de Ciência da Computação. No âmbito do trabalho, eu estudei e implementei na prática abordagens para resolver um dos problemas NP-difíceis mais conhecidos: o problema do cobertura de vértices.
Atualmente, um interessante enfoque para problemas NP-difíceis está se desenvolvendo rapidamente — algoritmos parametrizados. Vou tentar mantê-lo a par, explicando alguns algoritmos parametrizados simples e descrevendo um método poderoso que me ajudou bastante. Apresentei meus resultados na competição PACE Challenge: após os testes abertos, minha solução ocupa o terceiro lugar, e os resultados finais serão conhecidos em 1 de julho.
Sobre mim
Meu nome é Vasiliy Alferov, e estou concluindo o terceiro ano na НИУ ВШЭ — São Petersburgo. Tenho me interessado por algoritmos desde os tempos de escola, quando estudava na escola 179 de Moscovo e participei com sucesso em olimpíadas de informática.
Um número finito de especialistas em algoritmos parametrizados entra em um bar...
O exemplo foi retirado do livro
Imagine que você é o segurança de um bar em uma pequena cidade. Toda sexta-feira, metade da cidade vai ao seu bar para relaxar, o que traz muitos problemas: é preciso expulsar os frequentadores agitados para evitar brigas. No final, você fica cansado disso e decide tomar medidas preventivas.
Como a cidade é pequena, você sabe exatamente quais pares de visitantes têm uma alta probabilidade de brigar se estiverem no bar juntos. Você tem uma lista de n pessoas que vão chegar esta noite ao bar. Você decide não deixar entrar certos cidadãos da cidade de forma que ninguém brigue. Ao mesmo tempo, sua chefia não quer perder lucro e ficará insatisfeita se você não deixar mais do que k pessoas no bar.
Infelizmente, a tarefa que você enfrenta é uma clássica tarefa NP-difícil. Você pode conhecê-la como , ou como uma tarefa de cobertura de vértices. Para tais tarefas, em geral, não existem algoritmos que funcionem em um tempo aceitável. Para ser preciso, uma hipótese não comprovada e bastante forte, a ETH (Hipótese do Tempo Exponencial), sugere que essa tarefa não pode ser resolvida dentro de um tempo razoável. 
, ou seja, que não é possível pensar em algo significativamente melhor do que a força bruta. Por exemplo, suponha que um grupo de n = 1000 pessoas vai chegar ao seu bar. Assim, a força bruta envolveria verificar 
opções, o que é aproximadamente 
— um número surreal. Felizmente, sua gerência impôs uma limitação k = 10, então o número de combinações que você precisa verificar é muito menor: o número de subconjuntos de dez elementos é igual a 
. Isso já é melhor, mas ainda assim não será contado em um dia, mesmo em um cluster poderoso.
Para evitar a possibilidade de brigas nessa configuração de relações tensas entre os clientes do bar, você deve impedir a entrada de Bob, Daniel e Fiódor. Não existe uma solução na qual apenas duas pessoas fiquem de fora.
Isso significa que é hora de desistir e deixar todos entrarem? Vamos considerar outras opções. Bem, por exemplo, pode-se não permitir a entrada apenas daqueles que provavelmente brigariam com um grande número de pessoas. Se alguém pode brigar com pelo menos k + 1 outra pessoa, então essa pessoa não deve ser admitida — caso contrário, você teria que impedir a entrada de todos k + 1 os cidadãos com quem ele poderia brigar, o que certamente desagrada a gerência.
Suponha que você tenha barrado todas as pessoas que poderia com base neste princípio. Então, todos os outros podem brigar com no máximo k pessoas. Se você expulsar delas k pessoas, você pode evitar no máximo 
conflitos. Portanto, se houver mais de 
pessoas envolvidas em pelo menos um conflito, você definitivamente não conseguirá evitar todos. Assim, como é evidente, as pessoas que não geram conflitos devem ser admitidas, você precisará verificar todos os subconjuntos de tamanho dez de duzentas pessoas. São aproximadamente 
, e essa quantidade de operações já pode ser verificada em um cluster.
Se for possível aceitar pessoas que não estão em conflito, o que dizer daqueles que participam de apenas um conflito? Na verdade, também podemos deixá-los entrar, fechando a porta para seu oponente. E é verdade, se Alice está em conflito apenas com Bob, ao deixarmos Alice entrar, não perdemos: Bob pode ter outros conflitos, enquanto Alice definitivamente não tem. Além disso, faz pouco sentido não permitir a entrada de ambos. Após essas operações, não restará mais que 
convidados com destino incerto: no total temos 
conflitos, com duas pessoas em cada um e cada uma participando de pelo menos dois. Isso significa que resta apenas 
variantes a serem consideradas, o que pode ser feito em meio dia no laptop.
Na verdade, com raciocínios simples é possível chegar a condições 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ão 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ém iniciamos recursivamente. Como em cada passo descartamos alguém, a árvore de recursão desse algoritmo é uma árvore binária de profundidade k, portanto, o algoritmo funciona em 
, onde n — número de vértices, e m — número de arestas. No nosso exemplo, isso é em torno de dez milhões, o que pode ser calculado em frações de segundo, não apenas em um laptop, mas até mesmo em um telefone móvel.
O exemplo acima é um exemplo de algoritmo parametrizado. Algoritmos parametrizados são aqueles que operam em tempo f(k) poly(n), onde p — um polinômio, f — uma função computável arbitrária, e k — algum parâmetro que, possivelmente, será muito menor que o tamanho do problema.
Todos os raciocínios até este algoritmo levam ao exemplo de kernelização — uma das técnicas comuns para criar algoritmos parametrizados. Kernalização é a redução do tamanho do problema a um valor limitado por uma função em relação ao parâmetro. O problema resultante é frequentemente chamado de núcleo. Assim, com considerações simples sobre os graus dos vértices, obtemos um núcleo quadrático para o problema de Vertex Cover, parametrizado pelo tamanho da resposta. Existem outros parâmetros que podem ser escolhidos para este problema (por exemplo, Vertex Cover Above LP), mas discutiremos especificamente esse parâmetro.
Desafio Pace
Competição (O Desafio de Algoritmos Parametrizados e Experiências Computacionais) surgiu em 2015 para estabelecer uma conexão entre algoritmos parametrizados e abordagens utilizadas na prática para resolver problemas computacionais. As três primeiras competições foram dedicadas à busca da largura de árvore do grafo (), à busca pela Árvore de Steiner () e à busca por um conjunto de vértices que corta ciclos (). Este ano, uma das tarefas em que os participantes puderam testar suas habilidades foi a mencionada tarefa de Vertex Cover.
A competição ganha popularidade a cada ano. Segundo dados preliminares, somente na competição para resolver a tarefa de Vertex Cover participaram 24 equipes. Vale ressaltar que a competição não dura algumas horas ou até mesmo uma semana, mas vários meses. As equipes têm a oportunidade de estudar a literatura, inventar uma ideia original e tentar implementá-la. Essencialmente, esta competição representa um trabalho de pesquisa. As ideias para as soluções mais eficazes e a premiação dos vencedores acontecerão juntamente com a conferência (Simposio Internacional sobre Cálculo Parametrizado e Exato) no maior encontro anual de algoritmos na Europa . Informações mais detalhadas sobre a competição podem ser encontradas em , e os resultados dos anos anteriores estão disponíveis em .
Esquema de solução
Para lidar com o problema da cobertura de vértices, tentei aplicar algoritmos parametrizados. Eles geralmente consistem em duas partes: regras de simplificação (que idealmente levam à kernelização) e regras de divisão. As regras de simplificação são uma pré-processamento da entrada em tempo polinomial. O objetivo da aplicação dessas regras é reduzir o problema a um equivalente de menor tamanho. As regras de simplificação são a parte mais custosa do algoritmo, e a aplicação apenas dessa parte leva a um tempo total maior. 
Em vez de um tempo polinomial simples. No nosso caso, as regras de divisão são baseadas no fato de que para cada vértice precisamos escolher como resposta ou ele ou seu vizinho.
O esquema geral é o seguinte: aplicamos as regras de simplificação, depois escolhemos um vértice 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értice.
Para esse esquema, será feita exatamente uma adição no próximo parágrafo.
Ideias para regras de divisão (branching)
Vamos discutir como escolher o vértice por onde a divisão ocorrerá.
A ideia principal é muito gananciosa em termos algorítmicos: vamos escolher o vértice de maior grau e dividir exatamente por ele. Por que parece que isso é melhor? Porque na segunda ramificação da chamada recursiva, assim eliminamos muitos vértices. Podemos esperar que reste um grafo pequeno e que nele possamos trabalhar rapidamente.
Essa abordagem, juntamente com as técnicas simples de kernelização já discutidas, se mostra satisfatória, resolvendo alguns testes com milhares de vértices. Mas, por exemplo, funciona mal para grafos cúbicos (ou seja, grafos em que o grau de cada vértice é três).
Há também outra ideia, baseada em uma noção bastante simples: se o grafo é desconexo, o problema em suas componentes conexas pode ser resolvido independentemente, reunindo as respostas no final. Esse, aliás, é a pequena modificação prometida no esquema, que acelerará significativamente a solução: anteriormente, nesse caso, trabalhávamos com o produto dos tempos de contagem das respostas das componentes, e agora trabalhamos com a soma. E para acelerar a divisão, precisamos transformar um grafo conexo em um desconexo.
Como fazer isso? Se o grafo tiver um ponto de articulação, é necessário ramificar exatamente por ele. Um ponto de articulação é um vértice cuja remoção faz o grafo perder a conectividade. Encontrar todos os pontos de articulação em um grafo pode ser feito com um algoritmo clássico em tempo linear. Essa abordagem acelera significativamente a ramificação.
Ao remover qualquer um dos vértices destacados, o grafo se dividirá em componentes de conectividade.
Isso faremos, mas queremos mais. Por exemplo, buscar pequenos cortes de vértices no grafo e realizar a separação com base neles. O método mais eficiente que conheço para encontrar o corte global mínimo de vértices é usar a árvore de Gomory-Hu, que é construída em tempo cúbico. No PACE Challenge, o tamanho típico do grafo é de alguns milhares de vértices. Com essa escala, em cada vértice da árvore de recursão são necessárias bilhões de operações. Portanto, resolver essa tarefa no tempo estipulado é simplesmente impossível.
Vamos tentar otimizar a solução. O corte mínimo de vértices entre um par de vértices pode ser encontrado por qualquer algoritmo que construa o fluxo máximo. Podemos aplicar , que na prática funciona muito rápido. Suspeito que teoricamente é possível provar uma estimativa para o tempo de execução 
, que já é bastante aceitável.
Tentei várias vezes encontrar cortes entre pares de vértices aleatórios 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értices de grau máximo, executando-os com uma limitação na profundidade de busca. Após 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értices, o máximo que consegui separar foi apenas de 15 a 20.
Vale mencionar que nos artigos sobre os algoritmos teoricamente mais rápidos, técnicas muito mais avançadas de seleção de vértices para separação são utilizadas. Essas técnicas têm implementações muito complexas e, muitas vezes, avaliações ruins em relação ao tempo e à memória. Não consegui identificar delas opções que fossem razoáveis para a prática.
Como aplicar as regras de simplificação
Já temos ideias de kernelização. Lembro:
- Se houver um vértice isolado, removê-lo.
- Se houver um vértice de grau 1, remova-o e tome seu vizinho como resposta.
- Se houver um vértice de grau pelo menos k + 1, tome-o como resposta.
Com os dois primeiros tudo está claro, mas com o terceiro há um truque. Se na tarefa humorística sobre o bar nos foi dada uma restrição superior sobre k, no PACE Challenge é preciso apenas encontrar uma cobertura de vértices de tamanho mínimo. Esta é uma transformação típica de problemas de busca (Search Problem) em problemas de decisão (Decision Problem), frequentemente entre dois tipos de problemas não se faz distinção. Na prática, se estamos escrevendo um resolvedor para o problema de cobertura de vértices, a diferença pode existir. Por exemplo, como no terceiro ponto.
Do ponto de vista da implementação, existem duas abordagens. A primeira abordagem é chamada de Aprofundamento Iterativo. Ela consiste no seguinte: podemos começar com alguma restrição razoável inferior sobre a resposta e, em seguida, executar nosso algoritmo, usando essa restrição como limite superior na resposta, não descendo em recursões mais profundas do que essa restrição. Se encontramos alguma resposta, ela é garantidamente ótima, caso contrário, podemos aumentar essa restrição em uma unidade e reiniciar.
A segunda abordagem é armazenar alguma resposta ótima atual e procurar uma resposta de menor tamanho, ao encontrá-la, alterando esse parâmetro k para um maior corte de ramos desnecessários na busca.
Após realizar algumas experimentações noturnas, decidi por uma combinação dessas duas abordagens: primeiro, executo meu algoritmo com alguma restrição na profundidade da busca (ajustando-a para que leve um tempo insignificante em comparação com a solução principal) e uso a melhor solução encontrada como limite superior para a resposta — ou seja, para aquele k.
Vértices de grau 2
Com os vértices de grau 0 e 1 nos esclarecemos. Aparentemente, isso pode ser feito também com vértices de grau 2, mas para isso o gráfico exigirá operações mais complexas.
Para explicar isso, precisaremos de alguma forma de denotar os vértices. Chamaremos o vértice de grau 2 de vértice v, e seus vizinhos de vértices x e y. A seguir, teremos dois casos.
- Quando x e y — vizinhos. Então podemos tomar como resposta x e y, e v remover. E de fato, a partir deste triângulo, pelo menos dois vértices precisam ser tomados como resposta e com certeza não iremos perder se tomarmos x e y: eles provavelmente têm mais vizinhos, enquanto v eles não têm.
- Quando x e y — não vizinhos. Então, afirma-se que os três vértices podem ser fundidos em um só. A ideia é que, nesse caso, existe uma resposta ótima, na qual escolheremos ou v, ou ambos os vértices x e y. De fato, no primeiro caso, teremos que considerar todos os vizinhos na resposta x e y, enquanto no segundo não é obrigatoriamente necessário. Isso corresponde exatamente aos casos em que não incluímos o vértice fundido na resposta e quando o incluímos. Resta apenas notar que, em ambos os casos, a resposta dessa operação diminui em uma unidade.
Vale a pena notar que tal abordagem é bastante difícil de implementar de maneira cuidadosa em tempo linear real. A fusão dos vértices é uma operação complexa, sendo necessário copiar as listas de vizinhos. Se não for feita com cuidado, pode-se obter um tempo de execução assintoticamente não otimizado (por exemplo, se após cada fusão copiar muitas arestas). Parei de procurar por caminhos inteiros a partir de vértices de grau 2 e de analisar uma série de casos particulares, como ciclos envolvendo esses vértices ou todos esses vértices, exceto um.
Além disso, é necessário que essa operação seja reversível, para que, ao retornar da recursão, possamos restaurar o gráfico ao seu estado original. Para garantir isso, não limpei as listas de arestas dos vértices fundidos, após o que apenas sabia quais arestas deveriam ser direcionadas. Essa implementação de grafos também requer cuidado, mas garante um tempo linear real. Para gráficos com algumas dezenas de milhares de arestas, isso cabe perfeitamente no cache do processador, o que traz grandes vantagens em velocidade.
Núcleo Linear
Finalmente, a parte mais interessante do núcleo.
Para começar, lembremos que em grafos bipartidos, o mínimo conjunto de cobertura de vértices pode ser buscado em 
. Para isso, é necessário utilizar o algoritmo para encontrar lá um emparelhamento máximo e depois utilizar o teorema .
A ideia do núcleo linear é a seguinte: primeiro dividimos o gráfico, ou seja, em vez de cada vértice v , criamos dois vértices 
e 
, e em vez de cada aresta u — v , criamos duas arestas 
e 
O gráfico resultante será bipartido. Vamos encontrar a cobertura mínima de vértices nele. Algumas vértices do gráfico original aparecerão lá duas vezes, algumas apenas uma vez, e algumas nenhuma. O teorema de Nemhauser-Trotter afirma que, nesse caso, podemos remover os vértices que não apareceram e considerar como resposta aqueles que apareceram duas vezes. Mais importante, ele diz que, dos vértices restantes (aqueles que apareceram uma vez), devemos considerar como resposta pelo menos metade.
Acabamos de aprender a deixar no gráfico não mais do que 2k vértices. De fato, se na resposta restante houver pelo menos metade de todos os vértices, então o total de vértices não é maior que 2k.
Aqui consegui dar um pequeno passo à frente. Está claro que o núcleo construído dessa maneira depende de qual cobertura mínima de vértices em um gráfico bipartido escolhemos. Queremos escolher uma que minimize o número de vértices restantes. Anteriormente, isso só podia ser feito em um tempo 
. Eu consegui desenvolver a implementação deste algoritmo em um tempo 
, assim, este núcleo pode ser buscado em gráficos com centenas de milhares de vértices em cada etapa de ramificação.
Resultado
A prática mostra que minha solução funciona bem em testes com algumas centenas de vértices e milhares de arestas. Em tais testes, é razoável esperar que a solução seja encontrada em meia hora. A probabilidade de encontrar uma resposta em um tempo aceitável aumenta se o gráfico tiver muitos vértices de alto grau, por exemplo, grau 10 ou mais.
Para participar da competição, as soluções precisavam ser enviadas para . De acordo com a tabela apresentada lá Os resultados dos testes fechados serão conhecidos no primeiro de julho.
A pesquisa acadêmica é, sem dúvida, a parte mais interessante do nosso aprendizado. A ideia é experimentar a área escolhida já na universidade.
Fonte: habr.com
