Définir le partitionnement est NP-complet

Traduisez le problème Set Parcel en chinois. Il s'agit d'un problème NP-complet. La tâche consiste à déterminer si un ensemble donné d'entiers positifs peut être divisé en deux sous-ensembles de telle sorte que leurs sommes soient égales. NP-complet signifie qu'aucun algorithme en temps polynomial actuellement connu ne peut résoudre tous les cas, et la vérification d'une solution possible doit être effectuée en temps polynomial. De nombreux autres problèmes NP-complets peuvent être réduits au problème Set Parcel, démontrant sa complexité informatique et son importance dans la compréhension de la classe plus large des problèmes NP-complets. En raison de sa complexité, la résolution de cas à grande échelle du problème Set Parcel peut nécessiter un investissement de temps considérable, ce qui rend difficile la recherche efficace d'une solution optimale.

Méthodes utilisées

• Force Brute

• Algorithme de retour en arrière

Force Brute

La force brute est une approche algorithmique simple et innocente pour résoudre un problème en évaluant toutes les permutations possibles et en choisissant la bonne. Cela implique d’énumérer efficacement toutes les permutations possibles et de vérifier réellement si chaque permutation répond aux exigences du problème. Bien que l’approche par force brute soit conceptuellement simple et facile à mettre en œuvre, elle peut s’avérer inefficace sur le plan informatique et peu pratique pour les problèmes liés aux grands espaces de permutation.

Indépendamment de sa simplicité, la puissance sauvage peut être une méthode importante pour les problèmes avec peu d'informations ou lorsque l'espace d'arrangement est généralement petit et raisonnable. Elle est régulièrement utilisée pour des problèmes simples, comme modèle pour confirmer l'exactitude ou comme étape de départ. avant d'appliquer des calculs plus modernes.

Algorithme

• Calculez l'exhaustivité de tous les composants de l'ensemble et vérifiez s'ils sont divisibles par 2. Sinon, renvoyez "Aucune solution".

• Initialisez deux ensembles de purge, subset1 et subset2.

• Appelez l'assistant de partitionnement de travail récursif partitionHelper, en utilisant l'ensemble de départ S, le sous-ensemble 1, le sous-ensemble 2 et le total cible (totalSum / 2)

Dans la fonction partitionHelper :

• Vérifiez si l'intégralité des composants du sous-ensemble 1 est égale à l'ensemble cible. Si tel est le cas, imprimez les sous-ensembles 1 et 2 et revenez. Si l'ensemble S est effacé, retournez Choisissez le composant x de S et expulsez-le de S.

• Essayez d'inclure x dans le sous-ensemble1 et d'appeler partitionHelper de manière récursive avec le S, le sous-ensemble1, le sous-ensemble2 mis à niveau et la somme cible.

Si l'offre ne trouve pas de grande parcelle, excluez x du sous-ensemble 1 et essayez d'inclure x dans le sous-ensemble 2.

• Appelez de manière récursive la fonction partitionHelper en utilisant le S réorganisé, le sous-ensemble 1, le sous-ensemble 2 et la somme cible

• Si aucun segment substantiel n'est trouvé au milieu de la récursion, imprimez "Aucun arrangement".

Exemple

#include <iostream>
#include <vector>

bool partitionHelper(std::vector<int> S, std::vector<int>& 
subset1, std::vector<int>& subset2, int targetSum) {
   if (targetSum == 0) {
      std::cout << "Subset 1: ";
      for (int num : subset1) {
         std::cout << num << " ";
      }
      std::cout << "\nSubset 2: ";
      for (int num : subset2) {
         std::cout << num << " ";
      }
      return true;
   }

   if (S.empty()) {
      return false;
   }

   int x = S.back();
   S.pop_back();

   subset1.push_back(x);
   if (partitionHelper(S, subset1, subset2, targetSum - x)) {
      return true;
   }
   subset1.pop_back();

   subset2.push_back(x);
   if (partitionHelper(S, subset1, subset2, targetSum - x)) {
      return true;
   }
   subset2.pop_back();

   return false;
}

void partition(const std::vector<int>& S) {
   int totalSum = 0;
   for (int num : S) {
      totalSum += num;
   }
   if (totalSum % 2 != 0) {
      std::cout << "No solution.\n";
      return;
   }

   std::vector<int> subset1, subset2;
   int targetSum = totalSum / 2;

   if (!partitionHelper(S, subset1, subset2, targetSum)) {
      std::cout << "No solution.\n";
   }
}

int main() {
   std::vector<int> set = {1, 2, 3, 4, 5, 6};
   partition(set);
   return 0;
}

Sortie

No solution.

Retour en arrière

Le backtracking est une méthode algorithmique globale utilisée pour rechercher délibérément des réponses à des problèmes combinatoires. Il s'agit d'un type de recherche expérimentale dans laquelle le calcul étudie divers résultats imaginables, construisant progressivement un arrangement possible et faisant marche arrière lorsqu'il comprend que le flux et le reflux peuvent' Cela ne donne pas lieu à un arrangement substantiel.

Un système de backtracking peut être imaginé comme un arbre d'enquête, où chaque nœud représente une décision prise à une étape spécifique, et les branches représentent les résultats potentiels de cette décision. L'algorithme parcourt l'arbre en profondeur, explorant chaque chemin tour à tour jusqu'à ce qu'il trouve une solution valide ou épuise toutes les possibilités.

Algorithme

• Commencez par deux ensembles vides, SetA et SetB, pour traiter les deux sous-ensembles en cours de mise en forme.

• Étudiez de manière récursive tous les mélanges potentiels de composants d'un ensemble donné afin de vous rappeler ce qu'il y a dans SetA et SetB

• À chaque étape, ajoutez un composant à SetA et récurez sur les composants supplémentaires, ou ajoutez-le à SetB et récurez

• Surveillez le nombre de SetA et SetB pendant la récursion

• Si à tout moment, le montant de SetA atteint le montant de SetB, ramenez Valid dans tous les cas, revenez Trompeur.

Example

#include <iostream>
#include <vector>

bool isValidSubset(const std::vector<int>& inputSet, int index, int 
setSizeA, int setSizeB) {
   if (index == inputSet.size()) {
      return (setSizeA == setSizeB);
   }

   bool isValid = isValidSubset(inputSet, index + 1, setSizeA + 1, setSizeB);
   isValid |= isValidSubset(inputSet, index + 1, setSizeA, setSizeB + 1);

   return isValid;
}

int main() {
   std::vector<int> inputSet = {1000, 2000, 3000, 4000, 5000};
   bool isValid = isValidSubset(inputSet, 0, 0, 0);
   std::cout << (isValid ? "Valid" : "Misleading") << std::endl;
   return 0;
}

输出

Misleading

结论

本文研究了集合分割问题的NP完备性，该问题包括决定给定的一组正整数是否可以被分割成两个子集，使得它们的和相等。NP完备性意味着没有已知的多项式时间算法可以解决该问题的所有情况，并且验证一个潜在解决方案可以在多项式时间内完成。本文讨论了三种方法来解决这个问题：蛮力法、回溯法和动态规划。由于其复杂性，解决集合分割问题的大规模实例可能需要大量的时间和努力，使得寻找一个理想的解决方案变得具有挑战性。理解集合分割的复杂性很重要，因为它与其他NP完备问题相关，为我们揭示了计算复杂问题的更广泛教训

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!