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

El trabajo de investigaci\u00f3n es, sin duda, la parte m\u00e1s interesante de nuestra formaci\u00f3n. La idea es que, incluso durante la universidad, podamos probar nuestro rumbo elegido. Por ejemplo, los estudiantes de las especialidades de Ingenier\u00eda de Software y Aprendizaje Autom\u00e1tico a menudo llevan a cabo proyectos de investigaci\u00f3n en empresas (principalmente JetBrains o Yandex, pero no solo).<\/p>\n

En este post, hablar\u00e9 sobre mi proyecto en el \u00e1mbito de la Inform\u00e1tica. En el transcurso de este trabajo, estudi\u00e9 e implement\u00e9 en la pr\u00e1ctica enfoques para resolver uno de los problemas NP-duros m\u00e1s conocidos: el problema de la cobertura de v\u00e9rtices<\/b>.<\/p>\n

Actualmente, se est\u00e1 desarrollando r\u00e1pidamente un enfoque interesante hacia los problemas NP-duros: los algoritmos parametrizados. Intentar\u00e9 ponerte al tanto, presentar algunos algoritmos parametrizados simples y describir un poderoso m\u00e9todo que me fue de gran ayuda. Present\u00e9 mis resultados en la competencia PACE Challenge: tras las pruebas abiertas, mi soluci\u00f3n ocupa el tercer lugar, y los resultados finales se dar\u00e1n a conocer el 1 de julio.<\/p>\n

\"C\u00f3mo
\n<\/a><\/noindex><\/p>\n

Acerca de m\u00ed<\/h3>\n

Me llamo Vasily Alfyorov, estoy finalizando el tercer curso en la HSE de San Petersburgo. Me apasionan los algoritmos desde mis a\u00f1os escolares, cuando estudi\u00e9 en la escuela 179 de Mosc\u00fa y particip\u00e9 con \u00e9xito en olimpiadas de inform\u00e1tica.<\/p>\n

Un n\u00famero limitado de especialistas en algoritmos parametrizados entra en el bar\u2026<\/h3>\n

El ejemplo se toma del libro \u00abParameterized algorithms\u00bb<\/a><\/noindex><\/i><\/p>\n

Imagina que eres un guardia de seguridad en un peque\u00f1o bar en un pueblo. Cada viernes, la mitad del pueblo viene a tu bar a relajarse, lo que te genera muchos problemas: tienes que expulsar a los clientes problem\u00e1ticos para evitar peleas. Al final, te aburres de esto y decides tomar medidas preventivas.<\/p>\n

Dado que tu pueblo es peque\u00f1o, sabes exactamente qu\u00e9 pares de clientes tienen una alta probabilidad de pelear si entran al bar juntos. Tienes una lista de n<\/i> personas que vendr\u00e1n esta noche al bar. Decides no dejar entrar a ciertos ciudadanos de manera que nadie termine pele\u00e1ndose. Al mismo tiempo, tu jefe no quiere perder ganancias y estar\u00e1 descontento si no dejas entrar a m\u00e1s de k<\/i> personas.<\/p>\n

Desafortunadamente, el problema que enfrentan es un cl\u00e1sico problema NP-duro. Podr\u00edas conocerlo como Vertex Cover<\/a><\/noindex>, o como el problema del cubrimiento de v\u00e9rtices. Para tales problemas, en general, no se conocen algoritmos que funcionen en un tiempo razonable. Para ser precisos, la hip\u00f3tesis ETH (Hip\u00f3tesis del Tiempo Exponencial) no demostrada dice que este problema no se puede resolver en un tiempo \"C\u00f3mo, es decir, que no se puede idear algo significativamente mejor que la b\u00fasqueda completa. Por ejemplo, supongamos que un grupo de n = 1000<\/i> personas va a acudir a un bar. Entonces, la b\u00fasqueda completa implicar\u00e1 \"C\u00f3mo opciones, que es aproximadamente \"C\u00f3mo \u2014 una cantidad loca. Afortunadamente, su direcci\u00f3n le ha impuesto un l\u00edmite k = 10<\/i>, por lo que el n\u00famero de combinaciones que debe considerar es mucho menor: el n\u00famero de subconjuntos de diez elementos es \"C\u00f3mo. Esto ya es mejor, pero a\u00fan as\u00ed no se puede contar en un d\u00eda ni siquiera en un cl\u00faster potente.
\n\"C\u00f3mo
\nPara eliminar la posibilidad de peleas con esta configuraci\u00f3n de relaciones tensas entre los visitantes del bar, es necesario no dejar entrar a Bob, Daniel y Fyodor. No hay soluci\u00f3n en la que queden solo dos afuera.<\/p>\n

