El trabajo de investigación es quizás la parte más interesante de nuestra formación. La idea es esforzarse en la dirección elegida mientras aún está en la universidad. Por ejemplo, los estudiantes de las áreas de Ingeniería de Software y Machine Learning suelen ir a realizar investigaciones en empresas (principalmente JetBrains o Yandex, pero no solo).
En este post hablaré de mi proyecto en Informática. Como parte de mi trabajo, estudié y puse en práctica enfoques para resolver uno de los problemas NP-difíciles más famosos: problema de cobertura de vértices.
Hoy en día, se está desarrollando muy rápidamente un enfoque interesante para los problemas NP-difíciles: los algoritmos parametrizados. Intentaré ponerte al día, contarte algunos algoritmos parametrizados simples y describir un método poderoso que me ayudó mucho. Presenté mis resultados en el concurso PACE Challenge: según los resultados de las pruebas abiertas, mi solución ocupa el tercer lugar y los resultados finales se conocerán el 1 de julio.
Acerca de mí
Mi nombre es Vasily Alferov, estoy terminando mi tercer año en la Escuela Superior de Economía de la Universidad Nacional de Investigación - San Petersburgo. Me interesan los algoritmos desde mi época escolar, cuando estudiaba en la escuela número 179 de Moscú y participaba con éxito en las Olimpiadas de informática.
Un número finito de especialistas en algoritmos parametrizados entran en el bar...
Ejemplo tomado del libro.
Imagina que eres guardia de seguridad de un bar en un pueblo pequeño. Cada viernes, media ciudad viene a tu bar para relajarse, lo que te da muchos problemas: tienes que echar a los clientes alborotadores del bar para evitar peleas. Al final te cansas y decides tomar medidas preventivas.
Como tu ciudad es pequeña, sabes exactamente qué parejas de clientes probablemente se pelearán si terminan juntos en un bar. ¿Tiene una lista de n personas que vendrán al bar esta noche. Decides mantener a algunos habitantes fuera del bar sin que nadie se pelee. Al mismo tiempo, sus jefes no quieren perder ganancias y no estarán contentos si no dejan que más de k personas.
Desafortunadamente, el problema que tienes ante ti es un clásico problema NP-difícil. Quizás la conozcas como , o como un problema de cobertura de vértices. Para este tipo de problemas, en el caso general, no existen algoritmos que funcionen en un tiempo aceptable. Para ser precisos, la hipótesis no probada y bastante sólida ETH (Hipótesis del tiempo exponencial) dice que este problema no se puede resolver a tiempo. 
, es decir, no se te ocurre nada notablemente mejor que una búsqueda completa. Por ejemplo, digamos que alguien va a venir a tu bar. n = 1000 Humano. Entonces la búsqueda completa será 
opciones que hay aproximadamente 
- cantidad loca. Afortunadamente, tu gestión te ha puesto un límite. k = 10, por lo que el número de combinaciones que necesitas iterar es mucho menor: el número de subconjuntos de diez elementos es 
. Esto es mejor, pero aún así no se contará en un día, ni siquiera en un clúster potente.
Para eliminar la posibilidad de una pelea en esta configuración de relaciones tensas entre los visitantes del bar, debes mantener alejados a Bob, Daniel y Fedor. No hay solución en la que sólo dos queden atrás.
¿Significa esto que es hora de ceder y dejar entrar a todos? Consideremos otras opciones. Bueno, por ejemplo, no puedes dejar entrar solo a aquellos que probablemente pelearán con un gran número de personas. Si alguien puede luchar al menos con k+1 otra persona, entonces definitivamente no puedes dejarla entrar; de lo contrario, tendrás que mantener a todos fuera. k+1 gente del pueblo, con quien puede pelear, lo que definitivamente molestará al liderazgo.
Permítete expulsar a todos los que puedas según este principio. Entonces todos los demás podrán luchar con no más de k gente. echándolos k hombre, no puedes evitar nada más que 
conflictos. Esto significa que si hay más de 
Si una persona está involucrada en al menos un conflicto, entonces ciertamente no se pueden prevenir todos. Dado que, por supuesto, definitivamente dejará entrar a personas que no tienen ningún conflicto, debe revisar todos los subconjuntos de tamaño diez de doscientas personas. Hay aproximadamente 
, y esta cantidad de operaciones ya se puede ordenar en el clúster.
Si se puede tomar con seguridad a individuos que no tienen ningún conflicto en absoluto, ¿qué pasa entonces con aquellos que participan en un solo conflicto? De hecho, también se les puede dejar entrar cerrando la puerta a su oponente. De hecho, si Alice está en conflicto sólo con Bob, entonces si dejamos que Alice salga de ellos dos, no perderemos: Bob puede tener otros conflictos, pero Alice ciertamente no los tiene. Además, no tiene sentido para nosotros no dejarnos entrar a los dos. Después de tales operaciones no queda más 
invitados con un destino no resuelto: solo tenemos 
conflictos, cada uno con dos participantes y cada uno involucrado en al menos dos. Así que sólo queda ordenar 
opciones, que fácilmente pueden considerarse medio día en una computadora portátil.
De hecho, con un simple razonamiento se pueden conseguir condiciones aún más atractivas. Tenga en cuenta que definitivamente debemos resolver todas las disputas, es decir, de cada par en conflicto, elegir al menos una persona a quien no dejaremos entrar. Consideremos el siguiente algoritmo: tomamos cualquier conflicto, del cual eliminamos a un participante y comenzamos recursivamente desde el resto, luego eliminamos el otro y también comenzamos recursivamente. Dado que expulsamos a alguien en cada paso, el árbol de recursividad de dicho algoritmo es un árbol binario de profundidad. k, por lo que en total el algoritmo funciona en 
Donde n es el número de vértices, y m - número de costillas. En nuestro ejemplo, se trata de unos diez millones, que se pueden calcular en una fracción de segundo no sólo en un ordenador portátil, sino también en un teléfono móvil.
El ejemplo anterior es un ejemplo. algoritmo parametrizado. Los algoritmos parametrizados son algoritmos que se ejecutan en el tiempo. f(k) poli(n)Donde p - polinomio, f es una función computable arbitraria, y k - algún parámetro que, muy posiblemente, será mucho menor que el tamaño del problema.
Todo el razonamiento antes de este algoritmo da un ejemplo. kernelización es una de las técnicas generales para crear algoritmos parametrizados. La kernelización es la reducción del tamaño del problema a un valor limitado por la función de un parámetro. El problema resultante suele denominarse núcleo. Así, mediante un simple razonamiento sobre los grados de los vértices, obtuvimos un núcleo cuadrático para el problema Vertex Cover, parametrizado por el tamaño de la respuesta. Hay otras configuraciones que puede elegir para esta tarea (como Vertex Cover Above LP), pero esta es la configuración que discutiremos.
Desafío de ritmo
La competencia (The Parameterized Algorithms and Computational Experiments Challenge) nació en 2015 para establecer una conexión entre los algoritmos parametrizados y los enfoques utilizados en la práctica para resolver problemas computacionales. Los primeros tres concursos se dedicaron a encontrar el ancho del árbol de un gráfico (), buscando un árbol Steiner () y buscando un conjunto de vértices que corte ciclos (). Este año, uno de los problemas en los que pudiste probar fue el problema de cobertura de vértices descrito anteriormente.
La competencia está ganando popularidad cada año. Si nos fijamos en los datos preliminares, este año 24 equipos participaron en el concurso para resolver solos el problema de cubrir los vértices. Vale la pena señalar que la competencia no dura unas horas o incluso una semana, sino varios meses. Los equipos tienen la oportunidad de estudiar la literatura, proponer su propia idea original e intentar implementarla. En esencia, este concurso es un proyecto de investigación. Junto con la conferencia se llevarán a cabo ideas sobre las soluciones más efectivas y la premiación de los ganadores. (Simposio Internacional sobre Computación Parametrizada y Exacta) como parte de la reunión algorítmica anual más grande de Europa . Puede encontrar información más detallada sobre el concurso en sí en , y los resultados de años anteriores mienten .
Esquema de solución
Para resolver el problema de la cobertura de vértices, intenté utilizar algoritmos parametrizados. Por lo general, constan de dos partes: reglas de simplificación (que idealmente conducen a la kernelización) y reglas de división. Las reglas de simplificación son el preprocesamiento de la entrada en tiempo polinómico. El propósito de aplicar tales reglas es reducir el problema a un problema equivalente más pequeño. Las reglas de simplificación son la parte más costosa del algoritmo y la aplicación de esta parte conduce al tiempo total de ejecución. 
en lugar de tiempo polinómico simple. En nuestro caso, las reglas de división se basan en el hecho de que para cada vértice es necesario tomarlo o su vecino como respuesta.
El esquema general es el siguiente: aplicamos las reglas de simplificación, luego seleccionamos algún vértice y hacemos dos llamadas recursivas: en la primera lo tomamos en respuesta y en la otra tomamos todos sus vecinos. Esto es lo que llamamos división (ramificación) a lo largo de este vértice.
En el siguiente párrafo se hará exactamente una adición a este esquema.
Ideas para dividir (brunch) reglas
Analicemos cómo elegir un vértice a lo largo del cual se producirá la división.
La idea principal es muy codiciosa en el sentido algorítmico: tomemos un vértice de grado máximo y dividámoslo a lo largo de él. ¿Por qué parece mejor? Porque en la segunda rama de la llamada recursiva eliminaremos muchos vértices de esta manera. Puede contar con un pequeño gráfico restante y podremos trabajar en él rápidamente.
Este enfoque, con las técnicas simples de kernelización ya discutidas, se muestra bien y resuelve algunas pruebas de varios miles de vértices. Pero, por ejemplo, no funciona bien para gráficas cúbicas (es decir, gráficas cuyo grado de cada vértice es tres).
Hay otra idea basada en una idea bastante simple: si el gráfico está desconectado, el problema de sus componentes conectados se puede resolver de forma independiente, combinando las respuestas al final. Esta, por cierto, es una pequeña modificación prometida en el esquema, que acelerará significativamente la solución: anteriormente, en este caso, trabajábamos por el producto de los tiempos para calcular las respuestas de los componentes, pero ahora trabajamos por la suma. Y para acelerar la ramificación, es necesario convertir un gráfico conectado en uno desconectado.
¿Cómo hacerlo? Si hay un punto de articulación en el gráfico, debes luchar por él. Un punto de articulación es un vértice tal que cuando se elimina, el gráfico pierde su conectividad. Todos los puntos de unión de un gráfico se pueden encontrar utilizando un algoritmo clásico en tiempo lineal. Este enfoque acelera significativamente la ramificación.
Cuando se elimina cualquiera de los vértices seleccionados, el gráfico se dividirá en componentes conectados.
Haremos esto, pero queremos más. Por ejemplo, busque pequeños cortes de vértices en el gráfico y divídalos a lo largo de los vértices. La forma más eficaz que conozco de encontrar el corte de vértice global mínimo es utilizar un árbol Gomori-Hu, que se construye en tiempo cúbico. En el PACE Challenge, el tamaño típico del gráfico es de varios miles de vértices. En esta situación, es necesario realizar miles de millones de operaciones en cada vértice del árbol de recursividad. Resulta que es simplemente imposible resolver el problema en el tiempo asignado.
Intentemos optimizar la solución. El corte de vértice mínimo entre un par de vértices se puede encontrar mediante cualquier algoritmo que construya un flujo máximo. Puedes dejarlo entrar en dicha red. , en la práctica funciona muy rápidamente. Tengo la sospecha de que teóricamente es posible probar una estimación del tiempo de funcionamiento. 
, lo cual ya es bastante aceptable.
Intenté varias veces buscar cortes entre pares de vértices aleatorios y tomar el más equilibrado. Desafortunadamente, esto produjo malos resultados en las pruebas abiertas del PACE Challenge. Lo comparé con un algoritmo que divide los vértices de grado máximo, ejecutándolos con una limitación en la profundidad de descenso. Un algoritmo que intentaba encontrar un corte de esta manera dejó gráficos más grandes. Esto se debe al hecho de que los cortes resultaron estar muy desequilibrados: después de eliminar de 5 a 10 vértices, solo fue posible dividir de 15 a 20.
Vale la pena señalar que los artículos sobre los algoritmos teóricamente más rápidos utilizan técnicas mucho más avanzadas para seleccionar los vértices para dividir. Estas técnicas tienen una implementación muy compleja y, a menudo, un rendimiento deficiente en términos de tiempo y memoria. No pude identificar aquellos que son bastante aceptables para la práctica.
Cómo aplicar reglas de simplificación
Ya tenemos ideas para la kernelización. Déjame recordarte:
- Si hay un vértice aislado, elimínelo.
- Si hay un vértice de grado 1, elimínelo y tome su vecino como respuesta.
- Si hay un vértice de grado al menos k+1, tomar de nuevo.
Con los dos primeros todo está claro, con el tercero hay un truco. Si en un problema cómico sobre una barra nos dieran un límite superior de k, luego en el Desafío PACE solo necesitas encontrar una cobertura de vértice del tamaño mínimo. Esta es una transformación típica de problemas de búsqueda en problemas de decisión; a menudo no hay diferencia entre los dos tipos de problemas. En la práctica, si escribimos un solucionador para el problema de cobertura de vértices, puede haber una diferencia. Por ejemplo, como en el tercer punto.
Desde el punto de vista de la implementación, hay dos maneras de proceder. El primer enfoque se llama Profundización Iterativa. Es el siguiente: podemos comenzar con alguna restricción razonable desde abajo en la respuesta y luego ejecutar nuestro algoritmo usando esta restricción como una restricción en la respuesta desde arriba, sin bajar la recursividad a esta restricción. Si hemos encontrado alguna respuesta, se garantiza que será óptima; de lo contrario, podemos aumentar este límite en uno y empezar de nuevo.
Otro enfoque es almacenar alguna respuesta óptima actual y buscar una respuesta más pequeña, cambiando este parámetro cuando se encuentre. k para un mayor corte de ramas innecesarias en la búsqueda.
Después de realizar varios experimentos nocturnos, me decidí por una combinación de estos dos métodos: primero, ejecuto mi algoritmo con algún tipo de límite en la profundidad de búsqueda (seleccionándolo para que tome un tiempo insignificante en comparación con la solución principal) y uso el mejor solución encontrada como límite superior de la respuesta, es decir, de la misma cosa k.
Vértices de grado 2
Hemos tratado con vértices de grado 0 y 1. Resulta que esto se puede hacer con vértices de grado 2, pero esto requerirá operaciones más complejas del gráfico.
Para explicar esto, necesitamos designar de alguna manera los vértices. Llamemos vértice a un vértice de grado 2 v, y sus vecinos - vértices x и y. A continuación tendremos dos casos.
- ¿Cuándo x и y - vecinos. Entonces puedes responder x и yY v borrar. De hecho, de este triángulo es necesario tomar al menos dos vértices a cambio, y definitivamente no perderemos si tomamos x и y: probablemente tengan otros vecinos, y v No lo son.
- ¿Cuándo x и y - no vecinos. Luego se afirma que los tres vértices se pueden pegar en uno. La idea es que en este caso hay una respuesta óptima, en la que tomamos v, o ambos vértices x и y. Además, en el primer caso tendremos que tomar a todos los vecinos en respuesta. x и y, pero en el segundo no es necesario. Esto corresponde exactamente a los casos en los que no tomamos el vértice pegado en respuesta y cuando lo hacemos. Sólo queda señalar que en ambos casos la respuesta a dicha operación se reduce en uno.
Vale la pena señalar que este enfoque es bastante difícil de implementar con precisión en un tiempo lineal justo. Pegar vértices es una operación compleja; es necesario copiar listas de vecinos. Si esto se hace sin cuidado, puede terminar con un tiempo de ejecución asintóticamente subóptimo (por ejemplo, si copia muchos bordes después de cada pegado). Me decidí por encontrar caminos completos desde los vértices de grado 2 y analizar un montón de casos especiales, como ciclos desde dichos vértices o desde todos los vértices excepto uno.
Además, es necesario que esta operación sea reversible, de manera que al regresar de la recursividad restablezcamos el gráfico a su forma original. Para garantizar esto, no borré las listas de aristas de los vértices fusionados, y luego simplemente supe qué aristas debían ir a dónde. Esta implementación de gráficos también requiere precisión, pero proporciona un tiempo lineal justo. Y para gráficos de varias decenas de miles de aristas, cabe en la memoria caché del procesador, lo que proporciona grandes ventajas en velocidad.
núcleo lineal
Finalmente, la parte más interesante del kernel.
Para empezar, recuerde que en gráficos bipartitos la cobertura mínima de vértices se puede encontrar usando 
. Para hacer esto necesitas usar el algoritmo. para encontrar la coincidencia máxima allí, y luego usar el teorema .
La idea de un núcleo lineal es la siguiente: primero bifurcamos el gráfico, es decir, en lugar de cada vértice v agreguemos dos picos 
и 
, y en lugar de cada borde u-v agreguemos dos costillas 
и 
. El gráfico resultante será bipartito. Encontremos la cobertura mínima de vértices en él. Algunos vértices del gráfico original llegarán allí dos veces, otros solo una vez y otros nunca. El teorema de Nemhauser-Trotter establece que en este caso se pueden eliminar los vértices que no tocaron ni una sola vez y recuperar los que tocaron dos veces. Además, dice que de los vértices restantes (los que golpean una vez) es necesario tomar al menos la mitad como respuesta.
Acabamos de aprender a no dejar más que 2k picos De hecho, si la respuesta restante es al menos la mitad de todos los vértices, entonces no hay más vértices en total que 2k.
Aquí pude dar un pequeño paso adelante. Está claro que el núcleo construido de esta manera depende de qué tipo de cobertura mínima de vértices tomamos en el gráfico bipartito. Me gustaría tomar uno para que el número de vértices restantes sea mínimo. Antes solo podían hacerlo a tiempo. 
. Se me ocurrió una implementación de este algoritmo en el tiempo 
Por tanto, este núcleo se puede buscar en gráficos de cientos de miles de vértices en cada etapa de ramificación.
resultado
La práctica demuestra que mi solución funciona bien en pruebas de varios cientos de vértices y varios miles de aristas. En tales pruebas es muy posible esperar que se encuentre una solución en media hora. La probabilidad de encontrar una respuesta en un tiempo aceptable, en principio, aumenta si el gráfico tiene un número suficientemente grande de vértices de alto grado, por ejemplo, grado 10 y superior.
Para participar en el concurso era necesario enviar las soluciones a . A juzgar por la información allí presentada. , mi solución en las pruebas abiertas ocupa el tercer lugar entre veinte, con una gran diferencia con respecto al segundo. Para ser completamente honesto, no está del todo claro cómo se evaluarán las soluciones en la competencia: por ejemplo, mi solución pasa menos pruebas que la solución que ocupa el cuarto lugar, pero las que pasan, funciona más rápido.
Los resultados de las pruebas cerradas se conocerán el XNUMX de julio.
Fuente: habr.com
