Set pembahagian adalah NP-lengkap

Terjemahkan masalah Set Parcel ke dalam bahasa Cina Ini adalah masalah NP-lengkap. Tugasnya adalah untuk menentukan sama ada set integer positif boleh dibahagikan kepada dua sub - menetapkan supaya jumlah mereka adalah sama. NP-lengkap bermakna tiada algoritma masa polinomial yang diketahui pada masa ini boleh menyelesaikan semua kes, dan mengesahkan penyelesaian yang mungkin perlu dilakukan dalam masa polinomial. Banyak masalah lengkap NP lain boleh dikurangkan kepada masalah Set Parcel, menunjukkan kerumitan pengiraan dan kepentingannya dalam memahami kelas masalah lengkap NP yang lebih luas. Disebabkan kerumitannya, menyelesaikan kes berskala besar bagi masalah Set Parcel boleh memerlukan pelaburan masa yang besar, yang menyukarkan untuk mencari penyelesaian optimum dengan cekap.

Kaedah Digunakan

• Brute Force

• Algoritma penjejakan belakang

Brute Force

Brute force ialah pendekatan algoritma yang mudah dan tidak bersalah untuk menyelesaikan masalah dengan menilai setiap pilih atur yang mungkin dan memilih yang betul. Ia melibatkan pengiraan dengan cekap setiap pilih atur yang mungkin dan benar-benar menyemak sama ada setiap pilih atur memenuhi keperluan masalah. Walaupun pendekatan brute-force secara konsepnya mudah dan mudah untuk dilaksanakan, ia boleh menjadi tidak cekap dari segi pengiraan dan tidak praktikal untuk masalah dengan ruang pilihatur yang besar.

Terlepas dari keterusterangannya, kuasa ganas boleh menjadi metodologi yang penting untuk isu dengan saiz maklumat yang kecil atau apabila ruang susunan secara amnya kecil dan munasabah ia digunakan secara kerap untuk isu mudah, sebagai corak untuk mengesahkan kebenaran, atau sebagai peringkat permulaan sebelum menggunakan pengiraan yang lebih moden.

Algoritma

• Kira kesempurnaan semua komponen dalam set dan semak sama ada ia boleh dibahagikan dengan 2. Jika tidak, kembalikan "Tiada penyelesaian".

• Mulakan dua set pembersihan, subset1 dan subset2.

• Panggil pembantu partition partitionHelper kerja rekursif, menggunakan set permulaan S, subset 1, subset 2 dan jumlah sasaran (totalSum / 2)

Dalam fungsi partitionHelper:

• Semak sekiranya keseluruhan komponen dalam subset 1 adalah sama dengan keseluruhan sasaran Jika begitu, cetak subset 1 dan 2, dan kembalikan. Jika set S dikosongkan, kembalikan Pilih komponen x daripada S dan buang ia daripada S.

• Cuba sertakan x dalam subset1 dan panggil partitionHelper secara rekursif dengan S, subset1, subset2 dan jumlah sasaran yang dinaik taraf.

Jika bida tidak menemui petak yang besar, kecualikan x daripada subset 1 dan cuba masukkan x dalam subset 2

• Panggil fungsi partitionHelper secara rekursif menggunakan S tersusun semula, subset 1, subset 2 dan jumlah sasaran

• Jika tiada segmen besar ditemui di tengah-tengah rekursi, cetak "Tiada susunan."

Contoh

#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;
}

Output

No solution.

Menjejak Belakang

Backtracking ialah kaedah algoritmik keseluruhan yang digunakan untuk mencari jawapan bagi isu gabungan dengan sengaja Ia adalah sejenis carian percubaan di mana pengiraan menyiasat pelbagai hasil yang boleh difikirkan, secara berterusan membina susunan yang mungkin dan menjejak ke belakang apabila ia memahami bahawa pasang surut. cara tidak boleh menggesa susunan yang besar.

Sistem penjejakan ke belakang boleh dianggap sebagai pepohon tinjauan, di mana setiap nod mewakili keputusan yang dibuat pada langkah tertentu, dan cawangan mewakili kemungkinan hasil keputusan tersebut. Algoritma merentasi pokok itu secara mendalam, meneroka setiap laluan secara bergilir-gilir sehingga ia menemui penyelesaian yang sah atau menghabiskan semua kemungkinan.

Algoritma

• Mulakan dengan dua set kosong, SetA dan SetB, untuk menangani dua subset yang sedang dibentuk.

• Siasat secara rekursif semua potensi campuran komponen daripada set tertentu untuk mengingati apa yang ada dalam SetA dan SetB

• Pada setiap langkah, tambah komponen pada SetA dan ulangi komponen tambahan, atau tambahkannya pada SetB dan ulang semula

• Pantau bilangan SetA dan SetB semasa proses rekursif

• Jika bila-bila masa, jumlah SetA meningkat kepada jumlah SetB, bawa kembali Sah dalam apa jua keadaan, kembali Mengelirukan.

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完备问题相关，为我们揭示了计算复杂问题的更广泛教训

Atas ialah kandungan terperinci Set pembahagian adalah NP-lengkap. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!