\u00bfSignifica esto que es hora de rendirse y dejar entrar a todos? Consideremos otras opciones. Por ejemplo, se puede no dejar entrar solo a aquellos que probablemente pelear\u00e1n con una cantidad muy grande de gente. Si alguien puede pelear con al menos k + 1<\/i> otra persona, entonces definitivamente no se le puede dejar entrar; de lo contrario, habr\u00e1 que no dejar entrar a todos k + 1<\/i> los ciudadanos con quienes puede pelear, lo que ya seguro descontentar\u00e1 a la direcci\u00f3n.<\/p>\n

Supongamos que has echado a todos los que pudiste seg\u00fan este principio. Entonces, todos los dem\u00e1s pueden pelear con no m\u00e1s de k<\/i> personas. Echando de ellos k<\/i> personas, puedes prevenir no m\u00e1s de \"C\u00f3mo conflictos. Significa que, si hay m\u00e1s de \"C\u00f3mo personas implicadas en al menos un conflicto, entonces definitivamente no podr\u00e1s prevenirlos todos. Dado que, evidentemente, los que no son conflictivos los dejar\u00e1s entrar, debes considerar todos los subconjuntos de tama\u00f1o diez de doscientos personas. Hay aproximadamente \"C\u00f3mo, y tal cantidad de operaciones ya se puede contar en un cl\u00faster.<\/p>\n

Si es posible incluir a personalidades que no entren en conflicto, \u00bfqu\u00e9 pasa con aquellos que participan en solo un conflicto? En realidad, tambi\u00e9n se les puede dejar entrar, cerrando la puerta ante su oponente. De hecho, si Alicia solo tiene conflictos con Bob, al permitir la entrada de Alicia, no perderemos: Bob puede tener otros conflictos y Alicia no tiene ninguno. Adem\u00e1s, no tiene sentido no dejar entrar a ambos. Despu\u00e9s de tales operaciones, no quedan m\u00e1s que \"C\u00f3mo invitados con un destino incierto: en total, tenemos \"C\u00f3mo conflictos, en cada uno de los cuales hay dos participantes y cada uno participa en al menos dos. Por lo tanto, solo queda recorrer \"C\u00f3mo variantes, lo que podr\u00eda considerarse como medio d\u00eda en un port\u00e1til.<\/p>\n

En realidad, con razonamientos simples se pueden obtener condiciones a\u00fan m\u00e1s atractivas. Notemos que necesitamos resolver todas las disputas, es decir, de cada par en conflicto elegir al menos a una persona que no dejaremos entrar. Consideremos el siguiente algoritmo: tomaremos cualquier conflicto, eliminaremos a un participante y comenzaremos recursivamente desde el resto, luego eliminaremos al otro y tambi\u00e9n iniciaremos recursivamente. Dado que en cada paso eliminamos a alguien, el \u00e1rbol de recursi\u00f3n de este algoritmo es un \u00e1rbol binario de profundidad k<\/i>, por lo tanto, el algoritmo funciona en \"C\u00f3mo, donde n<\/i> \u2014 cantidad de nodos, y m<\/i> \u2014 cantidad de aristas. En nuestro ejemplo, esto es del orden de diez millones, lo que se calcular\u00e1 en fracciones de segundo no solo en un port\u00e1til, sino incluso en un tel\u00e9fono m\u00f3vil.<\/p>\n

El ejemplo anterior es un ejemplo de un algoritmo parametrizado<\/b>. Los algoritmos parametrizados son aquellos que funcionan en un tiempo f(k) poly(n)<\/i>, donde p<\/i> \u2014 polinomio, f<\/i> \u2014 funci\u00f3n computable arbitraria, y k<\/i> \u2014 alg\u00fan par\u00e1metro que, muy probablemente, ser\u00e1 mucho menor que el tama\u00f1o del problema.<\/p>\n

