Probablement, chacun était confronté au fait qu'il devait faire face à une tâche difficile, à laquelle la solution ne pouvait pas être trouvée, non seulement tout de suite - mais même après de longues heures de travail ou des jours tenaces. Aujourd'hui, nous allons parler de l'une des classes de ces problèmes - NP-complet.
En général, est-il réaliste d'accomplir de telles tâches dans la vie quotidienne? En fait, ils surviennent dans un grand nombre de cas: combinatoire, graphes et réseaux, exécution de formules logiques, travail avec des cartes, des chargements optimaux, des cartes, des problèmes d'optimisation discrets, trouver les séquences les plus longues, trouver des sommes égales, et de nombreux problèmes d'ensemble! Et ce n'est pas une liste complète.
Sous la coupe se trouve un guide informel - comment comprendre que vous pouvez avoir un problème NP devant vous et que faire si c'est ce qu'il s'est avéré être. Aujourd'hui, nous attaquons cette question d'un point de vue pratique.
Assurez-vous qu'elle est vraiment en face de vous
Comment savez-vous que vous êtes confronté à un problème NP-complet? Premièrement, l'heuristique de détection la plus simple est une recherche à travers des problèmes NP-complets déjà connus afin de déterminer quelque chose de similaire, il existe de nombreuses listes de ce type, par exemple .
Deuxièmement, considérez les propriétés suivantes des tâches:
- Nous devons choisir une solution dans laquelle n éléments de l'espace exp (n)
- Si vous avez déjà une solution de longueur n à partir de cet espace, elle peut être facilement vérifiée (polynomialement)
- Le choix de l'un des éléments de décision (peut) influer sur le choix de tous les autres (pas nécessairement tous).
- Dans le pire des cas, les options peuvent toujours être énumérées, en considérant l'espace exponentiel entier par une simple énumération.
- Les paramètres n - la longueur de la solution ou l'espace lui-même n'ont pas de valeur fixe, c'est-à-dire que nous ne parlons pas de l'échiquier toujours fixé 8 par 8, mais de la forme générale du problème N-par-N.
En savoir plus sur les propriétés des problèmes NP-complets ici et ici .
Un exemple de travail sur cette liste
Donnons un exemple simple sur un problème qui a été récemment approuvé comme NP-complete!
Basé sur les matériaux de l'article. Vous devez placer N reines sur une planche de taille N par N, à condition que déjà K <= N soient placées sur la planche (photo de l'article scientifique original)
Tout d'abord, notez qu'un problème très similaire avec les carrés latins NP partiellement contraints est complet.
Et puis nous parcourons la liste:
- Vous devez trouver N reines sur à partir de l'espace exp (N) (= N ^ 2 * (N ^ 2-1) * ....).
- La solution de N reines est vérifiée de manière triviale - pour chaque reine, vous devez vérifier les diagonales, les verticales et les lignes horizontales.
- Un réglage rend le choix d'un certain nombre d'autres invalide - c.-à-d. il existe des dépendances entre les éléments de la solution (vous ne pouvez pas organiser les reines indépendamment).
- Ici, vous pouvez résoudre le problème par force brute pour un tableau choisi arbitrairement dans exp (N) - nous plaçons le premier dans le premier sur la position (i, j), le second sur tout autre tableau inoccupé, etc. Le retour en arrière est garanti pour trouver une solution.
- Le problème n'a pas de paramètres fixes - c'est-à-dire qu'il est formulé sous une forme générale et à mesure que N croît, la complexité augmente également.
Notez que l'un des éléments de la liste échoue s'il est toujours connu que le tableau est propre et que la tâche devient triviale.
De plus, il s'agit d'une approche pratique conditionnelle - une heuristique pour détecter les problèmes NP-complets (avec tous les avantages et inconvénients).
Mélange
Source
Pourquoi, ayant sous la main des problèmes similaires, il n'est pas facile de comprendre formellement que nous avons un problème NP? Nous devons vraiment faire passer le problème NP au nôtre, alors nous saurons avec certitude que notre problème est NP-difficile! Et si nous avons pu le simuler, comme dans la liste ci-dessus, alors il est complet - c'est-à-dire au moins NP et pas plus que NP, en fait «le plus difficile parmi les problèmes NP» (comme le reste du NP-complet).
D'accord, en avons-nous besoin? Pas vraiment, si vous êtes simple, après toutes les vérifications, que vous êtes confronté à un problème NP, alors vous n'avez rien à prouver si vous n'écrivez pas un article scientifique.
Et vous avez besoin de l'un ou l'autre (nous en parlerons ci-dessous):
- simulez votre tâche à l'aide de systèmes qui résolvent de telles tâches;
- trouver une solution qui fonctionne assez rapidement dans votre cas;
- trouver une solution approximative qui nous satisfera.
N'abandonnez pas!
Le plus important est d'évaluer les dimensions-paramètres et des scénarios réalistes!
xkcd.com/287
Par exemple, vous savez que malgré le fait que les valeurs des paramètres ne soient pas fixes, le conditionnel N <100 n'est pas implémenté dans tous les scénarios pratiques, ce qui signifie que l'énumération conditionnelle peut être une vraie solution pour vous.
Vous devez déterminer vous-même: quelles valeurs réelles des paramètres sont possibles et entrent réellement dans le système, quelle est la distribution générale et les caractéristiques des données, qu'est-ce qui est réel et qu'est-ce qui ne l'est pas? Avons-nous besoin de la solution la plus optimale? Passons en revue ces points.
Distribution des données d'entrée
Ou malgré le fait que, dans le cas général, les données d'entrée peuvent être n'importe lesquelles, mais encore une fois en utilisant l'exemple des reines - généralement une reine est fixe ou même aucune. Cela signifie que 90% du temps, vous pouvez utiliser une solution très simple et n'appeler une solution complexe que dans des cas extrêmes.
Un exemple où, en moyenne, toutes les combinaisons habituelles sont simples: le problème de la complémentarité des reines - nous savons que l'heuristique DFS + conditionnelle peut dans la plupart des cas trouver des solutions très rapidement, et seulement dans des situations très atypiques peut être extrêmement difficile.
Voici un exemple de la façon dont la solution d'un problème de pavage NP-complet très spécialisé a été évaluée par rapport à une méthode générale de modélisation de toute une classe de tels problèmes à l'aide de méthodes de programmation logique:
(extrait de l'article Factorisation des données relationnelles (Paramonov, Sergey; van Leeuwen, Matthijs; De Raedt, Luc: Factorisation des données relationnelles, Machine Learning, volume 106))
Premièrement, la vitesse de la solution spéciale LTM-k et la méthode générale sont très différentes. Ainsi, une solution heuristique pour ce type de problème peut résoudre complètement ce problème.
Deuxièmement, en sacrifiant la qualité de la solution, la méthode d'approximation générale a donné une vitesse très similaire.
Heuristique et approximation
Le dernier et le plus puissant outil consiste à utiliser des systèmes de modélisation de problèmes NP-complets tels que Answer Set Programming .
En savoir plus sur les langages de programmation logiques.
Par exemple, la solution au problème de placement des reines ressemblera à ceci:
% domain
row(1..n).
column(1..n).
% alldifferent: guess a solution
1 { queen(X,Y) : column(Y) } 1 :- row(X).
1 { queen(X,Y) : row(X) } 1 :- column(Y).
% remove conflicting answers: check this solution
:- queen(X1,Y1), queen(X2,Y2), X1 < X2, Y1 == Y2.
:- queen(X1,Y1), queen(X2,Y2), X1 < X2, Y1 + X1 == Y2 + X2.
:- queen(X1,Y1), queen(X2,Y2), X1 < X2, Y1 - X1 == Y2 - X2.
Après avoir effectué une expérience simple pour trouver des solutions pour un nombre différent de reines N, nous obtenons ce qui suit: le long de l'axe X - reines, le long de Y - le temps par seconde pour trouver une solution:
Nous voyons que malgré le fait que la croissance du temps n'est clairement pas polynomiale (ce qui est logique), nous faisons du bon travail avec un nombre adéquat de reines et de tailles de planches.
Ensuite, si nous savons quelles tailles de cartes sont réelles pour nous, nous pouvons comprendre comment cette solution exacte est acceptable pour nous dans un système réel.
conclusions
Passons en revue les idées de l'article sous forme de check-list
- Déterminez que vous avez vraiment un problème de NP.
- Comprenez quelles sont les valeurs de paramètres réalistes et la distribution des données.
- Essayez d'écrire (l'ordre dépend du développeur et / ou de la tâche):
- Une solution heuristique précise (basée sur notre analyse) - sera-t-elle assez rapide?
- — ?
- NP- — ? , CPU ? .
- : , .
- — , — . !
:
