O traballo de investigación é quizais a parte máis interesante da nosa formación. A idea é probarte na túa dirección escollida mentres aínda estás na universidade. Por exemplo, os estudantes das áreas de Enxeñaría de Software e Machine Learning adoitan ir a investigar en empresas (principalmente JetBrains ou Yandex, pero non só).
Neste post falarei do meu proxecto en Informática. Como parte do meu traballo, estudei e puxen en práctica enfoques para resolver un dos problemas NP-hard máis famosos: problema de cobertura de vértices.
Hoxe en día, un enfoque interesante para problemas NP-hard está a desenvolverse moi rapidamente: algoritmos parametrizados. Tentarei poñerche ao día, contarche algúns algoritmos parametrizados sinxelos e describir un método poderoso que me axudou moito. Presentei os meus resultados no concurso PACE Challenge: segundo os resultados das probas abertas, a miña solución ocupa o terceiro lugar e os resultados finais coñeceranse o 1 de xullo.
Sobre min
Chámome Vasily Alferov, agora estou rematando o meu terceiro ano na Escola Superior de Economía da Universidade Nacional de Investigación - San Petersburgo. Interesáronme os algoritmos desde os meus tempos de escola, cando estudei na escola número 179 de Moscova e participei con éxito nas Olimpíadas de informática.
Un número finito de especialistas en algoritmos parametrizados entran na barra...
Exemplo tirado do libro
Imaxina que es un garda de seguridade do bar dunha cidade pequena. Todos os venres, a metade da cidade chega ao teu bar para relaxarte, o que che dá moitos problemas: tes que botar do bar aos clientes ruidosos para evitar pelexas. Finalmente, fartas e decides tomar medidas preventivas.
Dado que a túa cidade é pequena, sabes exactamente que parellas de clientes son susceptibles de loitar se acaban xuntos nun bar. Tes unha lista de n xente que virá ao bar esta noite. Decides manter a algúns veciños fóra do bar sen que ninguén se pele. Ao mesmo tempo, os teus xefes non queren perder beneficios e serán descontentos se non deixas máis de k persoas.
Desafortunadamente, o problema ante ti é un clásico problema NP-difícil. Podes coñecela como , ou como un problema de cobertura de vértices. Para tales problemas, no caso xeral, non hai algoritmos que funcionen nun tempo aceptable. Para ser precisos, a hipótese non comprobada e bastante forte ETH (Exponential Time Hypothesis) di que este problema non se pode resolver a tempo , é dicir, non se pode pensar en nada notablemente mellor que unha busca completa. Por exemplo, digamos que alguén vai vir ao teu bar n = 1000 Humano. Despois será a busca completa opcións que hai aproximadamente - cantidade tola. Afortunadamente, a súa xestión deulle un límite k = 10, polo que o número de combinacións que precisa iterar é moito menor: o número de subconxuntos de dez elementos é . Isto é mellor, pero aínda non se contará nun día nin sequera nun clúster potente.
Para eliminar a posibilidade dunha pelexa nesta configuración de relacións tensas entre os visitantes do bar, cómpre manter fóra a Bob, Daniel e Fedor. Non hai solución na que só queden dous atrás.
Significa isto que é hora de ceder e deixar entrar a todos? Consideremos outras opcións. Ben, por exemplo, non podes deixar entrar só aqueles que teñen probabilidades de loitar cun gran número de persoas. Se alguén pode loitar polo menos con k+1 outra persoa, entón definitivamente non podes deixala entrar; se non, terás que manter a todos fóra k+1 habitantes do pobo, cos que pode loitar, o que definitivamente alterará o liderado.
Permíteche botar fóra a todos os que puideses segundo este principio. Entón todos os demais poden loitar con non máis que k persoas. Botándoos fóra k home, non podes evitar nada máis que conflitos. Isto significa que se hai máis de Se unha persoa está involucrada en polo menos un conflito, entón certamente non pode evitalos todos. Xa que, por suposto, deixarás entrar persoas completamente sen conflitos, tes que pasar por todos os subconxuntos de tamaño dez de cada duascentas persoas. Hai aproximadamente , e este número de operacións xa se pode resolver no clúster.
Se podes levar con seguridade a persoas que non teñen ningún conflito, que pasa cos que só participan nun conflito? De feito, tamén se poden deixar entrar pechando a porta ao seu opoñente. De feito, se Alicia está en conflito só con Bob, entón se deixamos a Alicia fóra dos dous, non perderemos: Bob pode ter outros conflitos, pero Alicia certamente non os ten. Ademais, non ten sentido que non nos deixemos entrar os dous. Despois de tales operacións non queda máis hóspedes cun destino sen resolver: só temos conflitos, cada un con dous participantes e cada un implicado en polo menos dous. Polo tanto, só queda resolver opcións, que se poden considerar facilmente medio día nun portátil.
De feito, cun razoamento sinxelo pódese conseguir condicións aínda máis atractivas. Teña en conta que definitivamente temos que resolver todas as disputas, é dicir, de cada parella en conflito, escoller polo menos unha persoa á que non deixaremos entrar. Consideremos o seguinte algoritmo: tome calquera conflito, do que eliminamos un participante e comezamos recursivamente polo resto, despois eliminamos o outro e tamén comezamos recursivamente. Xa que botamos a alguén fóra a cada paso, a árbore de recursividade deste algoritmo é unha árbore binaria de profundidade k, polo que en total o algoritmo funciona onde n é o número de vértices, e m - número de costelas. No noso exemplo, trátase duns dez millóns, que se poden calcular nunha fracción de segundo non só nun portátil, senón mesmo nun teléfono móbil.
O exemplo anterior é un exemplo algoritmo parametrizado. Os algoritmos parametrizados son algoritmos que se executan no tempo f(k) poli(n)onde p - polinomio, f é unha función computable arbitraria, e k - algún parámetro, que, moi posiblemente, será moito menor que o tamaño do problema.
Todos os razoamentos anteriores a este algoritmo dan un exemplo kernelización é unha das técnicas xerais para a creación de algoritmos parametrizados. A kernelización é a redución do tamaño do problema a un valor limitado por unha función dun parámetro. O problema resultante adoita chamarse núcleo. Así, mediante un simple razoamento sobre os graos dos vértices, obtivemos un núcleo cuadrático para o problema Vertex Cover, parametrizado polo tamaño da resposta. Hai outras opcións que podes escoller para esta tarefa (como Vertex Cover Above LP), pero esta é a configuración que comentaremos.
Desafío de ritmo
Competición (The Parameterized Algorithms and Computational Experiments Challenge) naceu en 2015 para establecer unha conexión entre algoritmos parametrizados e enfoques utilizados na práctica para resolver problemas computacionais. Os tres primeiros concursos dedicáronse a atopar o ancho da árbore dun gráfico (), buscando unha árbore Steiner () e buscar un conxunto de vértices que corta os ciclos (). Este ano, un dos problemas nos que poderías probar a túa man foi o problema de cuberta de vértices descrito anteriormente.
A competición está gañando popularidade cada ano. Se cres os datos preliminares, este ano participaron 24 equipos na competición para resolver só o problema de cuberta de vértices. Cabe destacar que a competición non dura varias horas nin sequera unha semana, senón varios meses. Os equipos teñen a oportunidade de estudar a literatura, elaborar a súa propia idea orixinal e tentar poñela en práctica. En esencia, este concurso é un proxecto de investigación. As ideas para as solucións máis eficaces e a concesión dos gañadores realizaranse en conxunto coa conferencia (International Symposium on Parameterized and Exact Computation) como parte da maior reunión algorítmica anual de Europa . Pódese atopar información máis detallada sobre o propio concurso en , e os resultados de anos anteriores menten .
Diagrama de solución
Para resolver o problema de cobertura de vértices, intentei usar algoritmos parametrizados. Normalmente constan de dúas partes: regras de simplificación (que idealmente conducen á kernelización) e regras de división. As regras de simplificación son o preprocesamento da entrada en tempo polinómico. O propósito de aplicar tales regras é reducir o problema a un problema menor equivalente. As regras de simplificación son a parte máis cara do algoritmo, e a aplicación desta parte leva ao tempo total de execución. en lugar de tempo polinómico simple. No noso caso, as regras de división baséanse no feito de que para cada vértice cómpre tomar a el ou o seu veciño como resposta.
O esquema xeral é este: aplicamos as regras de simplificación, despois seleccionamos algún vértice e facemos dúas chamadas recursivas: na primeira tomamos como resposta e na outra tomamos todos os seus veciños. Isto é o que chamamos división (ramificación) ao longo deste vértice.
No seguinte parágrafo farase exactamente unha adición a este esquema.
Ideas para dividir (brunching) regras
Imos discutir como escoller un vértice ao longo do cal se producirá a división.
A idea principal é moi cobizosa no sentido algorítmico: tomemos un vértice de grao máximo e dividimos ao longo del. Por que parece mellor? Porque na segunda rama da chamada recursiva eliminaremos moitos vértices deste xeito. Podes contar cun pequeno gráfico restante e podemos traballar nel rapidamente.
Este enfoque, coas técnicas simples de kernelización xa comentadas, móstrase ben e resolve algunhas probas de varios miles de vértices de tamaño. Pero, por exemplo, non funciona ben para gráficos cúbicos (é dicir, gráficos cuxo grao de cada vértice é tres).
Hai outra idea baseada nunha idea bastante sinxela: se a gráfica está desconectada, o problema dos seus compoñentes conectados pódese resolver de forma independente, combinando as respostas ao final. Esta, por certo, é unha pequena modificación prometida no esquema, que acelerará significativamente a solución: anteriormente, neste caso, traballabamos para o produto dos tempos para calcular as respostas dos compoñentes, pero agora traballamos para a suma. E para acelerar a ramificación, cómpre converter un gráfico conectado nun desconectado.
Como facelo? Se hai un punto de articulación no gráfico, debes loitar contra el. Un punto de articulación é un vértice tal que cando se elimina, o gráfico perde a súa conectividade. Todos os puntos de unión dun gráfico pódense atopar usando un algoritmo clásico en tempo lineal. Este enfoque acelera significativamente a ramificación.
Cando se elimina algún dos vértices seleccionados, o gráfico dividirase en compoñentes conectados.
Farémolo, pero queremos máis. Por exemplo, busque pequenos cortes de vértice no gráfico e divídese ao longo dos vértices a partir del. A forma máis eficiente que coñezo de atopar o corte de vértice global mínimo é usar unha árbore Gomori-Hu, que está construída en tempo cúbico. No desafío PACE, o tamaño típico do gráfico é de varios miles de vértices. Nesta situación, hai que realizar miles de millóns de operacións en cada vértice da árbore de recursividade. Acontece que é simplemente imposible resolver o problema no tempo previsto.
Intentemos optimizar a solución. O corte de vértice mínimo entre un par de vértices pódese atopar mediante calquera algoritmo que constrúa un fluxo máximo. Podes deixalo a unha rede deste tipo , na práctica funciona moi rápido. Teño a sospeita de que teoricamente é posible probar unha estimación do tempo de funcionamento , que xa é bastante aceptable.
Intentei varias veces buscar cortes entre pares de vértices aleatorios e tomar o máis equilibrado. Desafortunadamente, isto deu malos resultados nas probas abertas de PACE Challenge. Compareino cun algoritmo que divide vértices de grao máximo, executándoos cunha limitación na profundidade de descenso. Un algoritmo que intentaba atopar un corte deste xeito deixou atrás gráficos máis grandes. Isto débese ao feito de que os cortes resultaron moi desequilibrados: despois de eliminar 5-10 vértices, foi posible dividir só 15-20.
Paga a pena sinalar que os artigos sobre os algoritmos teoricamente máis rápidos usan técnicas moito máis avanzadas para seleccionar vértices para dividir. Tales técnicas teñen unha implementación moi complexa e moitas veces un rendemento pobre en termos de tempo e memoria. Non puiden identificar aqueles que son bastante aceptables para a práctica.
Como aplicar as regras de simplificación
Xa temos ideas para a kernelización. Permíteme recordarche:
- Se hai un vértice illado, elimínao.
- Se hai un vértice de grao 1, elimínao e toma o seu veciño como resposta.
- Se hai un vértice de grao polo menos k+1, tómao de volta.
Cos dous primeiros está todo claro, co terceiro hai un truco. Se nun problema cómico sobre un bar nos deron un límite superior de k, entón no Desafío PACE só tes que atopar unha tapa de vértice do tamaño mínimo. Esta é unha transformación típica dos problemas de busca en problemas de decisión; moitas veces non hai diferenzas entre os dous tipos de problemas. Na práctica, se estamos escribindo un solucionador para o problema de cobertura de vértices, pode haber unha diferenza. Por exemplo, como no terceiro punto.
Desde o punto de vista da implementación, hai dúas formas de proceder. O primeiro enfoque chámase profundización iterativa. É o seguinte: podemos comezar con algunha restrición razoable desde abaixo na resposta e, a continuación, executar o noso algoritmo usando esta restrición como unha restrición na resposta desde arriba, sen baixar en recursividade que esta restrición. Se atopamos algunha resposta, está garantido que é a óptima, se non, podemos aumentar este límite nun e comezar de novo.
Outro enfoque é almacenar algunha resposta óptima actual e buscar unha resposta máis pequena, cambiando este parámetro cando se atope k para un maior corte de ramas innecesarias na busca.
Despois de realizar varios experimentos nocturnos, decidín unha combinación destes dous métodos: primeiro, executo o meu algoritmo con algún tipo de límite na profundidade de busca (seleccionándoo de xeito que leva un tempo insignificante en comparación coa solución principal) e uso o mellor. solución atopada como límite superior á resposta, é dicir, á mesma cousa k.
Vértices de grao 2
Tratamos os vértices de grao 0 e 1. Resulta que isto pódese facer con vértices de grao 2, pero isto requirirá operacións máis complexas do gráfico.
Para explicar isto, necesitamos designar dalgún xeito os vértices. Chamemos vértice a un vértice de grao 2 v, e os seus veciños - vértices x и y. A continuación teremos dous casos.
- Cando x и y - veciños. Entón podes responder x и yE v eliminar. De feito, deste triángulo hai que tomar polo menos dous vértices a cambio, e definitivamente non perderemos se tomamos x и y: probablemente teñan outros veciños, e v Non están aquí.
- Cando x и y -non veciños. Entón indícase que os tres vértices poden pegarse nun. A idea é que neste caso haxa unha resposta óptima, na que tomamos calquera das dúas v, ou os dous vértices x и y. Ademais, no primeiro caso teremos que levar a todos os veciños como resposta x и y, pero no segundo non é necesario. Isto correspóndese exactamente cos casos nos que non tomamos o vértice pegado en resposta e cando o facemos. Só queda notar que en ambos os casos a resposta de tal operación diminúe nun.
Paga a pena notar que este enfoque é bastante difícil de implementar con precisión nun tempo lineal xusto. Pegar vértices é unha operación complexa; cómpre copiar listas de veciños. Se isto se fai sen coidado, podes ter un tempo de execución asintóticamente subóptimo (por exemplo, se copias moitos bordos despois de cada pegado). Decidín buscar camiños enteiros a partir de vértices de grao 2 e analizar unha morea de casos especiais, como ciclos a partir de tales vértices ou de todos os devanditos vértices excepto un.
Ademais, cómpre que esta operación sexa reversible, para que ao volver da recursividade recuperemos o gráfico á súa forma orixinal. Para garantir isto, non limpei as listas de bordos dos vértices combinados, e entón só sabía que bordos debían ir onde. Esta implementación de gráficos tamén require precisión, pero proporciona un tempo lineal xusto. E para gráficos de varias decenas de miles de bordos, encaixa na caché do procesador, o que dá grandes vantaxes na velocidade.
Núcleo lineal
Finalmente, a parte máis interesante do núcleo.
Para comezar, lembre que nos gráficos bipartitos pódese atopar a cobertura mínima de vértices usando . Para iso cómpre usar o algoritmo para atopar alí a máxima coincidencia e, a continuación, use o teorema .
A idea dun núcleo lineal é esta: primeiro bifurcamos o gráfico, é dicir, en lugar de cada vértice v imos engadir dous picos и , e no canto de cada bordo u - v imos engadir dúas costelas и . O gráfico resultante será bipartito. Atopemos nela a cobertura mínima de vértices. Algúns vértices do gráfico orixinal chegarán alí dúas veces, algúns só unha e outros nunca. O teorema de Nemhauser-Trotter afirma que neste caso pódese eliminar os vértices que non golpearon nin unha vez e recuperar os que golpearon dúas veces. Ademais, di que dos vértices restantes (os que golpean unha vez) cómpre tomar polo menos a metade como resposta.
Acabamos de aprender a deixar máis que 2k picos De feito, se a resposta restante é polo menos a metade de todos os vértices, entón non hai máis vértices en total que 2k.
Aquí puiden dar un pequeno paso adiante. Está claro que o núcleo construído deste xeito depende do tipo de cobertura mínima de vértices que tomamos no gráfico bipartito. Gustaríame tomar un para que o número de vértices restantes sexa mínimo. Anteriormente, só podían facelo a tempo . Ocorreu unha implementación deste algoritmo no tempo , así, este núcleo pódese buscar en gráficos de centos de miles de vértices en cada etapa de ramificación.
Resultado
A práctica demostra que a miña solución funciona ben en probas de varios centos de vértices e varios miles de arestas. En tales probas é moi posible esperar que se atope unha solución en media hora. A probabilidade de atopar unha resposta nun tempo aceptable, en principio, aumenta se a gráfica ten un número suficientemente grande de vértices de grao alto, por exemplo, grao 10 e superior.
Para participar no concurso houbo que enviar solucións a . A xulgar pola información alí presentada , a miña solución en probas abertas ocupa o terceiro lugar de vinte, cunha gran diferenza respecto ao segundo. Para ser completamente honesto, non está do todo claro como se avaliarán as solucións no propio concurso: por exemplo, a miña solución pasa menos probas que a solución en cuarto lugar, pero nas que aproban, funciona máis rápido.
Os resultados das probas pechadas coñeceranse o XNUMX de xullo.
Fonte: www.habr.com