Кіріспе
Компьютерлік ғылымдағы NP толық проблемасы
Сандар теориясы мен компьютерлік ғылымда, бөлу проблемасы немесе санды бөлу – бұл оң бүтін сандардың берілген көп жиынтығы S-ті екі кіші жиынтыққа, S1 және S2, бөлуге бола ма, жоқ па, анықтау міндеті, мұнда S1 жиынтығындағы сандардың қосындысы S2 жиынтығындағы сандардың қосындысына тең болады. Бөлу проблемасы NP толық болғанымен, псевдополиномдық уақытты динамикалық бағдарламалау шешімі бар, сондай-ақ мәселені көптеген жағдайларда оңтайлы немесе жуықтап шешетін эвристикалар бар. Осы себепті, оны "ең оңай қиын проблема" деп атайды. Бөлу проблемасының оптимизациялық түрі де бар, ол S көп жиынтығын S1, S2 екі кіші жиынтығына бөлуді қарастырады, S1 жиынтығындағы элементтердің қосындысы мен S2 жиынтығындағы элементтердің қосындысы арасындағы айырмашылықты ең төменгі деңгейге дейін азайтуды мақсат етеді. Оптимизациялық түрі NP қиын, бірақ тәжірибеде тиімді шешуге болады. Бөлу проблемасы екі байланысты проблеманың ерекше жағдайы болып табылады:
In number theory and computer science, the partition problem, or number partitioning, is the task of deciding whether a given multiset S of positive integers can be partitioned into two subsets S1 and S2 such that the sum of the numbers in S1 equals the sum of the numbers in S2. Although the partition problem is NP complete, there is a pseudo polynomial time dynamic programming solution, and there are heuristics that solve the problem in many instances, either optimally or approximately. For this reason, it has been called "the easiest hard problem". There is an optimization version of the partition problem, which is to partition the multiset S into two subsets S1, S2 such that the difference between the sum of elements in S1 and the sum of elements in S2 is minimized. The optimization version is NP hard, but can be solved efficiently in practice. The partition problem is a special case of two related problems:
Кіші жиынның қосындысы (subset sum) проблемасында мақсат – S жиынтығынан белгілі бір мақсатты сан T-ге тең болатын кіші жиынды табу (бөлу проблемасы – T, S жиынтығының жарты сомасына тең болатын ерекше жағдай). Көп жолды санды бөлуде (multiway number partitioning) k бүтін сан параметрі бар, және мақсат – S-ті тең сомалы k кіші жиынтыққа бөлуге бола ма, жоқ па, анықтау (бөлу проблемасы – k = 2 болатын ерекше жағдай). Алайда, бұл 3 бөлу (3-partition) проблемасынан мүлдем өзгеше: сол проблемада кіші жиынтықтардың саны алдын ала белгіленбеген – ол |S|/3-ке тең болуы керек, мұнда әрбір кіші жиынтықта дәл 3 элемент болуы тиіс. 3 бөлу, бөлуден әлдеқайда қиын – егер P = NP болмаса, оның псевдополиномдық уақыт алгоритмі жоқ.
Мысалдар
S = {3,1,1,2,2,1} берілген болса, бөлу мәселесіне дұрыс шешім – S1 = {1,1,1,2} және S2 = {2,3} жиынтықтары. Екі жиынтықтың қосындысы да 5-ке тең, және олар S жиынтығын екіге бөледі. Бұл шешім жалғыз емес екенін ескеріңіз. S1 = {3,1,1} және S2 = {2,2,1} – тағы бір шешім. Оң бүтін сандардың кез келген көп жиынтығын тең сомалы екі қосалқы жиынтыққа бөлу мүмкін емес. Мұндай жиынға мысал: S = {2,5}.
Есептеулік қаттылық
Партициялау мәселесі NP-қиын. Бұл мәселені SubsetSum мәселесінен азайту арқылы дәлелдеуге болады. SubsetSum мысалы оң бүтін сандардың S жиынынан және мақсатты T санынан тұрады; мақсат – S жиынының дәл T санына тең болатын кіші жиынының бар-жоғын анықтау.
Мұндай мысал берілген болса, кіріс жиынында бастапқы жиынтық пен екі элементі бар Partition мысалын құрастырыңыз: z1 және z2, мұнда z1 = sum(S) және z2 = 2T. Бұл кіріс жиынының қосындысы sum(S) + z1 + z2 = 2sum(S) + 2T, сондықтан Partition үшін мақсатты қосынды sum(S) + T.
SubsetSum мысалына S′ шешімі бар деп есептейік. Онда sum(S′) = T, демек sum(S′ + z1) = sum(S) + T, сондықтан S′ + z1 Partition мысалының шешімі болады. Керісінше, Partition мысалына S′′ шешімі бар деп болжайық. Онда S′′ құрамында z1 немесе z2 болуы керек, бірақ екеуі де емес, өйткені олардың қосындысы sum(S) + T-дан артық. Егер S′′ құрамында z1 болса, онда ол дәл T қосындысы бар S элементтерін қамтуы керек, сондықтан S′′ минус z1 SubsetSum мысалының шешімі болады. Егер S′′ құрамында z2 болса, онда ол S элементтерін қамтуы керек, олардың қосындысы дәл sum(S) - T-қа тең, сондықтан S-дегі қалған элементтер SubsetSum мысалының шешімі болады.
Тарату алгоритмдері
Жоғарыда айтылғандай, бөлу мәселесі көп жолды бөлудің және қосалқы жиынның сомасының ерекше жағдайы болып табылады. Сондықтан, оны осы мәселелер үшін әзірленген алгоритмдер арқылы шешуге болады. Көп жолды сандарды бөлуге арналған алгоритмдерге мыналар кіреді: Ашкөз сандарды бөлу – сандарды тізбектеп қарап, әр санды қазіргі сомасы ең кіші жиынға қояды. Егер сандар сұрыпталмаған болса, орындалу уақыты O(n) және шамалау қатынасы ең көп дегенде 3/2 ("шамалау қатынасы" – алгоритм нәтижесіндегі үлкен соманың, оптималды бөлістегі үлкен сомаға қатынасы). Сандарды сұрыптау орындалу уақытын O(n log n) дейін ұзартады және шамалау қатынасын 7/6-ға дейін жақсартады. Егер сандар [0,1] аралығында біркелкі таратылған болса, онда шамалау қатынасы ең көп дегенде, және күтуде болады. Ең үлкен айырмалау әдісі (Кармакар–Карп алгоритмі деп те аталады) сандарды төмендеу ретімен сұрыптап, оларды олардың айырмасымен қайта-қайта алмастырады. Орындалу уақытының күрделілігі O(n log n). Ең нашар жағдайда оның шамалау қатынасы да сондай – ең көп дегенде 7/6. Алайда, орташа жағдайда ол ашкөз алгоритмнен әлдеқайда жақсы жұмыс істейді: сандар [0,1] аралығында біркелкі таратылған кезде, оның шамалау қатынасы ең көп дегенде күтуде болады. Сондай-ақ, модельдеу тәжірибелерінде де жақсы нәтижелер көрсетеді. Multifit алгоритмі екілік іздеуді қоспақтап орналастыру алгоритмімен біріктіреді. Ең нашар жағдайда оның шамалау қатынасы 8/7-ге тең. Қосалқы жиынның сомасы мәселесі үшін FPTAS бар, оны бөлу мәселесі үшін де қолдануға болады, мақсатты соманы sum(S)/2 деп белгілеу арқылы.
Greedy number partitioning – loops over the numbers, and puts each number in the set whose current sum is smallest. If the numbers are not sorted, then the runtime is O(n) and the approximation ratio is at most 3/2 ("approximation ratio" means the larger sum in the algorithm output, divided by the larger sum in an optimal partition). Sorting the numbers increases the runtime to O(n log n) and improves the approximation ratio to 7/6. If the numbers are distributed uniformly in [0,1], then the approximation ratio is at most almost surely, and in expectation. Largest Differencing Method (also called the Karmarkar–Karp algorithm) sorts the numbers in descending order and repeatedly replaces numbers by their differences. The runtime complexity is O(n log n). In the worst case, its approximation ratio is similar – at most 7/6. However, in the average case it performs much better than the greedy algorithm: when numbers are distributed uniformly in [0,1], its approximation ratio is at most in expectation. It also performs better in simulation experiments. The Multifit algorithm uses binary search combined with an algorithm for bin packing. In the worst case, its approximation ratio is 8/7. The subset sum problem has an FPTAS which can be used for the partition problem as well, by setting the target sum to sum(S)/2.
Қиын жағдайлар мен фазалық ауысу
Тек бір немесе бөлігі жоқ жиынтықтарды кіріс мөлшерімен салыстырғанда шешу ең қиын (немесе ең қымбат) болады. Жиынның мөлшерімен салыстырғанда мәндер кішкентай болғанда, толық бөлінулерге жететін мүмкіндік артады. Бұл мәселе "фазалық өтуден" өтеді; кейбір жиынтықтар үшін ықтимал, ал басқалары үшін - емес. Егер m жиынтықтағы кез келген санды көрсетуге қажетті биттер саны болса, ал n жиынтықтың мөлшері болса, онда көптеген шешімдер болады, ал шешімдері аз немесе мүлдем болмайды. n және m ұлғайған сайын, толық бөліну ықтималдығы тиісінше 1 немесе 0-ге жақындайды. Бұл алғаш Гент пен Уолш эмпирикалық деректер негізінде, кейін Мертенс статистикалық физика әдістерін қолдана отырып, ал кейін Боргс, Чайес және Питтель дәлелдеді.
Ықтималдық нұсқасы
Туған күн парадоксына едәуір ұқсас, байланысты мәселе – кіріс жиынының мөлшерін анықтау, осылайша жиынның әрбір мүшесі 1-ден белгілі бір мәнге дейін тегіс үлестіріліммен кездейсоқ таңдалатын болса, шешімнің болу ықтималдығы жартыға жетеді. Осы мәселенің шешімі туған күн парадоксі сияқты, күтпеген болуы мүмкін.
Түрлері мен жалпылаулары
Тең кардиналдылықтағы бөліс – екі бөлігінің де бірдей сомаға ие болуымен қатар, бірдей мөлшерде элементтері болуын талап ететін нұсқа. Бұл нұсқа да NP-қиын. Ковалев пен Пеш партиция түріндегі мәселелердің NP-қиындығын дәлелдеудің жалпы тәсілі туралы әңгімелейді.
Қолданбалар
Бөлу проблемасының бір қолданылуы сайлауды бұрмалау болып табылады. Дәл айтқанда, үш үміткер бар делік (А, В және С). Бір үміткерді бағалау жүйесіне негізделген дауыс беру қағидасы арқылы сайлау керек, мысалы, вето қағидасы (әрбір сайлаушы бір үміткерге вето қояды және ең аз вето алған үміткер жеңіске жетеді). Егер коалиция С-нің сайлануын қамтамасыз етуді қаласа, олар өз дауыстарын А мен В арасында бөліп, олардың әрқайсысының алған ең аз ветосының санын барынша арттыруы керек. Дауыстар салмақты болса, онда бұл мәселені бөлу проблемасына келтіріп шешуге болады, соның салдарынан CKK арқылы тиімді шешім табуға болады. Осыған ұқсас, кез келген бағалау жүйесіне негізделген дауыс беру қағидасы үшін де осы принцип қолданылады.