O trabalho de pesquisa é talvez a parte mais interessante da nossa formação. A ideia é tentar a direção escolhida ainda na universidade. Por exemplo, estudantes das áreas de Engenharia de Software e Machine Learning vão frequentemente fazer pesquisas em empresas (principalmente JetBrains ou Yandex, mas não só).
Neste post falarei sobre meu projeto em Ciência da Computação. Como parte do meu trabalho, estudei e coloquei em prática abordagens para resolver um dos mais famosos problemas NP-difíceis: problema de cobertura de vértices.
Hoje em dia, uma abordagem interessante para problemas NP-difíceis está se desenvolvendo muito rapidamente - algoritmos parametrizados. Tentarei atualizá-lo, apresentar alguns algoritmos parametrizados simples e descrever um método poderoso que me ajudou muito. Apresentei meus resultados na competição PACE Challenge: de acordo com os resultados dos testes abertos, minha solução fica em terceiro lugar, e os resultados finais serão conhecidos no dia 1º de julho.
Quem sou eu
Meu nome é Vasily Alferov, estou terminando meu terceiro ano na Escola Superior de Economia da National Research University - São Petersburgo. Tenho me interessado por algoritmos desde meus tempos de escola, quando estudei na escola nº 179 de Moscou e participei com sucesso de olimpíadas de ciência da computação.
Um número finito de especialistas em algoritmos parametrizados entra na barra...
Exemplo retirado do livro
Imagine que você é segurança de um bar em uma cidade pequena. Toda sexta-feira, metade da cidade vem ao seu bar para relaxar, o que lhe dá muitos problemas: é preciso expulsar os clientes desordeiros do bar para evitar brigas. Eventualmente, você fica farto e decide tomar medidas preventivas.
Como sua cidade é pequena, você sabe exatamente quais pares de clientes provavelmente brigarão se acabarem juntos em um bar. Você tem uma lista de n pessoas que virão ao bar esta noite. Você decide manter algumas pessoas da cidade fora do bar sem que ninguém brigue. Ao mesmo tempo, os seus chefes não querem perder lucros e ficarão insatisfeitos se você não deixar mais do que k pessoas.
Infelizmente, o problema diante de você é um problema clássico NP-difícil. Você pode conhecê-la como , ou como um problema de cobertura de vértices. Para tais problemas, no caso geral, não existem algoritmos que funcionem em um tempo aceitável. Para ser mais preciso, a hipótese não comprovada e bastante forte ETH (Hipótese do Tempo Exponencial) diz que este problema não pode ser resolvido a tempo , isto é, você não consegue pensar em nada visivelmente melhor do que uma pesquisa completa. Por exemplo, digamos que alguém vá ao seu bar n = 1000 Humano. Então a pesquisa completa será opções que existem aproximadamente - quantidade absurda. Felizmente, sua gestão lhe deu um limite k = 10, então o número de combinações que você precisa iterar é muito menor: o número de subconjuntos de dez elementos é . Isso é melhor, mas ainda não será contado em um dia, mesmo em um cluster poderoso.
Para eliminar a possibilidade de briga nessa configuração de relações tensas entre os frequentadores do bar, é preciso manter Bob, Daniel e Fedor afastados. Não há solução em que apenas dois fiquem para trás.
Isso significa que é hora de ceder e deixar todos entrarem? Vamos considerar outras opções. Bem, por exemplo, você não pode deixar entrar apenas aqueles que provavelmente lutarão com um número muito grande de pessoas. Se alguém pode lutar pelo menos com k+1 outra pessoa, então você definitivamente não pode deixá-la entrar - caso contrário, você terá que manter todos fora k+1 cidadãos, com quem ele pode lutar, o que certamente perturbará a liderança.
Deixe você expulsar todos que puder de acordo com este princípio. Então todos os outros poderão lutar com não mais do que k pessoas. Jogando-os fora k cara, você não pode evitar nada mais do que conflitos. Isto significa que se houver mais de Se uma pessoa estiver envolvida em pelo menos um conflito, certamente não será possível evitar todos eles. Como, é claro, você definitivamente permitirá a entrada de pessoas completamente sem conflito, você precisa passar por todos os subconjuntos de tamanho dez em duzentas pessoas. Existem aproximadamente , e esse número de operações já pode ser resolvido no cluster.
Se você pode considerar com segurança indivíduos que não têm nenhum conflito, então o que dizer daqueles que participam de apenas um conflito? Na verdade, eles também podem entrar fechando a porta ao oponente. Na verdade, se Alice está em conflito apenas com Bob, então se deixarmos Alice fora dos dois, não perderemos: Bob pode ter outros conflitos, mas Alice certamente não os tem. Além disso, não faz sentido não deixarmos nós dois entrar. Depois de tais operações não resta mais convidados com um destino não resolvido: só temos conflitos, cada um com dois participantes e cada um envolvido em pelo menos dois. Então tudo o que resta é classificar opções, que podem facilmente ser consideradas meio dia em um laptop.
Na verdade, com um raciocínio simples você pode conseguir condições ainda mais atrativas. Observe que definitivamente precisamos resolver todas as disputas, ou seja, de cada par conflitante, escolher pelo menos uma pessoa que não deixaremos entrar. Vamos considerar o seguinte algoritmo: pegue qualquer conflito, do qual removemos um participante e iniciamos recursivamente do restante, depois removemos o outro e também iniciamos recursivamente. Como expulsamos alguém a cada passo, a árvore de recursão desse algoritmo é uma árvore binária de profundidade k, então no total o algoritmo funciona em Onde n é o número de vértices, e m - número de costelas. No nosso exemplo, são cerca de dez milhões, que podem ser calculados em uma fração de segundo não apenas em um laptop, mas até mesmo em um telefone celular.
O exemplo acima é um exemplo algoritmo parametrizado. Algoritmos parametrizados são algoritmos que rodam no tempo f(k) poli(n)Onde p - 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.
Todo o raciocínio antes deste algoritmo dá um exemplo kernelização é uma das técnicas gerais para criar algoritmos parametrizados. Kernelização é a redução do tamanho do problema a um valor limitado por uma função de um parâmetro. O problema resultante costuma ser chamado de kernel. Assim, por simples raciocínio sobre os graus dos vértices, obtivemos um kernel quadrático para o problema de Cobertura de Vértices, parametrizado pelo tamanho da resposta. Existem outras configurações que você pode escolher para esta tarefa (como Vertex Cover Above LP), mas esta é a configuração que discutiremos.
Desafio de ritmo
Concorrência (The Parameterized Algorithms and Computational Experiments Challenge) nasceu 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 a encontrar a largura da árvore de um gráfico (), procurando por uma árvore Steiner () e buscando um conjunto de vértices que corta ciclos (). Este ano, um dos problemas que você poderia tentar resolver foi o problema de cobertura de vértices descrito acima.
A competição está ganhando popularidade a cada ano. Se você acredita nos dados preliminares, este ano 24 equipes participaram da competição para resolver sozinhas o problema de cobertura de vértices. É importante destacar que a competição não dura várias horas ou mesmo uma semana, mas vários meses. As equipes têm a oportunidade de estudar a literatura, apresentar suas próprias ideias originais e tentar implementá-las. Em essência, esta competição é um projeto de pesquisa. Ideias para as soluções mais eficazes e premiação dos vencedores serão realizadas em conjunto com a conferência (Simpósio Internacional sobre Computação Parametrizada e Exata) como parte do maior encontro algorítmico anual da Europa . Informações mais detalhadas sobre a competição em si podem ser encontradas em , e os resultados dos anos anteriores estão .
Esquema de solução
Para resolver o problema de cobertura de vértices, tentei usar algoritmos parametrizados. Normalmente 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 o pré-processamento da entrada em tempo polinomial. O objetivo da aplicação de tais regras é reduzir o problema a um problema equivalente menor. As regras de simplificação são a parte mais cara do algoritmo e a aplicação desta parte leva ao tempo total de execução em vez de tempo polinomial simples. No nosso caso, as regras de divisão baseiam-se no fato de que para cada vértice é necessário tomá-lo ou seu vizinho como resposta.
O esquema geral é este: aplicamos as regras de simplificação, depois selecionamos algum vértice e fazemos duas chamadas recursivas: na primeira pegamos ele como resposta, e na outra pegamos todos os seus vizinhos. Isso é o que chamamos de divisão (ramificação) ao longo deste vértice.
Exatamente um acréscimo será feito a este esquema no próximo parágrafo.
Ideias para regras de divisão (brunch)
Vamos discutir como escolher um vértice ao longo do qual ocorrerá a divisão.
A ideia principal é muito gananciosa no sentido algorítmico: vamos pegar um vértice de grau máximo e dividir ao longo dele. Por que parece melhor? Porque no segundo ramo da chamada recursiva iremos remover muitos vértices desta forma. Você pode contar com um pequeno gráfico restante e podemos trabalhar nisso rapidamente.
Esta abordagem, com as técnicas simples de kernelização já discutidas, mostra-se bem e resolve alguns testes de vários milhares de vértices de tamanho. Mas, por exemplo, não funciona bem para grafos cúbicos (isto é, grafos cujo grau de cada vértice é três).
Há outra ideia baseada em uma ideia bastante simples: se o grafo estiver desconectado, o problema em seus componentes conectados pode ser resolvido de forma independente, combinando as respostas no final. Essa, aliás, é uma pequena modificação prometida no esquema, que irá agilizar significativamente a solução: anteriormente, neste caso, trabalhávamos pelo produto dos tempos para cálculo das respostas dos componentes, mas agora trabalhamos para a soma. E para acelerar a ramificação, você precisa transformar um gráfico conectado em um desconectado.
Como fazer isso? Se houver um ponto de articulação no gráfico, você precisará lutar contra ele. Um ponto de articulação é um vértice tal que, ao ser removido, o grafo perde sua conectividade. Todos os pontos de junção em um gráfico podem ser encontrados usando um algoritmo clássico em tempo linear. Essa abordagem acelera significativamente a ramificação.
Quando qualquer um dos vértices selecionados for removido, o gráfico será dividido em componentes conectados.
Faremos isso, mas queremos mais. Por exemplo, procure pequenos cortes de vértices no gráfico e divida-os ao longo dos vértices. A maneira mais eficiente que conheço para encontrar o corte global mínimo do vértice é usar uma árvore Gomori-Hu, que é construída em tempo cúbico. No PACE Challenge, o tamanho típico do gráfico é de vários milhares de vértices. Nesta situação, bilhões de operações precisam ser realizadas em cada vértice da árvore recursiva. Acontece que é simplesmente impossível resolver o problema no tempo previsto.
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 um fluxo máximo. Você pode deixá-lo entrar em tal rede , na prática funciona muito rapidamente. Suspeito que seja teoricamente possível comprovar uma estimativa para o tempo de operação , o que já é bastante aceitável.
Tentei várias vezes procurar cortes entre pares de vértices aleatórios e escolher o mais equilibrado. Infelizmente, isso produziu resultados ruins nos testes abertos do PACE Challenge. Comparei-o com um algoritmo que divide vértices de grau máximo, executando-os com uma limitação na profundidade de descida. Um algoritmo tentando encontrar um corte dessa forma deixou para trás gráficos maiores. Isso se deve ao fato de os cortes terem se revelado muito desequilibrados: após a remoção de 5 a 10 vértices, foi possível dividir apenas 15 a 20.
É importante notar que artigos sobre algoritmos teoricamente mais rápidos usam técnicas muito mais avançadas para selecionar vértices para divisão. Tais técnicas têm implementação muito complexa e muitas vezes baixo desempenho em termos de tempo e memória. Não consegui identificar aqueles que são bastante aceitáveis para a prática.
Como aplicar regras de simplificação
Já temos ideias para kernelização. Deixe-me lembrá-lo:
- Se houver um vértice isolado, exclua-o.
- Se houver um vértice de grau 1, remova-o e pegue seu vizinho como resposta.
- Se houver um vértice de grau pelo menos k+1, levá-lo de volta.
Com os dois primeiros tudo fica claro, com o terceiro há um truque. Se num problema cômico sobre um bar nos fosse dado um limite superior de k, então no PACE Challenge você só precisa encontrar uma cobertura de vértice de tamanho mínimo. Esta é uma transformação típica de Problemas de Pesquisa em Problemas de Decisão; muitas vezes não há diferença entre os dois tipos de problemas. Na prática, se estivermos escrevendo um solucionador para o problema de cobertura de vértices, pode haver uma diferença. Por exemplo, como no terceiro ponto.
Do ponto de vista da implementação, existem duas maneiras de proceder. A primeira abordagem é chamada de Aprofundamento Iterativo. É o seguinte: podemos começar com alguma restrição razoável de baixo para a resposta e então executar nosso algoritmo usando essa restrição como uma restrição para a resposta de cima, sem diminuir em recursão do que essa restrição. Se encontrarmos alguma resposta, é garantido que ela seja ótima; caso contrário, podemos aumentar esse limite em um e começar de novo.
Outra abordagem é armazenar alguma resposta ótima atual e procurar uma resposta menor, alterando esse parâmetro quando encontrado k para maior corte de galhos desnecessários na busca.
Depois de realizar vários experimentos noturnos, decidi por uma combinação desses dois métodos: primeiro, executo meu algoritmo com algum tipo de limite na profundidade da pesquisa (selecionando-o de forma que leve um tempo insignificante em comparação com a solução principal) e uso o melhor solução encontrada como limite superior para a resposta - isto é, para a mesma coisa k.
Vértices de grau 2
Lidamos com vértices de grau 0 e 1. Acontece que isso pode ser feito com vértices de grau 2, mas isso exigirá operações mais complexas do grafo.
Para explicar isso, precisamos designar de alguma forma os vértices. Vamos chamar um vértice de grau 2 de vértice v, e seus vizinhos - vértices x и y. A seguir teremos dois casos.
- Quando x и y - vizinhos. Então você pode responder x и yE v excluir. Na verdade, deste triângulo pelo menos dois vértices precisam ser tomados em troca, e definitivamente não perderemos se tomarmos x и y: eles provavelmente têm outros vizinhos, e v Eles não estão aqui.
- Quando x и y - não vizinhos. Então afirma-se que todos os três vértices podem ser colados em um. A ideia é que neste caso exista uma resposta ótima, na qual tomamos v, ou ambos os vértices x и y. Além disso, no primeiro caso teremos que aceitar todos os vizinhos em resposta x и y, mas no segundo não é necessário. Isso corresponde exatamente aos casos em que não pegamos o vértice colado em resposta e quando o fazemos. Resta apenas notar que em ambos os casos a resposta de tal operação diminui em um.
Vale a pena notar que esta abordagem é bastante difícil de implementar com precisão em um tempo linear justo. Colar vértices é uma operação complexa; você precisa copiar listas de vizinhos. Se isso for feito de maneira descuidada, você pode acabar com um tempo de execução assintoticamente abaixo do ideal (por exemplo, se você copiar muitas arestas após cada colagem). Decidi encontrar caminhos inteiros a partir de vértices de grau 2 e analisar vários casos especiais, como ciclos de tais vértices ou de todos esses vértices, exceto um.
Além disso, é necessário que esta operação seja reversível, para que ao retornar da recursão restauremos o gráfico à sua forma original. Para garantir isso, não limpei as listas de arestas dos vértices mesclados e apenas sabia quais arestas precisavam ir para onde. Esta implementação de gráficos também requer precisão, mas fornece um tempo linear justo. E para gráficos de várias dezenas de milhares de arestas, ele cabe no cache do processador, o que oferece grandes vantagens em velocidade.
Kernel linear
Finalmente, a parte mais interessante do kernel.
Para começar, lembre-se que em grafos bipartidos a cobertura mínima de vértices pode ser encontrada usando . Para fazer isso você precisa usar o algoritmo para encontrar a correspondência máxima e então usar o teorema .
A ideia de um kernel linear é esta: primeiro bifurcamos o gráfico, ou seja, em vez de cada vértice v vamos adicionar dois picos и , e em vez de cada aresta você - v vamos adicionar duas costelas и . O gráfico resultante será bipartido. Vamos encontrar a cobertura mínima de vértices nele. Alguns vértices do gráfico original chegarão lá duas vezes, alguns apenas uma vez e outros nunca. O teorema de Nemhauser-Trotter afirma que, neste caso, pode-se remover vértices que não atingiram nenhuma vez e recuperar aqueles que atingiram duas vezes. Além disso, ela diz que dos vértices restantes (aqueles que atingiram uma vez) você precisa pegar pelo menos metade como resposta.
Acabamos de aprender a não deixar mais do que 2k picos Na verdade, se a resposta restante for pelo menos metade de todos os vértices, então não há mais vértices no total do que 2k.
Aqui pude dar um pequeno passo em frente. É claro que o kernel construído desta forma depende do tipo de cobertura mínima de vértices que adotamos no grafo bipartido. Eu gostaria de escolher um para que o número de vértices restantes fosse mínimo. Anteriormente, eles só conseguiam fazer isso a tempo . Eu criei uma implementação desse algoritmo na época , assim, esse núcleo pode ser pesquisado em gráficos de centenas de milhares de vértices em cada estágio de ramificação.
resultado
A prática mostra que minha solução funciona bem em testes de centenas de vértices e milhares de arestas. Nesses testes é bem possível esperar que uma solução seja encontrada em meia hora. A probabilidade de encontrar uma resposta em um tempo aceitável, em princípio, aumenta se o gráfico tiver um número suficientemente grande de vértices de alto grau, por exemplo, grau 10 e superior.
Para participar no concurso as soluções tiveram que ser enviadas para . A julgar pelas informações ali apresentadas , minha solução em testes abertos ocupa o terceiro lugar entre vinte, com uma grande diferença em relação ao segundo lugar. Para ser totalmente honesto, não está totalmente claro como as soluções serão avaliadas na própria competição: por exemplo, a minha solução passa menos testes do que a solução do quarto lugar, mas nas que passam, funciona mais rápido.
Os resultados dos testes fechados serão conhecidos no dia XNUMXº de julho.
Fonte: habr.com