{"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\/fr\/blog\/news\/kak-reshat-np-trudnye-zadachi-s-pomoshhyu-parametrizovannyh-algoritmov","title":{"rendered":"Comment r\u00e9soudre les probl\u00e8mes NP-difficiles \u00e0 l'aide d'algorithmes param\u00e9tr\u00e9s","gt_translate_keys":[{"key":"rendered","format":"text"}]},"content":{"rendered":"

Le travail de recherche scientifique est sans doute la partie la plus int\u00e9ressante de notre formation. L'id\u00e9e est d'exp\u00e9rimenter dans le domaine choisi d\u00e8s l'universit\u00e9. Par exemple, les \u00e9tudiants en ing\u00e9nierie logicielle et en apprentissage machine font souvent des recherches dans des entreprises (principalement JetBrains ou Yandex, mais pas seulement).<\/p>\n

Dans ce post, je vais parler de mon projet en sciences informatiques. Dans le cadre de ce travail, j'ai \u00e9tudi\u00e9 et mis en pratique des approches pour r\u00e9soudre l'un des probl\u00e8mes NP-difficiles les plus connus : le probl\u00e8me du couvercle de sommets<\/b>.<\/p>\n

Actuellement, un int\u00e9r\u00eat rapide se d\u00e9veloppe pour les probl\u00e8mes NP-difficiles \u2014 les algorithmes param\u00e9tr\u00e9s. Je vais essayer de vous mettre au courant, de vous parler de quelques algorithmes param\u00e9tr\u00e9s simples et de d\u00e9crire une m\u00e9thode puissante qui m'a beaucoup aid\u00e9. J'ai pr\u00e9sent\u00e9 mes r\u00e9sultats au concours PACE Challenge : \u00e0 la suite des tests ouverts, ma solution occupe la troisi\u00e8me place, et les r\u00e9sultats finaux seront connus le 1er juillet.<\/p>\n

\"Comment
\n<\/a><\/noindex><\/p>\n

\u00c0 propos de moi<\/h3>\n

Je m'appelle Vassily Alferov, je termine actuellement ma troisi\u00e8me ann\u00e9e \u00e0 la HSE de Saint-P\u00e9tersbourg. Je me passionne pour les algorithmes depuis mes ann\u00e9es de lyc\u00e9e, lorsque j'\u00e9tudiais \u00e0 l'\u00e9cole 179 de Moscou et que je participais avec succ\u00e8s aux olympiades d'informatique.<\/p>\n

Un nombre limit\u00e9 de sp\u00e9cialistes en algorithmes param\u00e9tr\u00e9s entre dans un bar\u2026<\/h3>\n

L'exemple est tir\u00e9 du livre \u00abParameterized algorithms\u00bb<\/a><\/noindex><\/i><\/p>\n

Imaginez que vous \u00eates le gardien d'un bar dans une petite ville. Chaque vendredi, la moiti\u00e9 de la ville vient se d\u00e9tendre dans votre bar, ce qui vous cause pas mal de tracas : vous devez evincer les clients turbulents pour emp\u00eacher les bagarres. Finalement, cela vous ennuie, et vous d\u00e9cidez de prendre des mesures pr\u00e9ventives.<\/p>\n

\u00c9tant donn\u00e9 que votre ville est petite, vous savez exactement quelles paires de clients sont susceptibles de se battre s'ils sont dans le bar ensemble. Vous avez une liste de n<\/i> personnes qui viendront ce soir au bar. Vous d\u00e9cidez de ne pas laisser entrer certains habitants de fa\u00e7on \u00e0 ce que personne ne se batte. En m\u00eame temps, votre direction ne veut pas perdre de profits et sera m\u00e9contente si vous ne laissez pas entrer plus de k<\/i> personnes.<\/p>\n

Malheureusement, le probl\u00e8me auquel vous \u00eates confront\u00e9 est un probl\u00e8me NP-difficile classique. Vous pourriez le conna\u00eetre sous le nom de Couvercle de sommets<\/a><\/noindex>, ou comme le probl\u00e8me du couplage de sommets. Pour de tels probl\u00e8mes, il n'existe g\u00e9n\u00e9ralement pas d'algorithmes qui fonctionnent dans un d\u00e9lai raisonnable. Pour \u00eatre pr\u00e9cis, l'hypoth\u00e8se ETH (Exponential Time Hypothesis), qui n'est pas prouv\u00e9e et est assez forte, sugg\u00e8re que ce probl\u00e8me ne peut \u00eatre r\u00e9solu dans un temps acceptable. \"Comment, c'est-\u00e0-dire qu'il n'y a rien de notablement meilleur que la recherche exhaustive. Par exemple, supposons qu'un groupe de personnes vienne au bar n = 1000<\/i> personnes. Dans ce cas, la recherche exhaustive donnerait \"Comment options, ce qui fait environ \"Comment \u2014 horriblement beaucoup. Heureusement, votre direction vous a impos\u00e9 une restriction k = 10<\/i>, donc le nombre de combinaisons \u00e0 examiner est beaucoup plus petit : le nombre des sous-ensembles de dix \u00e9l\u00e9ments est \"Comment. C'est d\u00e9j\u00e0 mieux, mais ce n'est toujours pas faisable en une journ\u00e9e m\u00eame sur un puissant cluster.
\n\"Comment
\nPour \u00e9viter la probabilit\u00e9 de bagarres avec une telle configuration de relations tendues entre les clients du bar, il faut ne pas laisser entrer Bob, Daniel et Fiodor. Il n'existe pas de solution o\u00f9 seulement deux personnes sont laiss\u00e9es dehors.<\/p>\n

Cela signifie-t-il qu'il est temps d'abandonner et de laisser entrer tout le monde ? Explorons d'autres options. Par exemple, on peut n'emp\u00eacher d'entrer que ceux qui pourraient se battre avec un grand nombre de personnes. Si quelqu'un peut se battre avec au moins k + 1<\/i> autres personnes, alors il ne doit pas \u00eatre admis \u2014 sinon, il faudra interdire l'entr\u00e9e \u00e0 tous ceux k + 1<\/i> avec qui il pourrait se battre, ce qui ne manquera pas de contrarier la direction.<\/p>\n

Supposons que vous ayez exclu toutes les personnes possibles selon ce principe. Alors, toutes les autres ne peuvent se battre avec pas plus de k<\/i> personnes. En excluant k<\/i> personnes, vous pouvez \u00e9viter au maximum \"Comment conflits. Cela signifie que si plus de \"Comment personnes sont impliqu\u00e9es dans au moins un conflit, vous ne pourrez pas tous les emp\u00eacher. \u00c9videmment, vous ferez entrer ceux qui ne sont pas en conflit, donc vous devez examiner tous les sous-ensembles de taille dix parmi deux cents personnes. Il y en a environ \"Comment, et un tel nombre d'op\u00e9rations peut d\u00e9j\u00e0 \u00eatre trait\u00e9 sur un cluster.<\/p>\n

S'il est possible de faire entrer des personnalit\u00e9s qui ne sont pas en conflit, que dire de celles qui participent \u00e0 un seul conflit ? En r\u00e9alit\u00e9, nous pouvons \u00e9galement les laisser entrer, en fermant la porte \u00e0 leur opposant. En effet, si Alice est en conflit seulement avec Bob, accueillir Alice parmi eux ne nous fera pas perdre : Bob peut avoir d'autres conflits et Alice, aucun. D'autant plus qu'il est insens\u00e9 de ne laisser entrer aucun des deux. Apr\u00e8s de telles op\u00e9rations, il nous reste au maximum \"Comment des invit\u00e9s au destin ind\u00e9termin\u00e9 : au total, nous avons \"Comment des conflits, chacun impliquant deux participants qui participent tous \u00e0 au moins deux. Donc, il ne reste plus qu'\u00e0 consid\u00e9rer \"Comment des options, ce qui peut parfaitement \u00eatre calcul\u00e9 en une demi-journ\u00e9e sur un ordinateur portable.<\/p>\n

En r\u00e9alit\u00e9, avec des raisonnements simples, nous pouvons obtenir des conditions encore plus favorables. Notons que nous devons absolument r\u00e9soudre tous les diff\u00e9rends, c'est-\u00e0-dire choisir au moins une personne parmi chaque paire en conflit que nous ne laisserons pas entrer. Consid\u00e9rons l'algorithme suivant : prenons n'importe quel conflit, supprimons un participant et lan\u00e7ons de mani\u00e8re r\u00e9cursive sur le reste, puis supprimons l'autre et lan\u00e7ons aussi r\u00e9cursivement. Comme \u00e0 chaque \u00e9tape, nous \u00e9liminons quelqu'un, l'arbre de r\u00e9cursivit\u00e9 de cet algorithme est un arbre binaire de profondeur k<\/i>, donc, le temps total de l'algorithme est \"Comment, o\u00f9 n<\/i> \u2014 le nombre de sommets, et m<\/i> \u2014 le nombre d'ar\u00eates. Dans notre exemple, cela tourne autour de dix millions, ce qui peut \u00eatre calcul\u00e9 en une fraction de seconde, non seulement sur un ordinateur portable, mais m\u00eame sur un t\u00e9l\u00e9phone mobile.<\/p>\n

L'exemple ci-dessus est un exemple de d'algorithme param\u00e9tr\u00e9.<\/b>Les algorithmes param\u00e9tr\u00e9s sont des algorithmes qui fonctionnent en un temps f(k) poly(n)<\/i>, o\u00f9 p<\/i> \u2014 un polyn\u00f4me, o\u00f9 f<\/i> \u2014 une fonction calculable arbitraire, et o\u00f9 k<\/i> \u2014 un param\u00e8tre qui sera probablement beaucoup plus petit que la taille du probl\u00e8me.<\/p>\n

Tous les raisonnements pr\u00e9c\u00e9dents conduisent \u00e0 l'exemple de la kernelisation.<\/b> \u2014 l'une des techniques communes pour cr\u00e9er des algorithmes param\u00e9tr\u00e9s. La kernelisation consiste \u00e0 r\u00e9duire la taille d'un probl\u00e8me \u00e0 une valeur limit\u00e9e par une fonction d'un param\u00e8tre. Le probl\u00e8me r\u00e9sultant est souvent appel\u00e9 noyau. Ainsi, par des raisonnements simples sur les puissances des sommets, nous avons obtenu un noyau quadratique pour le probl\u00e8me de Vertex Cover, param\u00e9tr\u00e9 par la taille de la r\u00e9ponse. Il existe d'autres param\u00e8tres qui peuvent \u00eatre choisis pour ce probl\u00e8me (par exemple, Vertex Cover Above LP), mais nous allons discuter de ce param\u00e8tre sp\u00e9cifique.<\/p>\n

D\u00e9fi Pace<\/h3>\n

Comp\u00e9tition D\u00e9fi PACE<\/a><\/noindex> (Le D\u00e9fi des Algorithmes Param\u00e9tr\u00e9s et des Exp\u00e9riences Computationnelles) a \u00e9t\u00e9 lanc\u00e9 en 2015 pour \u00e9tablir un lien entre les algorithmes param\u00e9tr\u00e9s et les approches utilis\u00e9es en pratique pour r\u00e9soudre des probl\u00e8mes computationnels. Les trois premi\u00e8res comp\u00e9titions \u00e9taient consacr\u00e9es \u00e0 la recherche de la largeur d'une arbre de graphe (Largeur d'Arbre<\/a><\/noindex>), \u00e0 la recherche de l'arbre de Steiner (Arbre de Steiner<\/a><\/noindex>) et \u00e0 la recherche d'un ensemble de sommets coupant les cycles (Ensemble de Sommets de Feedback<\/a><\/noindex>). Cette ann\u00e9e, l'un des probl\u00e8mes dans lequel il \u00e9tait possible de tenter sa chance \u00e9tait le probl\u00e8me de couverture de sommets d\u00e9crit ci-dessus.<\/p>\n

La comp\u00e9tition gagne en popularit\u00e9 chaque ann\u00e9e. Si l'on en croit les donn\u00e9es pr\u00e9liminaires, cette ann\u00e9e, 24 \u00e9quipes ont particip\u00e9 \u00e0 la comp\u00e9tition sur le probl\u00e8me de couverture de sommets. Il convient de noter que la comp\u00e9tition ne dure pas quelques heures et m\u00eame pas une semaine, mais plusieurs mois. Les \u00e9quipes ont la possibilit\u00e9 d'\u00e9tudier la litt\u00e9rature, de concevoir leur propre id\u00e9e originale et d'essayer de la mettre en \u0153uvre. En substance, cette comp\u00e9tition repr\u00e9sente un travail de recherche. Les id\u00e9es des solutions les plus efficaces et la remise des prix aux vainqueurs se d\u00e9rouleront conjointement avec la conf\u00e9rence IPEC<\/a><\/noindex> (Symposium International sur la Programmation Param\u00e9tr\u00e9e et Exacte) dans le cadre de la plus grande assembl\u00e9e algorithmique annuelle en Europe ALGO<\/a><\/noindex>. Pour plus d'informations sur la comp\u00e9tition elle-m\u00eame, vous pouvez consulter site<\/a><\/noindex>, et les r\u00e9sultats des ann\u00e9es pr\u00e9c\u00e9dentes sont disponibles ici<\/a><\/noindex>.<\/p>\n

Sch\u00e9ma de solution<\/h3>\n

Pour r\u00e9soudre le probl\u00e8me de couverture de sommets, j'ai tent\u00e9 d'appliquer des algorithmes param\u00e9tr\u00e9s. Ceux-ci se composent g\u00e9n\u00e9ralement de deux parties : des r\u00e8gles de simplification (qui, id\u00e9alement, m\u00e8nent \u00e0 la kernelisation) et des r\u00e8gles de fractionnement. Les r\u00e8gles de simplification consistent en un pr\u00e9traitement de l'entr\u00e9e en temps polynomial. L'objectif de l'application de telles r\u00e8gles est de r\u00e9duire le probl\u00e8me \u00e0 un probl\u00e8me \u00e9quivalent de taille plus petite. Les r\u00e8gles de simplification repr\u00e9sentent la partie la plus co\u00fbteuse de l'algorithme, et l'application de cette partie conduit \u00e0 un temps d'ex\u00e9cution global. \"Comment au lieu d'un simple temps polynomial. Dans notre cas, les r\u00e8gles de fractionnement reposent sur le fait que pour chaque sommet, il faut choisir soit lui, soit son voisin en r\u00e9ponse.<\/p>\n

Le sch\u00e9ma g\u00e9n\u00e9ral est le suivant : nous appliquons les r\u00e8gles de simplification, puis choisissons un sommet, et effectuons deux appels r\u00e9cursifs : dans le premier, nous le prenons en compte, et dans l'autre, nous prenons tous ses voisins. Nous appelons cela se fractionner (brancher) \u00e0 partir de ce sommet.<\/p>\n

Il y aura exactement un ajout \u00e0 ce sch\u00e9ma dans le paragraphe suivant.<\/p>\n

Id\u00e9es pour les r\u00e8gles de fractionnement (branching)<\/h3>\n

Discutons de la mani\u00e8re de choisir le sommet sur lequel se fera le fractionnement.
\nL'id\u00e9e principale est tr\u00e8s gourmande du point de vue algorithmique : prenons le sommet de degr\u00e9 maximal et fractionnons-nous pr\u00e9cis\u00e9ment \u00e0 partir de celui-ci. Pourquoi semble-t-il que cela soit mieux ? Parce que dans la deuxi\u00e8me branche de l'appel r\u00e9cursif, nous \u00e9liminons ainsi beaucoup de sommets. On peut s'attendre \u00e0 ce qu'il reste un petit graphe sur lequel nous travaillerons rapidement.<\/p>\n

Cette approche, avec les techniques simples de kernelisation d\u00e9j\u00e0 discut\u00e9es, montre des r\u00e9sultats plut\u00f4t satisfaisants, r\u00e9solvant certains tests de plusieurs milliers de sommets. Mais, par exemple, elle fonctionne mal pour les graphes cubiques (c'est-\u00e0-dire les graphes dans lesquels le degr\u00e9 de chaque sommet est \u00e9gal \u00e0 trois).
\nIl y a encore une id\u00e9e, bas\u00e9e sur une pens\u00e9e assez simple : si le graphe est d\u00e9connect\u00e9, le probl\u00e8me sur ses composants de connexit\u00e9 peut \u00eatre r\u00e9solu ind\u00e9pendamment, en r\u00e9unissant les r\u00e9ponses \u00e0 la fin. C'est d'ailleurs la petite modification promise dans le sch\u00e9ma qui acc\u00e9l\u00e9rera consid\u00e9rablement la solution : auparavant, dans ce cas, nous travaillions avec le produit des temps de calcul des r\u00e9ponses des composants, alors qu'\u00e0 pr\u00e9sent, nous travaillons avec la somme. Pour acc\u00e9l\u00e9rer le fractionnement, il faut transformer un graphe connect\u00e9 en d\u00e9connect\u00e9.<\/p>\n

Comment faire cela ? Si le graphe a un point d'articulation, il faut le fragmenter exactement \u00e0 ce point. Un point d'articulation est un sommet dont la suppression rend le graphe non connexe. On peut trouver tous les points d'articulation dans un graphe avec un algorithme classique en temps lin\u00e9aire. Cette approche acc\u00e9l\u00e8re consid\u00e9rablement le processus de fragmentation.
\n\"Comment
\nLors de la suppression de l'un des sommets marqu\u00e9s, le graphe se divisera en composants connexes.<\/p>\n

Nous allons le faire, mais nous voulons plus. Par exemple, rechercher dans le graphe de petites coupures de sommets et r\u00e9aliser des fragmentations \u00e0 partir de celles-ci. La m\u00e9thode la plus efficace que je connaisse pour trouver la coupure minimale globale de sommets consiste \u00e0 utiliser l'arbre de Gomory-Hu, qui se construit en temps cubique. Dans le PACE Challenge, la taille typique d'un graphe est de plusieurs milliers de sommets. Dans un tel sc\u00e9nario, chaque sommet de l'arbre de r\u00e9cursion doit ex\u00e9cuter des milliards d'op\u00e9rations. Il s'av\u00e8re donc qu'il est simplement impossible de r\u00e9soudre la t\u00e2che dans le temps imparti.<\/p>\n

Essayons d'optimiser la solution. La coupure minimale entre une paire de sommets peut \u00eatre trouv\u00e9e par n'importe quel algorithme construisant un flux maximal. On peut appliquer sur un tel r\u00e9seau l'algorithme de Dinic<\/a><\/noindex>, qui, en pratique, fonctionne tr\u00e8s rapidement. J'ai le soup\u00e7on qu'on peut th\u00e9oriquement prouver une estimation sur le temps d'ex\u00e9cution \"Comment, ce qui est d\u00e9j\u00e0 tout \u00e0 fait acceptable.<\/p>\n

J'ai essay\u00e9 plusieurs fois de rechercher des coupures entre des paires de sommets al\u00e9atoires et de choisir la plus \u00e9quilibr\u00e9e. Malheureusement, cela a donn\u00e9 de mauvais r\u00e9sultats lors des tests ouverts du PACE Challenge. J'ai compar\u00e9 cela avec un algorithme se fragmentant sur les sommets de degr\u00e9 maximal, en le lan\u00e7ant avec une limitation sur la profondeur de descente. Apr\u00e8s l'algorithme essayant de trouver une coupure de cette mani\u00e8re, il restait des graphes de plus grande taille. Cela est d\u00fb au fait que les coupures \u00e9taient tr\u00e8s d\u00e9s\u00e9quilibr\u00e9es : en supprimant 5-10 sommets, on n'arrivait qu'\u00e0 d\u00e9tacher seulement 15-20.<\/p>\n

Il convient de noter que dans les articles sur les algorithmes th\u00e9oriquement les plus rapides, des techniques de choix de sommets pour la fragmentation beaucoup plus avanc\u00e9es sont utilis\u00e9es. Ces techniques ont une mise en \u0153uvre tr\u00e8s complexe et souvent de mauvaises estimations en temps et en m\u00e9moire. Je n'ai pas r\u00e9ussi \u00e0 en extraire de vraiment acceptables pour la pratique.<\/p>\n

Comment appliquer les r\u00e8gles de simplification<\/h3>\n

Nous avons d\u00e9j\u00e0 des id\u00e9es de kernelisation. Je me souviens :<\/p>\n

    \n
  1. S'il y a un sommet isol\u00e9, il faut le supprimer.<\/li>\n
  2. Si une ar\u00eate de degr\u00e9 1 existe, la supprimer et prendre son voisin en r\u00e9ponse.<\/li>\n
  3. Si une ar\u00eate de degr\u00e9 au moins k + 1<\/i>, la prendre en r\u00e9ponse.<\/li>\n<\/ol>\n

    Pour les deux premiers, tout est clair, mais pour le troisi\u00e8me, il y a une astuce. Si dans le probl\u00e8me humoristique sur le bar, nous avions une limite sup\u00e9rieure sur k<\/i>, dans le PACE Challenge, il faut simplement trouver un couplage de sommets de taille minimale. C'est une transformation typique de probl\u00e8mes de recherche (Search Problem) en probl\u00e8mes de d\u00e9cision (Decision Problem), souvent, on ne fait pas de distinction entre les deux types de probl\u00e8mes. En pratique, si nous \u00e9crivons un solveur pour le probl\u00e8me du couplage des sommets, la diff\u00e9rence peut exister. Par exemple, comme dans le troisi\u00e8me point.<\/p>\n

    D'un point de vue mise en \u0153uvre, il existe deux approches. La premi\u00e8re approche s'appelle l'Approfondissement it\u00e9ratif. Elle consiste \u00e0 commencer \u00e0 partir d'une certaine limite inf\u00e9rieure raisonnable sur la r\u00e9ponse, puis \u00e0 lancer notre algorithme en utilisant cette limite comme une limite sup\u00e9rieure sur la r\u00e9ponse, sans descendre en r\u00e9cursivit\u00e9 au-dessous de cette limite. Si nous avons trouv\u00e9 une r\u00e9ponse, elle est garantie optimale ; sinon, nous pouvons augmenter cette limite d'une unit\u00e9 et relancer.<\/p>\n

    L'autre approche consiste \u00e0 conserver une certaine r\u00e9ponse optimale actuelle et \u00e0 chercher une r\u00e9ponse de taille inf\u00e9rieure, en modifiant ce param\u00e8tre lors de la d\u00e9couverte. k<\/i> pour couper davantage les branches superflues dans la recherche.<\/p>\n

    Apr\u00e8s quelques exp\u00e9riences nocturnes, je me suis arr\u00eat\u00e9 sur une combinaison de ces deux m\u00e9thodes : d'abord, je lance mon algorithme avec une certaine profondeur de recherche (en choisissant pour qu'elle prenne un temps n\u00e9gligeable par rapport \u00e0 la solution principale) et j'utilise la meilleure solution trouv\u00e9e comme limite sup\u00e9rieure sur la r\u00e9ponse \u2014 c'est-\u00e0-dire sur ce fameux k<\/i>.<\/p>\n

    Sommets de degr\u00e9 2<\/h3>\n

    Nous avons compris les sommets de degr\u00e9 0 et 1. Il s'av\u00e8re que cela peut \u00e9galement \u00eatre fait avec les sommets de degr\u00e9 2, mais cela n\u00e9cessitera des op\u00e9rations plus complexes sur le graphe.<\/p>\n

    Pour l'expliquer, il faut d'une certaine mani\u00e8re d\u00e9signer les sommets. Appelons un sommet de degr\u00e9 2 un sommet v<\/i>, et ses voisins - des sommets x<\/i> et y<\/i>. Ensuite, nous aurons deux cas.<\/p>\n

      \n
    1. Lorsque x<\/i> et y<\/i> \u2014 voisins. Alors nous pouvons prendre en r\u00e9ponse x<\/i> et y<\/i>, et v<\/i> supprimer. Et en effet, dans ce triangle, il faut prendre au moins deux sommets en r\u00e9ponse et nous ne perdrons pas, si nous prenons x<\/i> et y<\/i>: ils ont probablement encore des voisins, mais v<\/i> eux n'en ont pas.<\/li>\n
    2. Lorsque x<\/i> et y<\/i> \u2014 pas des voisins. Il est alors affirm\u00e9 que les trois sommets peuvent \u00eatre fusionn\u00e9s en un seul. L'id\u00e9e est que dans ce cas, il existe une r\u00e9ponse optimale, o\u00f9 nous prendrons soit v<\/i>, soit les deux sommets x<\/i> et y<\/i>. Dans le premier cas, nous devrons inclure tous les voisins dans la r\u00e9ponse x<\/i> et y<\/i>, tandis que dans le second, ce n'est pas n\u00e9cessaire. Cela correspond exactement aux cas o\u00f9 nous ne prenons pas le sommet fusionn\u00e9 dans la r\u00e9ponse et lorsque nous le prenons. Il reste \u00e0 noter que dans les deux cas, la r\u00e9ponse de cette op\u00e9ration diminue d'une unit\u00e9.<\/li>\n<\/ol>\n

      \"Comment<\/p>\n

      Il convient de noter qu'une telle approche est assez difficile \u00e0 mettre en \u0153uvre avec pr\u00e9cision en temps lin\u00e9aire. La fusion des sommets est une op\u00e9ration complexe, il faut copier les listes de voisins. Si cela n'est pas fait avec soin, on peut obtenir un temps de fonctionnement asymptotiquement sous-optimal (par exemple, si apr\u00e8s chaque fusion, beaucoup d'ar\u00eates sont copi\u00e9es). Je me suis concentr\u00e9 sur la recherche de chemins entiers \u00e0 partir de sommets de degr\u00e9 2 et sur l'analyse de nombreux cas particuliers, tels que les cycles \u00e0 partir de ces sommets ou \u00e0 partir de tous les sommets sauf un.<\/p>\n

      De plus, cette op\u00e9ration doit \u00eatre r\u00e9versible, afin qu'\u00e0 la sortie de la r\u00e9cursivit\u00e9, nous puissions restaurer le graphe dans son \u00e9tat d'origine. Pour garantir cela, je n'ai pas vid\u00e9 les listes d'ar\u00eates des sommets fusionn\u00e9s, apr\u00e8s quoi je savais simplement quelles ar\u00eates devaient \u00eatre orient\u00e9es o\u00f9. Une telle impl\u00e9mentation des graphes n\u00e9cessite \u00e9galement de la rigueur, mais offre un temps lin\u00e9aire honn\u00eate. Et pour les graphes de plusieurs dizaines de milliers d'ar\u00eates, cela tient parfaitement dans le cache du processeur, ce qui procure de grands avantages en vitesse.<\/p>\n

      Noyau lin\u00e9aire<\/h3>\n

      Enfin, la partie la plus int\u00e9ressante du noyau.<\/p>\n

      Tout d'abord, rappelons qu'il est possible de chercher un couvercle minimum de sommets dans des graphes bipartis en \"Comment. Pour cela, il faut utiliser l'algorithme de Hopcroft-Karp<\/a><\/noindex> pour trouver le maximum appariement, puis utiliser le th\u00e9or\u00e8me de K\u00f6nig-Egervari.<\/a><\/noindex>.<\/p>\n

      L'id\u00e9e du noyau lin\u00e9aire est la suivante : d'abord, nous allons bifurquer le graphe, c'est-\u00e0-dire qu'au lieu de chaque sommet v<\/i> , nous allons cr\u00e9er deux sommets \"Comment et \"Comment, et pour chaque ar\u00eate u \u2014 v<\/i> , nous allons cr\u00e9er deux ar\u00eates. \"Comment et \"Comment. Le graphe obtenu sera bipartite. Trouvons-y un couvercle de sommets minimum. Certaines sommets du graphe d'origine figureront l\u00e0 deux fois, certaines une seule fois, et certaines \u2014 jamais. Le th\u00e9or\u00e8me de Nemhauser-Trotter affirme que dans ce cas, il est possible de supprimer les sommets qui n'y figurent jamais et de prendre en r\u00e9ponse ceux qui apparaissent deux fois. De plus, il dit que parmi les sommets restants (ceux qui apparaissent une fois), il faut en prendre au moins la moiti\u00e9 en r\u00e9ponse.<\/p>\n

      Nous venons d'apprendre \u00e0 laisser dans le graphe pas plus que 2k<\/i> sommets. Et en effet, si dans le reste de la r\u00e9ponse \u2014 au moins la moiti\u00e9 de tous les sommets, alors en tout, il n'y a pas plus de sommets que 2k<\/i>.<\/p>\n

      Ici, j'ai r\u00e9ussi \u00e0 faire un petit pas en avant. Il est clair que le noyau construit de cette mani\u00e8re d\u00e9pend de quel couvercle de sommets minimum dans le graphe bipartite nous avons pris. On souhaite en choisir un de sorte que le nombre de sommets restants soit minimal. Auparavant, cela n'\u00e9tait possible que dans un temps \"Comment. J'ai cependant \u00e9labor\u00e9 une impl\u00e9mentation de cet algorithme en un temps \"Comment, ce qui permet de chercher ce noyau sur des graphes de plusieurs centaines de milliers de sommets \u00e0 chaque \u00e9tape de la branche.<\/p>\n

      R\u00e9sultat<\/h3>\n

      La pratique montre que ma solution fonctionne bien sur des tests de plusieurs centaines de sommets et plusieurs milliers d'ar\u00eates. Lors de tels tests, on peut raisonnablement s'attendre \u00e0 ce qu'une solution soit trouv\u00e9e en une demi-heure. La probabilit\u00e9 de trouver une r\u00e9ponse dans un temps acceptable augmente en principe si le graphe contient suffisamment de sommets de haute degr\u00e9, par exemple un degr\u00e9 de 10 et plus.<\/p>\n

      Pour participer \u00e0 la comp\u00e9tition, les solutions devaient \u00eatre soumises sur optil.io<\/a><\/noindex>. D'apr\u00e8s le tableau qui y est pr\u00e9sent\u00e9, ma solution se classe troisi\u00e8me sur vingt dans les tests ouverts, avec un grand \u00e9cart par rapport \u00e0 la seconde place. Pour \u00eatre tout \u00e0 fait honn\u00eate, il n'est pas compl\u00e8tement clair comment les solutions seront \u00e9valu\u00e9es lors de la comp\u00e9tition elle-m\u00eame : par exemple, ma solution passe moins de tests que celle \u00e0 la quatri\u00e8me place, mais pour ceux qu'elle passe, elle fonctionne plus rapidement.<\/a><\/noindex>Les r\u00e9sultats des tests ferm\u00e9s seront connus le premier juillet.<\/p>\n

      La recherche scientifique est sans doute la partie la plus int\u00e9ressante de notre formation. L'id\u00e9e est d'essayer, d\u00e8s l'universit\u00e9, de se lancer dans la direction choisie.<\/p>\n

      Source : 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\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\udd47Comment r\u00e9soudre des probl\u00e8mes NP-difficiles \u00e0 l'aide d'algorithmes param\u00e9tr\u00e9s | ProHoster","description":"\ud83e\udd47Comment r\u00e9soudre des probl\u00e8mes NP-difficiles \u00e0 l'aide d'algorithmes param\u00e9tr\u00e9s | ProHoster","canonical_url":"https:\/\/prohoster.info\/fr\/blog\/news\/kak-reshat-np-trudnye-zadachi-s-pomoshhyu-parametrizovannyh-algoritmov","robots":"max-image-preview:large","keywords":"","webmasterTools":{"miscellaneous":""},"schema":null,"og:locale":"fr_FR","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\/fr\/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\/fr\/wp-json\/wp\/v2\/posts\/35406","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/prohoster.info\/fr\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/prohoster.info\/fr\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/prohoster.info\/fr\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/prohoster.info\/fr\/wp-json\/wp\/v2\/comments?post=35406"}],"version-history":[{"count":0,"href":"https:\/\/prohoster.info\/fr\/wp-json\/wp\/v2\/posts\/35406\/revisions"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/prohoster.info\/fr\/wp-json\/wp\/v2\/media\/26562"}],"wp:attachment":[{"href":"https:\/\/prohoster.info\/fr\/wp-json\/wp\/v2\/media?parent=35406"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/prohoster.info\/fr\/wp-json\/wp\/v2\/categories?post=35406"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/prohoster.info\/fr\/wp-json\/wp\/v2\/tags?post=35406"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}