Todos los razonamientos hasta este algoritmo dan el ejemplo de kernelizaci\u00f3n<\/b> una de las t\u00e9cnicas comunes para crear algoritmos parametrizados. La kernelizaci\u00f3n es la reducci\u00f3n del tama\u00f1o del problema a un valor limitado por una funci\u00f3n del par\u00e1metro. El problema obtenido a menudo se denomina n\u00facleo. As\u00ed, mediante razonamientos simples sobre las potencias de los v\u00e9rtices, obtuvimos un n\u00facleo cuadr\u00e1tico para el problema de Vertex Cover, parametrizado por el tama\u00f1o de la respuesta. Existen otros par\u00e1metros que se pueden elegir para este problema (por ejemplo, Vertex Cover Above LP), pero discutiremos exactamente este par\u00e1metro.<\/p>\n

Desaf\u00edo Pace<\/h3>\n

Competencia Desaf\u00edo PACE<\/a><\/noindex> (El Desaf\u00edo de Algoritmos Parametrizados y Experimentos Computacionales) surgi\u00f3 en 2015 para establecer un v\u00ednculo entre los algoritmos parametrizados y los enfoques utilizados en la pr\u00e1ctica para resolver problemas computacionales. Las primeras tres competencias se centraron en la b\u00fasqueda de la anchura de \u00e1rbol del grafo (Anchura de \u00c1rbol<\/a><\/noindex>), la b\u00fasqueda del \u00e1rbol de Steiner (\u00c1rbol de Steiner<\/a><\/noindex>) y la b\u00fasqueda de un conjunto de v\u00e9rtices que corta ciclos (Conjunto de V\u00e9rtices de Retroalimentaci\u00f3n<\/a><\/noindex>). Este a\u00f1o, uno de los problemas en los que se pudo intentar demostrar habilidades fue el mencionado arriba sobre el cubrimiento de v\u00e9rtices.<\/p>\n

La competencia gana popularidad con cada a\u00f1o que pasa. Si se cree en los datos preliminares, este a\u00f1o solo en la competencia para resolver el problema del cubrimiento de v\u00e9rtices participaron 24 equipos. Cabe se\u00f1alar que la competencia no dura solo unas pocas horas, ni una semana, sino varios meses. Los equipos tienen la oportunidad de investigar la literatura, idear su propia idea original y tratar de implementarla. Esencialmente, esta competencia representa un trabajo de investigaci\u00f3n. Las ideas de las soluciones m\u00e1s efectivas y la premiaci\u00f3n de los ganadores se llevar\u00e1n a cabo junto con la conferencia IPEC<\/a><\/noindex> (Simposio Internacional sobre C\u00e1lculo Parametrizado y Exacto) en el marco de la reuni\u00f3n algor\u00edtmica anual m\u00e1s grande en Europa ALGO<\/a><\/noindex>. Se puede encontrar m\u00e1s informaci\u00f3n sobre la competencia en el sitio web<\/a><\/noindex>, y los resultados de a\u00f1os anteriores est\u00e1n disponibles en aqu\u00ed<\/a><\/noindex>.<\/p>\n

Esquema de soluci\u00f3n<\/h3>\n

Para abordar el problema de la cobertura de v\u00e9rtices, intent\u00e9 aplicar algoritmos parametrizados. Estos generalmente consisten en dos partes: reglas de simplificaci\u00f3n (que idealmente conducen a la kernelizaci\u00f3n) y reglas de bifurcaci\u00f3n. Las reglas de simplificaci\u00f3n son un preprocesamiento de la entrada en tiempo polin\u00f3mico. El objetivo de aplicar tales reglas es reducir el problema a un problema equivalente de menor tama\u00f1o. Las reglas de simplificaci\u00f3n son la parte m\u00e1s costosa del algoritmo, y la aplicaci\u00f3n de esta parte conduce al tiempo total de ejecuci\u00f3n \"C\u00f3mo en lugar de un tiempo polin\u00f3mico simple. En nuestro caso, las reglas de bifurcaci\u00f3n se basan en que para cada v\u00e9rtice se debe tomar como respuesta ya sea \u00e9l o su vecino.<\/p>\n

