Le travail de recherche est peut-être la partie la plus intéressante de notre formation. L'idée est de vous essayer dans la direction que vous avez choisie pendant vos études universitaires. Par exemple, les étudiants des domaines du génie logiciel et du machine learning vont souvent faire des recherches dans des entreprises (principalement JetBrains ou Yandex, mais pas seulement).
Dans cet article, je parlerai de mon projet en informatique. Dans le cadre de mon travail, j'ai étudié et mis en pratique des approches pour résoudre l'un des problèmes NP-difficiles les plus connus : problème de couverture des sommets.
De nos jours, une approche intéressante des problèmes NP-difficiles se développe très rapidement : les algorithmes paramétrés. Je vais essayer de vous mettre au courant, de vous présenter quelques algorithmes paramétrés simples et de décrire une méthode puissante qui m'a beaucoup aidé. J'ai présenté mes résultats au concours PACE Challenge : selon les résultats des tests ouverts, ma solution prend la troisième place, et les résultats définitifs seront connus le 1er juillet.
À propos de moi
Je m'appelle Vasily Alferov, je termine actuellement ma troisième année à l'École supérieure d'économie de l'Université nationale de recherche de Saint-Pétersbourg. Je m'intéresse aux algorithmes depuis mes années d'école, lorsque j'ai étudié à l'école n° 179 de Moscou et que j'ai participé avec succès aux Olympiades d'informatique.
Un nombre fini de spécialistes des algorithmes paramétrés entrent dans le barreau...
Exemple tiré du livre
Imaginez que vous êtes agent de sécurité dans un bar dans une petite ville. Chaque vendredi, la moitié de la ville vient se détendre dans votre bar, ce qui vous pose bien des problèmes : vous devez expulser les clients turbulents du bar pour éviter les bagarres. Finalement, vous en avez marre et décidez de prendre des mesures préventives.
Comme votre ville est petite, vous savez exactement quels couples de clients sont susceptibles de se battre s'ils se retrouvent ensemble dans un bar. Avez-vous une liste de n des gens qui viendront au bar ce soir. Vous décidez de garder certains citadins hors du bar sans que personne ne se batte. Dans le même temps, vos patrons ne veulent pas perdre de profits et seront mécontents si vous ne leur accordez pas plus de k personnes.
Malheureusement, le problème qui se pose à vous est un problème NP-difficile classique. Vous la connaissez peut-être comme , ou comme problème de couverture de sommets. Pour de tels problèmes, dans le cas général, il n'existe pas d'algorithmes qui fonctionnent dans un délai acceptable. Pour être précis, l'hypothèse non prouvée et assez forte ETH (Exponential Time Hypothesis) dit que ce problème ne peut pas être résolu à temps. , c’est-à-dire que vous ne pouvez penser à rien de mieux qu’une recherche complète. Par exemple, disons que quelqu'un va venir dans votre bar n = 1000 Humain. Ensuite, la recherche complète sera options qu'il y a environ - une somme folle. Heureusement, votre direction vous a donné une limite k = 10, donc le nombre de combinaisons sur lesquelles vous devez parcourir est beaucoup plus petit : le nombre de sous-ensembles de dix éléments est . C'est mieux, mais cela ne se comptera toujours pas en un jour, même sur un cluster puissant.
Pour éliminer toute possibilité de bagarre dans cette configuration de relations tendues entre les visiteurs du bar, il faut exclure Bob, Daniel et Fedor. Il n’existe pas de solution dans laquelle seuls deux seraient laissés pour compte.
Cela signifie-t-il qu'il est temps de céder et de laisser tout le monde entrer ? Considérons d'autres options. Eh bien, par exemple, vous ne pouvez pas laisser entrer uniquement ceux qui sont susceptibles de se battre avec un très grand nombre de personnes. Si quelqu'un peut se battre au moins avec k+1 une autre personne, alors vous ne pouvez absolument pas la laisser entrer - sinon vous devrez exclure tout le monde k+1 des citadins, avec qui il peut se battre, ce qui va certainement bouleverser les dirigeants.
Laissez-vous jeter tous ceux que vous pouvez selon ce principe. Alors tout le monde ne pourra se battre qu'avec k personnes. Les jeter k mec, tu ne peux rien empêcher de plus que conflits. Cela signifie que s'il y a plus de Si une personne est impliquée dans au moins un conflit, vous ne pourrez certainement pas tous les empêcher. Puisque, bien sûr, vous laisserez certainement entrer des personnes totalement non conflictuelles, vous devez passer par tous les sous-ensembles de taille dix sur deux cents personnes. Il y a environ , et ce nombre d'opérations peut déjà être trié sur le cluster.
Si vous pouvez prendre en toute sécurité des individus qui n’ont aucun conflit, alors qu’en est-il de ceux qui ne participent qu’à un seul conflit ? En fait, ils peuvent aussi se laisser entrer en fermant la porte à leur adversaire. En effet, si Alice n'est en conflit qu'avec Bob, alors si nous laissons Alice sortir des deux, nous ne perdrons pas : Bob a peut-être d'autres conflits, mais Alice n'en a certainement pas. De plus, cela n’a aucun sens pour nous de ne pas nous laisser entrer tous les deux. Après de telles opérations, il ne reste plus des invités au sort non résolu : nous n'avons que conflits, chacun avec deux participants et chacun impliqué dans au moins deux. Il ne reste donc plus qu'à faire le tri options, qui peuvent facilement être envisagées une demi-journée sur un ordinateur portable.
En fait, avec un raisonnement simple, vous pouvez obtenir des conditions encore plus attractives. Notez que nous devons absolument résoudre tous les différends, c'est-à-dire que parmi chaque paire en conflit, choisir au moins une personne que nous ne laisserons pas entrer. Considérons l'algorithme suivant : prenons n'importe quel conflit, dont nous supprimons un participant et recommençons récursivement à partir du reste, puis supprimons l'autre et recommençons également récursivement. Puisque nous expulsons quelqu'un à chaque étape, l'arbre de récursion d'un tel algorithme est un arbre binaire de profondeur k, donc au total l'algorithme fonctionne dans Où n est le nombre de sommets, et m - nombre de côtes. Dans notre exemple, cela représente environ dix millions, qui peuvent être calculés en une fraction de seconde non seulement sur un ordinateur portable, mais même sur un téléphone portable.
L'exemple ci-dessus est un exemple algorithme paramétré. Les algorithmes paramétrés sont des algorithmes qui s'exécutent dans le temps f(k)poly(n)Où p - polynôme, f est une fonction calculable arbitraire, et k - un paramètre qui, très probablement, sera beaucoup plus petit que la taille du problème.
Tout le raisonnement avant cet algorithme donne un exemple kernelisation est l'une des techniques générales de création d'algorithmes paramétrés. La Kernelisation est la réduction de la taille du problème à une valeur limitée par une fonction d'un paramètre. Le problème qui en résulte est souvent appelé noyau. Ainsi, par un simple raisonnement sur les degrés des sommets, nous avons obtenu un noyau quadratique pour le problème Vertex Cover, paramétré par la taille de la réponse. Il existe d'autres paramètres que vous pouvez choisir pour cette tâche (tels que Vertex Cover Above LP), mais c'est ce paramètre dont nous allons discuter.
Défi de rythme
Concours (The Parameterized Algorithms and Computational Experiments Challenge) est né en 2015 pour établir un lien entre les algorithmes paramétrés et les approches utilisées en pratique pour résoudre des problèmes informatiques. Les trois premiers concours étaient consacrés à trouver la largeur de l'arbre d'un graphe (), à la recherche d'un arbre de Steiner () et rechercher un ensemble de sommets qui coupent les cycles (). Cette année, l'un des problèmes auxquels vous avez pu vous essayer était le problème de couverture des sommets décrit ci-dessus.
Le concours gagne en popularité chaque année. Si l'on en croit les données préliminaires, cette année, 24 équipes ont participé à la compétition pour résoudre seules le problème de la couverture des sommets. Il est à noter que le concours ne dure pas plusieurs heures ni même une semaine, mais plusieurs mois. Les équipes ont la possibilité d'étudier la littérature, de proposer leur propre idée originale et d'essayer de la mettre en œuvre. Essentiellement, ce concours est un projet de recherche. Des idées pour les solutions les plus efficaces et la remise des gagnants auront lieu parallèlement à la conférence. (International Symposium on Parameterized and Exact Computation) dans le cadre du plus grand congrès annuel d'algorithmique en Europe . Des informations plus détaillées sur le concours lui-même peuvent être trouvées sur , et les résultats des années précédentes se situent .
Schéma de solution
Pour résoudre le problème de couverture des sommets, j'ai essayé d'utiliser des algorithmes paramétrés. Elles se composent généralement de deux parties : les règles de simplification (qui conduisent idéalement à la kernelisation) et les règles de fractionnement. Les règles de simplification sont un prétraitement de l'entrée en temps polynomial. Le but de l’application de telles règles est de réduire le problème à un problème équivalent plus petit. Les règles de simplification sont la partie la plus coûteuse de l'algorithme, et l'application de cette partie conduit au temps d'exécution total au lieu d'un simple temps polynomial. Dans notre cas, les règles de division sont basées sur le fait que pour chaque sommet, vous devez prendre soit celui-ci, soit son voisin comme réponse.
Le schéma général est le suivant : nous appliquons les règles de simplification, puis nous sélectionnons un sommet et effectuons deux appels récursifs : dans le premier nous le prenons en réponse, et dans l'autre nous prenons tous ses voisins. C'est ce que nous appelons le fractionnement (ramification) le long de ce sommet.
Exactement un ajout sera apporté à ce schéma dans le paragraphe suivant.
Idées de règles de fractionnement (brunch)
Voyons comment choisir un sommet le long duquel la division se produira.
L'idée principale est très gourmande au sens algorithmique : prenons un sommet de degré maximum et divisons-le le long de celui-ci. Pourquoi ça semble mieux ? Parce que dans la deuxième branche de l’appel récursif, nous supprimerons ainsi beaucoup de sommets. Vous pouvez compter sur un petit graphique restant et nous pouvons y travailler rapidement.
Cette approche, avec les techniques de kernelisation simples déjà évoquées, se montre bien et résout certains tests de plusieurs milliers de sommets. Mais, par exemple, cela ne fonctionne pas bien pour les graphes cubiques (c'est-à-dire les graphes dont le degré de chaque sommet est de trois).
Il existe une autre idée basée sur une idée assez simple : si le graphique est déconnecté, le problème sur ses composantes connectées peut être résolu indépendamment, en combinant les réponses à la fin. Il s'agit d'ailleurs d'une petite modification promise dans le schéma, qui accélérera considérablement la solution : auparavant, dans ce cas, nous travaillions sur le produit des temps pour calculer les réponses des composants, mais maintenant nous travaillons sur la somme. Et pour accélérer le branchement, vous devez transformer un graphique connecté en un graphique déconnecté.
Comment faire? S’il y a un point d’articulation dans le graphique, vous devez vous y battre. Un point d'articulation est un sommet tel que lorsqu'il est supprimé, le graphe perd sa connectivité. Tous les points de jonction d’un graphe peuvent être trouvés à l’aide d’un algorithme classique en temps linéaire. Cette approche accélère considérablement le branchement.
Lorsque l'un des sommets sélectionnés est supprimé, le graphique est divisé en composants connectés.
Nous le ferons, mais nous en voulons plus. Par exemple, recherchez de petites coupes de sommets dans le graphique et divisez-les le long des sommets. Le moyen le plus efficace que je connaisse pour trouver la coupe minimale de sommet global est d'utiliser un arbre Gomori-Hu, qui est construit en temps cube. Dans le défi PACE, la taille typique d’un graphique est de plusieurs milliers de sommets. Dans cette situation, des milliards d’opérations doivent être effectuées à chaque sommet de l’arbre de récursivité. Il s'avère qu'il est tout simplement impossible de résoudre le problème dans le temps imparti.
Essayons d'optimiser la solution. Le sommet minimum coupé entre une paire de sommets peut être trouvé par n'importe quel algorithme qui construit un flux maximum. Vous pouvez le laisser sur un tel réseau , en pratique cela fonctionne très vite. Je soupçonne qu'il est théoriquement possible de prouver une estimation du temps de fonctionnement , ce qui est déjà tout à fait acceptable.
J'ai essayé plusieurs fois de rechercher des coupes entre des paires de sommets aléatoires et de prendre celui le plus équilibré. Malheureusement, cela a produit de mauvais résultats lors des tests ouverts du PACE Challenge. Je l'ai comparé à un algorithme qui divise les sommets d'un degré maximum, en les exécutant avec une limitation de la profondeur de descente. Un algorithme essayant de trouver une coupure de cette manière a laissé des graphiques plus grands. Cela est dû au fait que les coupes se sont révélées très déséquilibrées : après avoir supprimé 5 à 10 sommets, il n'a été possible d'en séparer que 15 à 20.
Il convient de noter que les articles sur les algorithmes théoriquement les plus rapides utilisent des techniques beaucoup plus avancées pour sélectionner les sommets à diviser. De telles techniques ont une mise en œuvre très complexe et des performances souvent médiocres en termes de temps et de mémoire. Je n'ai pas pu identifier ceux qui sont tout à fait acceptables pour la pratique.
Comment appliquer les règles de simplification
Nous avons déjà des idées pour la kernelisation. Laisse-moi te rappeler:
- S'il existe un sommet isolé, supprimez-le.
- S'il existe un sommet de degré 1, supprimez-le et prenez son voisin en réponse.
- S'il existe au moins un sommet de degré k+1, reprends-le.
Avec les deux premiers, tout est clair, avec le troisième il y a un truc. Si, dans un problème comique concernant un bar, on nous donnait une limite supérieure de k, puis dans le PACE Challenge, il vous suffit de trouver une couverture de sommet de la taille minimale. Il s’agit d’une transformation typique des problèmes de recherche en problèmes de décision ; il n’y a souvent aucune différence entre les deux types de problèmes. En pratique, si nous écrivons un solveur pour le problème de couverture de sommets, il peut y avoir une différence. Par exemple, comme au troisième point.
Du point de vue de la mise en œuvre, il existe deux manières de procéder. La première approche est appelée approfondissement itératif. C'est le suivant : nous pouvons commencer avec une contrainte raisonnable d'en bas sur la réponse, puis exécuter notre algorithme en utilisant cette contrainte comme contrainte sur la réponse d'en haut, sans descendre en récursion plus bas que cette contrainte. Si nous avons trouvé une réponse, elle est garantie d'être optimale, sinon nous pouvons augmenter cette limite d'un et recommencer.
Une autre approche consiste à stocker une réponse optimale actuelle et à rechercher une réponse plus petite, en modifiant ce paramètre une fois trouvé. k pour une meilleure suppression des branches inutiles dans la recherche.
Après avoir mené plusieurs expériences nocturnes, j'ai opté pour une combinaison de ces deux méthodes : d'abord, j'exécute mon algorithme avec une sorte de limite sur la profondeur de recherche (en le sélectionnant pour qu'il prenne un temps négligeable par rapport à la solution principale) et j'utilise la meilleure solution trouvée comme limite supérieure de la réponse, c'est-à-dire de la même chose k.
Sommets de degré 2
Nous avons traité des sommets de degré 0 et 1. Il s'avère que cela peut être fait avec des sommets de degré 2, mais cela nécessitera des opérations plus complexes à partir du graphique.
Pour expliquer cela, nous devons désigner les sommets d’une manière ou d’une autre. Appelons un sommet de degré 2 un sommet v, et ses voisins - sommets x и y. Nous aurons ensuite deux cas.
- Quand x и y - voisins. Ensuite tu pourras répondre x и yEt v supprimer. En effet, de ce triangle il faut prendre au moins deux sommets en retour, et nous ne perdrons certainement pas si nous prenons x и y: ils ont probablement d'autres voisins, et v ils ne le sont pas.
- Quand x и y - pas des voisins. Ensuite, il est indiqué que les trois sommets peuvent être regroupés en un seul. L’idée est que dans ce cas il existe une réponse optimale, dans laquelle on prend soit v, ou les deux sommets x и y. De plus, dans le premier cas, nous devrons prendre tous les voisins en réponse x и y, mais dans le second, ce n'est pas nécessaire. Cela correspond exactement aux cas où on ne prend pas le sommet collé en réponse et où on le fait. Il ne reste plus qu'à constater que dans les deux cas la réponse à une telle opération diminue de un.
Il convient de noter que cette approche est assez difficile à mettre en œuvre avec précision en un temps linéaire équitable. Coller des sommets est une opération complexe ; vous devez copier des listes de voisins. Si cela est fait avec négligence, vous pouvez vous retrouver avec un temps d'exécution asymptotiquement sous-optimal (par exemple, si vous copiez beaucoup d'arêtes après chaque collage). J'ai décidé de trouver des chemins entiers à partir de sommets de degré 2 et d'analyser un tas de cas particuliers, tels que des cycles à partir de tels sommets ou à partir de tous ces sommets sauf un.
De plus, il faut que cette opération soit réversible, pour qu'au retour de la récursion on redonne au graphe sa forme originale. Pour garantir cela, je n'ai pas effacé les listes d'arêtes des sommets fusionnés, et je savais simplement quelles arêtes devaient aller où. Cette implémentation de graphiques nécessite également de la précision, mais elle fournit un temps linéaire juste. Et pour les graphiques de plusieurs dizaines de milliers d'arêtes, il s'insère dans le cache du processeur, ce qui donne de gros avantages en termes de rapidité.
Noyau linéaire
Enfin, la partie la plus intéressante du noyau.
Pour commencer, rappelons que dans les graphes bipartis, la couverture minimale des sommets peut être trouvée en utilisant . Pour ce faire, vous devez utiliser l'algorithme afin d'y trouver la correspondance maximale, puis d'utiliser le théorème .
L'idée d'un noyau linéaire est la suivante : on bifurque d'abord le graphe, c'est-à-dire au lieu de chaque sommet v ajoutons deux sommets и , et au lieu de chaque bord tu - v ajoutons deux côtes и . Le graphe résultant sera biparti. Trouvons-y la couverture minimale des sommets. Certains sommets du graphe d'origine y parviendront deux fois, d'autres une seule fois et d'autres jamais. Le théorème de Nemhauser-Trotter stipule que dans ce cas, on peut supprimer les sommets qui n'ont pas frappé une seule fois et reprendre ceux qui ont frappé deux fois. De plus, elle dit que parmi les sommets restants (ceux qui ont frappé une fois), vous devez en prendre au moins la moitié comme réponse.
Nous venons d'apprendre à ne laisser que 2k pics En effet, si la réponse du reste est au moins la moitié de tous les sommets, alors il n’y a pas plus de sommets au total que 2k.
Ici, j’ai pu faire un petit pas en avant. Il est clair que le noyau construit de cette manière dépend du type de couverture minimale de sommets que nous avons pris dans le graphe biparti. Je voudrais en prendre un pour que le nombre de sommets restants soit minime. Auparavant, ils ne pouvaient le faire qu'à temps . J'ai proposé une implémentation de cet algorithme à l'époque , ainsi, ce noyau peut être recherché dans des graphiques de centaines de milliers de sommets à chaque étape de branchement.
Résultat
La pratique montre que ma solution fonctionne bien sur des tests de plusieurs centaines de sommets et de plusieurs milliers d'arêtes. Dans de tels tests, il est tout à fait possible de s'attendre à ce qu'une solution soit trouvée en une demi-heure. La probabilité de trouver une réponse dans un délai acceptable augmente en principe si le graphique comporte un nombre suffisamment grand de sommets de degré élevé, par exemple de degré 10 et supérieur.
Pour participer au concours, les solutions devaient être envoyées à . À en juger par les informations qui y sont présentées , ma solution dans les tests ouverts se classe troisième sur vingt, avec un écart important par rapport à la deuxième. Pour être tout à fait honnête, il n'est pas tout à fait clair comment les solutions seront évaluées lors du concours lui-même : par exemple, ma solution réussit moins de tests que la solution classée quatrième, mais sur celles qui réussissent, elle fonctionne plus rapidement.
Les résultats des tests fermés seront connus le XNUMXer juillet.
Source: habr.com