El esquema general es el siguiente: aplicamos las reglas de simplificaci\u00f3n, luego elegimos un v\u00e9rtice y hacemos dos llamadas recursivas: en la primera tomamos el v\u00e9rtice como respuesta, y en la otra tomamos a todos sus vecinos. A esto lo llamamos bifurcarnos (branching) por este v\u00e9rtice.<\/p>\n

A este esquema se le har\u00e1 exactamente una adici\u00f3n en el siguiente p\u00e1rrafo.<\/p>\n

Ideas para las reglas de bifurcaci\u00f3n (branching)<\/h3>\n

Hablemos sobre c\u00f3mo elegir el v\u00e9rtice por el que se realizar\u00e1 la bifurcaci\u00f3n.
\nLa idea principal es muy codiciosa en el sentido algor\u00edtmico: tomemos el v\u00e9rtice de mayor grado y bifurc\u00e9monos precisamente por \u00e9l. \u00bfPor qu\u00e9 parece que esto es mejor? Porque en la segunda rama de la llamada recursiva, de este modo eliminaremos muchos v\u00e9rtices. Se puede esperar que quede un grafo peque\u00f1o y que trabajemos r\u00e1pidamente sobre \u00e9l.<\/p>\n

Este enfoque con las t\u00e9cnicas simples de kernelizaci\u00f3n ya discutidas se comporta bastante bien, resolviendo algunas pruebas de varios miles de v\u00e9rtices. Pero, por ejemplo, funciona mal para grafos c\u00fabicos (es decir, grafos en los que el grado de cada v\u00e9rtice es tres).
\nHay otra idea basada en un pensamiento bastante simple: si el grafo es desconexo, se puede resolver la tarea en sus componentes de conectividad de forma independiente, combinando las respuestas al final. Esta, por cierto, es la peque\u00f1a modificaci\u00f3n prometida en el esquema, que acelerar\u00e1 significativamente la soluci\u00f3n: antes, en tal caso, trabaj\u00e1bamos por el producto de los tiempos de conteo de respuestas de los componentes, y ahora trabajamos por la suma. Y para acelerar la bifurcaci\u00f3n, es necesario convertir el grafo conexo en desconexo.<\/p>\n

\u00bfC\u00f3mo hacerlo? Si en el grafo hay un punto de articulaci\u00f3n, se debe bifurcar exactamente en \u00e9l. El punto de articulaci\u00f3n es un v\u00e9rtice tal que, al eliminarlo, el grafo pierde su conectividad. Se puede encontrar todos los puntos de articulaci\u00f3n en el grafo usando un algoritmo cl\u00e1sico en tiempo lineal. Este enfoque acelera notablemente el bifurcamiento.
\n\"C\u00f3mo
\nAl eliminar cualquiera de los v\u00e9rtices destacados, el grafo se descompondr\u00e1 en componentes de conectividad.<\/p>\n

Esto lo haremos, pero queremos m\u00e1s. Por ejemplo, buscar peque\u00f1os cortes de v\u00e9rtices en el grafo y realizar la bifurcaci\u00f3n usando esos v\u00e9rtices. El m\u00e9todo m\u00e1s eficiente que conozco para encontrar el corte global m\u00ednimo de v\u00e9rtices es utilizar el \u00e1rbol de Gomory-Hu, que se construye en tiempo c\u00fabico. En el desaf\u00edo PACE, el tama\u00f1o t\u00edpico del grafo es de varios miles de v\u00e9rtices. Con este panorama, en cada v\u00e9rtice del \u00e1rbol de recursi\u00f3n se deben realizar miles de millones de operaciones. Por lo tanto, resolver el problema en el tiempo asignado es simplemente imposible.<\/p>\n

Intentemos optimizar la soluci\u00f3n. El corte m\u00ednimo de v\u00e9rtices entre un par de v\u00e9rtices se puede encontrar utilizando cualquier algoritmo que construya flujo m\u00e1ximo. Se puede aplicar a tal red. el algoritmo de Dinic<\/a><\/noindex>, en la pr\u00e1ctica funciona muy r\u00e1pido. Tengo la sospecha de que te\u00f3ricamente se puede demostrar una cota en el tiempo de ejecuci\u00f3n \"C\u00f3mo, lo cual ya es bastante aceptable.<\/p>\n

He intentado varias veces buscar cortes entre pares de v\u00e9rtices aleatorios y tomar el m\u00e1s equilibrado. Desafortunadamente, en las pruebas abiertas del desaf\u00edo PACE esto dio malos resultados. Compar\u00e9 con el algoritmo que se bifurca por v\u00e9rtices de m\u00e1xima grado, ejecut\u00e1ndolo con una restricci\u00f3n en la profundidad de descenso. Despu\u00e9s del algoritmo que intenta encontrar un corte de esta manera, quedaban grafos de mayor tama\u00f1o. Esto se debe a que los cortes resultaban muy desequilibrados: al eliminar de 5 a 10 v\u00e9rtices, se lograba desprender solo de 15 a 20.<\/p>\n

Cabe mencionar que en los art\u00edculos sobre los algoritmos te\u00f3ricamente m\u00e1s r\u00e1pidos se utilizan t\u00e9cnicas de selecci\u00f3n de v\u00e9rtices para la bifurcaci\u00f3n que son mucho m\u00e1s avanzadas. Estas t\u00e9cnicas tienen una implementaci\u00f3n muy compleja y, a menudo, malas estimaciones en cuanto a tiempo y memoria. No logr\u00e9 extraer de ellas opciones razonables para la pr\u00e1ctica.<\/p>\n

C\u00f3mo aplicar las reglas de simplificaci\u00f3n<\/h3>\n

Ya tenemos ideas de kernelizaci\u00f3n. Recuerdo:<\/p>\n

    \n
  1. Si hay un v\u00e9rtice aislado, eliminarlo.<\/li>\n
  2. Si hay un v\u00e9rtice de grado 1, elim\u00ednalo y toma su vecino como respuesta.<\/li>\n
  3. Si hay un v\u00e9rtice de grado al menos k + 1<\/i>, t\u00f3malo como respuesta.<\/li>\n<\/ol>\n

    Con los dos primeros est\u00e1 claro, con el tercero hay un truco. Si en la tarea humor\u00edstica sobre el bar se nos dio un l\u00edmite superior en k<\/i>, en el PACE Challenge solo necesitas encontrar una cobertura de v\u00e9rtices de tama\u00f1o m\u00ednimo. Esta es una transformaci\u00f3n t\u00edpica de problemas de b\u00fasqueda (Search Problem) a problemas de decisi\u00f3n (Decision Problem), a menudo no se diferencia entre estos dos tipos de problemas. En la pr\u00e1ctica, si estamos escribiendo un resolutivo para el problema de la cobertura de v\u00e9rtices, la diferencia puede ser notable. Por ejemplo, como en el tercer punto.<\/p>\n

    Desde el punto de vista de la implementaci\u00f3n, se pueden seguir dos enfoques. El primer enfoque se llama Iterative Deepening. Consiste en lo siguiente: podemos comenzar con alg\u00fan l\u00edmite razonable inferior en la respuesta y luego ejecutar nuestro algoritmo, utilizando este l\u00edmite como un l\u00edmite superior en la respuesta, sin profundizar en la recursi\u00f3n m\u00e1s all\u00e1 de este l\u00edmite. Si encontramos alguna respuesta, es garantizadamente \u00f3ptima, de lo contrario, se puede aumentar este l\u00edmite en uno y volver a ejecutarlo.<\/p>\n

    El otro enfoque es mantener alguna respuesta \u00f3ptima actual y buscar una respuesta de menor tama\u00f1o, ajustando este par\u00e1metro al encontrarla k<\/i> para podar m\u00e1s ramas innecesarias en la b\u00fasqueda.<\/p>\n

    Despu\u00e9s de realizar varios experimentos nocturnos, me detuve en una combinaci\u00f3n de estos dos enfoques: primero ejecuto mi algoritmo con alg\u00fan l\u00edmite en la profundidad de b\u00fasqueda (ajust\u00e1ndolo de manera que tome un tiempo insignificante en comparaci\u00f3n con la soluci\u00f3n principal) y utilizo la mejor soluci\u00f3n encontrada como l\u00edmite superior en la respuesta, es decir, en lo que es k<\/i>.<\/p>\n

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

    Con los v\u00e9rtices de grado 0 y 1 hemos resuelto la cuesti\u00f3n. Resulta que tambi\u00e9n se puede hacer con los v\u00e9rtices de grado 2, pero para esto se requerir\u00e1n operaciones m\u00e1s complejas en el gr\u00e1fico.<\/p>\n

    Para explicar esto, hay que designar de alguna manera los v\u00e9rtices. Llamaremos al v\u00e9rtice de grado 2 como v\u00e9rtice v<\/i>, y a sus vecinos como v\u00e9rtices x<\/i> y y<\/i>. A continuaci\u00f3n, tendremos dos casos.<\/p>\n

      \n
    1. Cuando x<\/i> y y<\/i> \u2014 vecinos. Entonces se puede tomar como respuesta x<\/i> y y<\/i>, y v<\/i> eliminar. Y de hecho, de este tri\u00e1ngulo, al menos dos v\u00e9rtices deben tomarse en la respuesta y seguramente no perderemos si tomamos x<\/i> y y<\/i>: probablemente tienen m\u00e1s vecinos, mientras que v<\/i> ellos no tienen.<\/li>\n
    2. Cuando x<\/i> y y<\/i> \u2014 no vecinos. Entonces, se afirma que se pueden fusionar los tres v\u00e9rtices en uno. La idea es que en tal caso hay una respuesta \u00f3ptima, en la que tomaremos ya sea v<\/i>, o ambos v\u00e9rtices x<\/i> y y<\/i>. En el primer caso, tendremos que incluir en la respuesta a todos los vecinos x<\/i> y y<\/i>, mientras que en el segundo no es necesario. Esto corresponde exactamente a los casos en los que noIncluimos el v\u00e9rtice fusionado en la respuesta y cuando s\u00ed lo hacemos. Solo queda notar que en ambos casos la respuesta de tal operaci\u00f3n se reduce en uno.<\/li>\n<\/ol>\n

      \"C\u00f3mo<\/p>\n

      Cabe se\u00f1alar que este enfoque es bastante complicado de implementar de manera eficiente en tiempo lineal. La fusi\u00f3n de v\u00e9rtices es una operaci\u00f3n compleja, se deben copiar las listas de vecinos. Si no se hace con cuidado, se puede obtener un tiempo de ejecuci\u00f3n asint\u00f3ticamente sub\u00f3ptimo (por ejemplo, si despu\u00e9s de cada fusi\u00f3n se copian muchos bordes). Me detuve en la b\u00fasqueda de caminos enteros de v\u00e9rtices de grado 2 y en el an\u00e1lisis de muchos casos particulares, como ciclos de estos v\u00e9rtices o de todos estos v\u00e9rtices excepto uno.<\/p>\n

      Adem\u00e1s, es necesario que esta operaci\u00f3n sea reversible, para que al volver de la recursi\u00f3n restauramos el gr\u00e1fico a su estado original. Para asegurar esto, no limpi\u00e9 las listas de bordes de los v\u00e9rtices fusionados, despu\u00e9s de lo cual simplemente sab\u00eda a d\u00f3nde dirigir los bordes necesarios. Esta implementaci\u00f3n de gr\u00e1ficos tambi\u00e9n requiere cuidado, pero garantiza un tiempo lineal eficiente. Y para gr\u00e1ficos de varios miles de bordes, f\u00e1cilmente cabe en la cach\u00e9 del procesador, lo que proporciona grandes ventajas en velocidad.<\/p>\n

      N\u00facleo lineal<\/h3>\n

      Finalmente, la parte m\u00e1s interesante del n\u00facleo.<\/p>\n

      Para empezar, recordemos que en los gr\u00e1ficos bipartitos, se puede buscar la cobertura m\u00ednima de v\u00e9rtices en \"C\u00f3mo. Para ello, se debe utilizar el algoritmo Hopcroft-Karp<\/a><\/noindex> para encontrar all\u00ed el emparejamiento m\u00e1ximo, y luego utilizar el teorema de K\u00f6nig-Egerv\u00e1ry<\/a><\/noindex>.<\/p>\n

      La idea del n\u00facleo lineal es la siguiente: primero bifurcamos el gr\u00e1fico, es decir, en lugar de cada v\u00e9rtice v<\/i> creamos dos v\u00e9rtices \"C\u00f3mo y \"C\u00f3mo, y en lugar de cada borde u \u2014 v<\/i> creamos dos bordes \"C\u00f3mo y \"C\u00f3mo. El gr\u00e1fico obtenido ser\u00e1 bipartito. Encontramos en \u00e9l una cobertura m\u00ednima de v\u00e9rtices. Algunos v\u00e9rtices del gr\u00e1fico original estar\u00e1n en la cobertura dos veces, algunos una sola vez, y algunos no estar\u00e1n en absoluto. El teorema de Nemhauser-Trotter afirma que en tal caso se pueden eliminar los v\u00e9rtices que no aparecieron y tomar como respuesta aquellos que aparecieron dos veces. Adem\u00e1s, indica que de los v\u00e9rtices restantes (aquellos que aparecieron una vez) debemos tomar al menos la mitad como respuesta.<\/p>\n

      Acabamos de aprender a dejar en el gr\u00e1fico no m\u00e1s de 2k<\/i> v\u00e9rtices. Y es cierto, si en la respuesta restante hay al menos la mitad de todos los v\u00e9rtices, entonces el total de v\u00e9rtices no es m\u00e1s que 2k<\/i>.<\/p>\n

      Aqu\u00ed he logrado dar un peque\u00f1o paso adelante. Est\u00e1 claro que el n\u00facleo construido de esta manera depende de qu\u00e9 cobertura m\u00ednima de v\u00e9rtices tomamos en el gr\u00e1fico bipartito. Quisiera tomar una que minimizara el n\u00famero de v\u00e9rtices restantes. Antes, esto solo se pod\u00eda hacer en un tiempo \"C\u00f3mo. Yo ide\u00e9 una implementaci\u00f3n de este algoritmo en un tiempo \"C\u00f3mo, as\u00ed que este n\u00facleo se puede buscar en gr\u00e1ficos de cientos de miles de v\u00e9rtices en cada etapa de ramificaci\u00f3n.<\/p>\n

      Resultado<\/h3>\n

      La pr\u00e1ctica demuestra que mi soluci\u00f3n funciona bien en pruebas con varios cientos de v\u00e9rtices y varios miles de aristas. En tales pruebas, se puede esperar que la soluci\u00f3n se encuentre en media hora. La probabilidad de encontrar una respuesta en un tiempo razonable aumenta en principio si hay muchos v\u00e9rtices de alto grado en el gr\u00e1fico, por ejemplo, de grado 10 o m\u00e1s.<\/p>\n

      Para participar en la competencia, era necesario enviar las soluciones a optil.io<\/a><\/noindex>. Seg\u00fan la tabla presentada all\u00ed , mi soluci\u00f3n ocupa el tercer lugar en las pruebas p\u00fablicas de veinte, con una gran diferencia con el segundo. Si soy completamente honesto, no est\u00e1 del todo claro c\u00f3mo se evaluar\u00e1n las soluciones en la competencia en s\u00ed: por ejemplo, mi soluci\u00f3n pasa menos pruebas que la del cuarto lugar, pero en aquellas que pasa, funciona m\u00e1s r\u00e1pido.<\/a><\/noindex>Los resultados en las pruebas cerradas se conocer\u00e1n el primero de julio.<\/p>\n

      La investigaci\u00f3n cient\u00edfica es, sin duda, la parte m\u00e1s interesante de nuestra formaci\u00f3n. La idea es, a\u00fan en la universidad, tener la oportunidad de probarse en la direcci\u00f3n elegida.<\/p>\n

      Fuente: 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\udd47C\u00f3mo resolver problemas NP-dif\u00edciles con algoritmos parametrizados | ProHoster","description":"\ud83e\udd47C\u00f3mo resolver problemas NP-dif\u00edciles utilizando algoritmos parametrizados | ProHoster","canonical_url":"https:\/\/prohoster.info\/es\/blog\/news\/kak-reshat-np-trudnye-zadachi-s-pomoshhyu-parametrizovannyh-algoritmov","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"es_ES","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\/es\/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\/es\/wp-json\/wp\/v2\/posts\/35406","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/es\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/es\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/es\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/es\/wp-json\/wp\/v2\/comments?post=35406"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/es\/wp-json\/wp\/v2\/posts\/35406\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/es\/wp-json\/wp\/v2\/media\/26562"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/es\/wp-json\/wp\/v2\/media?parent=35406"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/es\/wp-json\/wp\/v2\/categories?post=35406"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/es\/wp-json\/wp\/v2\/tags?post=35406"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}